Sequitur (или алгоритм Невилла-Мэннинга ) - это рекурсивный алгоритм, разработанный Крейгом Невиллом-Мэннингом и Яном Х. Виттеном в 1997 году [1], который выводит иерархическую структуру ( контекстно-свободную грамматику ) из последовательности дискретных символов. Алгоритм работает в линейном пространстве и времени. Его можно использовать в программных приложениях для сжатия данных. [2]
Ограничения [ править ]
Алгоритм sequitur создает грамматику, заменяя повторяющиеся фразы в заданной последовательности новыми правилами и, следовательно, дает краткое представление последовательности. Например, если последовательность
- S → abcab,
алгоритм произведет
- S → AcA, A → ab.
При сканировании входной последовательности алгоритм следует двум ограничениям для эффективной генерации своей грамматики: уникальность диграммы и полезность правила .
Уникальность диграммы [ править ]
Каждый раз, когда из последовательности сканируется новый символ, к нему добавляется последний отсканированный символ, чтобы сформировать новую биграмму . Если эта биграмма была сформирована ранее, то создается новое правило для замены обоих вхождений биграмм. Следовательно, это гарантирует, что никакая биграмма не встречается в грамматике более одного раза. Например, в последовательности S → abaaba , когда первые четыре символа уже отсканированы, образуются биграммы ab, ba, aa . При чтении пятого символа образуется новая биграмма «ab», которая уже существует. Таким образом, оба экземпляра «аb» заменяются новым правилом (скажем, A) в S . Теперь грамматика принимает вид S → AaAa, A → ab , и процесс продолжается до тех пор, пока в грамматике не перестанет существовать повторяющаяся биграмма.
Утилита правил [ править ]
Это ограничение гарантирует, что все правила используются более одного раза в правых частях всех продуктов грамматики, т. Е. Если правило встречается только один раз, его следует удалить из грамматики, а его вхождение следует заменить символами из который он создан. Например, в приведенном выше примере, если отсканировать последний символ и применить уникальность биграммы для «Aa», то грамматика выдаст: S → BB, A → ab, B → Aa . Теперь правило «A» встречается только один раз в грамматике в B → Aa . Следовательно, A удаляется, и, наконец, грамматика становится
- S → BB, B → aba .
Это ограничение помогает уменьшить количество правил в грамматике.
Краткое описание метода [ править ]
Алгоритм работает путем сканирования последовательности терминальных символов и построения списка всех пар символов, которые он прочитал. Каждый раз, когда обнаруживается второе вхождение пары, эти два вхождения заменяются в последовательности изобретенным нетерминальным символом., список пар символов корректируется в соответствии с новой последовательностью, и сканирование продолжается. Если нетерминальный символ пары используется только в определении только что созданного символа, используемый символ заменяется его определением, и символ удаляется из определенных нетерминальных символов. После завершения сканирования преобразованную последовательность можно интерпретировать как правило верхнего уровня в грамматике для исходной последовательности. Определения правил для нетерминальных символов, которые он содержит, можно найти в списке пар символов. Эти определения правил могут сами содержать дополнительные нетерминальные символы, определения правил которых также можно прочитать из любого места в списке пар символов. [3]
См. Также [ править ]
- Бесконтекстная грамматика
- Сжатие данных
- Сжатие данных без потерь
- Прямолинейная грамматика
- Кодирование пар байтов
Ссылки [ править ]
- ^ Невилл-Мэннинг, CG ; Виттен, IH (1997). «Идентификация иерархической структуры в последовательностях: алгоритм линейного времени». arXiv : cs / 9709102 . Bibcode : 1997cs ........ 9102N . Цитировать журнал требует
|journal=
( помощь ) - ^ Невилл-Мэннинг, CG ; Виттен, IH (1997). «Линейно-временной, инкрементный вывод иерархии для сжатия». Известия DCC '97. Конференция по сжатию данных . С. 3–11. CiteSeerX 10.1.1.30.2305 . DOI : 10.1109 / DCC.1997.581951 . ISBN 978-0-8186-7761-8.
- ^ GrammarViz 2.0 - Sequitur и параллельные реализации Sequitur в Java, обнаружение шаблонов временных рядов на основе Sequitur
Внешние ссылки [ править ]
- sequitur.info - эталонная реализация алгоритма Sequitur на C ++, Java и других языках.