Алгоритм Sequitur: различия между версиями
In.wiki (комментарии | вклад) м (20 версий импортировано: Импорт из Википедии) |
In.wiki (комментарии | вклад) (→Ссылки) |
||
| Строка 51: | Строка 51: | ||
* [http://www.sequitur.info/ sequitur.info — реализация алгоритма Sequitur на C++, Java и других языках] | * [http://www.sequitur.info/ sequitur.info — реализация алгоритма Sequitur на C++, Java и других языках] | ||
{{Методы сжатия|state=collapsed}} | {{Методы сжатия|state=collapsed}} | ||
| − | + | ||
| − | |||
| − | |||
| − | |||
| − | |||
[[Категория:Сжатие данных]] | [[Категория:Сжатие данных]] | ||
[[Категория:Алгоритмы сжатия без потерь]] | [[Категория:Алгоритмы сжатия без потерь]] | ||
Версия от 21:27, 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).