Алгоритм Sequitur: различия между версиями
In.wiki (комментарии | вклад) (→Ссылки) |
In.wiki (комментарии | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | Алгоритм '''Sequitur''' (или '''алгоритм Невилла-Мэннинга''') — [[рекурсивный алгоритм]], разработанный [[Невилл-Мэннинг, Крейг|Крейгом Невиллом-Мэннингом]] и {{нп5|Виттен, Иан Х.|Ианом Виттеном||Ian H. Witten}} в 1997 году{{sfn|Nevill-Manning, Witten|1997-1}}. Алгоритм создает [[Иерархическая структура|иерархическую структуру]] ([[Контекстно-свободная грамматика|контекстно-свободную грамматику]]) из последовательности дискретных символов, и алгоритм выполняется | + | Алгоритм '''Sequitur''' (или '''алгоритм Невилла-Мэннинга''') — [[рекурсивный алгоритм]], разработанный [[Невилл-Мэннинг, Крейг|Крейгом Невиллом-Мэннингом]] и {{нп5|Виттен, Иан Х.|Ианом Виттеном||Ian H. Witten}} в 1997 году{{sfn|Nevill-Manning, Witten|1997-1}}. Алгоритм создает [[Иерархическая структура|иерархическую структуру]] ([[Контекстно-свободная грамматика|контекстно-свободную грамматику]]) из последовательности дискретных символов, и алгоритм выполняется с линейным расходом памяти за линейное время, что является основной областью применения этого алгоритма в приложениях для [[Сжатие данных|сжатия данных]]{{sfn|Nevill-Manning, Witten|1997-2|pp=3–11}}. |
== Ограничения == | == Ограничения == | ||
Текущая версия от 21:29, 20 августа 2025
Алгоритм Sequitur (или алгоритм Невилла-Мэннинга) — рекурсивный алгоритм, разработанный Крейгом Невиллом-Мэннингом и Ианом Виттеном[англ.] в 1997 году[1]. Алгоритм создает иерархическую структуру (контекстно-свободную грамматику) из последовательности дискретных символов, и алгоритм выполняется с линейным расходом памяти за линейное время, что является основной областью применения этого алгоритма в приложениях для сжатия данных[2].
Ограничения[править | править код]
Алгоритм Sequitur строит грамматику путём подстановки вместо повторяющихся фраз в заданной последовательности нового правила, что позволяет сократить представление исходной последовательности. Например, если последовательностью будет:
- S→abcab,
алгоритм даёт:
- S→AcA, A→ab.
При просмотре входной строки алгоритм следует двум правилам для эффективной генерации грамматики: единственность пары символов и использование правила.
Единственность пары символов[править | править код]
Когда новый символ выбирается из последовательности, он добавляется к последнему выбранному символу, и формируется новая пара символов. Если такая пара была образована ранее, формируется новое правило для замены обоих вхождений пар символов.
Тем самым обеспечивается, что пара встречается не более одного раза в грамматике. Например, в последовательности S→abaaba после просмотра первых четырёх символов формируются пары ab, ba, aa. Когда выбирается пятый символ, новая пара "ab" уже была образована. Поэтому обе пары 'ab' заменяются в S новым правилом (скажем, A). Теперь грамматика превращается в S→AaAa, A→ab и процесс продолжается, пока не останется никаких повторяющихся пар.
Использование правила[править | править код]
Это ограничение обеспечивает то, что все правила используются более одного раза в правых частях грамматики. То есть, если правило встречается только один раз, его следует удалить из грамматики и должна быть осуществлена соответствующая подстановка. Например в вышеприведённом примере, если просматривается последний символ и применено правило единственности для 'Aa', то грамматика даст S→BB, A→ab, B→Aa. Теперь правило 'A' встречается только один раз в B→Aa. Поэтому A удаляется и, в конце концов, грамматика превращается в S→BB, B→aba.
Данное ограничение позволяет сократить число правил в грамматике.
Описание метода[править | править код]
Алгоритм анализирует последовательность терминальных символов, формируя список всех встречающихся пар символов. При повторном обнаружении пары оба её вхождения заменяются новым нетерминальным символом, список пар символов обновляется, чтобы соответствовать новой последовательности, и просмотр продолжается. Если пара нетерминальных символов встречается только в рамках определения только что созданного символа, этот символ заменяется своим определением и удаляется из списка нетерминальных символов. По завершении анализа преобразованная последовательность может быть интерпретирована, как правило верхнего уровня грамматики исходной последовательности. Определения правил для нетерминальных символов можно найти в списке пар. Эти определения правил могут сами содержать дополнительные нетерминальные символы, определения которых можно найти в том же списке пар[3].
См. также[править | править код]
Примечания[править | править код]
- ↑ Nevill-Manning, Witten, 1997-1.
- ↑ Nevill-Manning, Witten, 1997-2, pp. 3–11.
- ↑ GrammarViz 2.0 — Реализация Sequitur и параллельный Sequitur на Java. Дата обращения: 10 сентября 2022. Архивировано 10 сентября 2022 года.
Литература[править | править код]
- Nevill-Manning C.G., Witten I.H. Identifying Hierarchical Structure in Sequences: A linear-time algorithm. — 1997. — . — Шаблон:Arxiv.
- Nevill-Manning C.G., Witten I.H. Linear-Time, Incremental Hierarchy Inference for Compression // Proceedings DCC '97. Data Compression Conference. — 1997. — ISBN 978-0-8186-7761-8. — doi:10.1109/DCC.1997.581951.
Ссылки[править | править код]
Ошибка Lua в Модуль:Navbox на строке 353: attempt to index local 'listText' (a nil value).