Алгоритм Sequitur
Алгоритм 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).