Алгоритм Sequitur (Glikjnmb Sequitur)

Перейти к навигации Перейти к поиску

Алгоритм Sequitur (или алгоритм Невилла-Мэннинга) — рекурсивный алгоритм, разработанный Крейгом Невиллом-Мэннингом и Ианом Виттеном[en] в 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].

См. также[править | править код]

Примечания[править | править код]

  1. ↑ Nevill-Manning, Witten, 1997-1.
  2. ↑ Nevill-Manning, Witten, 1997-2, pp. 3–11.
  3. ↑ GrammarViz 2.0 — Реализация Sequitur и параллельный Sequitur на Java. Дата обращения: 10 сентября 2022. Архивировано 10 сентября 2022 года.

Литература[править | править код]

  • 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.

Ссылки[править | править код]

Источник — https://ru.wikipedia.org/w/index.php?title=Алгоритм_Sequitur&oldid=131468746