Алгоритм следующий

Sequitur (или алгоритм Невилла-Мэннинга-Виттена ) — рекурсивный алгоритм, разработанный Крейгом Невилл-Мэннингом и Яном Х. Виттеном в 1997 году. ^[1] который выводит иерархическую структуру ( контекстно-свободную грамматику ) из последовательности дискретных символов. Алгоритм работает в линейном пространстве и времени. Его можно использовать в для сжатия данных . программных приложениях ^[2]

Ограничения

Алгоритм секвитура создает грамматику, заменяя повторяющиеся фразы в заданной последовательности новыми правилами и, следовательно, создает краткое представление последовательности. Например, если последовательность

S→abcab,

алгоритм выдаст

S→AcA, A→ab.

При сканировании входной последовательности алгоритм следует двум ограничениям для эффективной генерации своей грамматики: уникальность диграммы и полезность правила .

Уникальность диграммы

Всякий раз, когда из последовательности сканируется новый символ, к нему добавляется последний отсканированный символ, образуя новую биграмму . Если эта биграмма была сформирована ранее, то создается новое правило для замены обоих вхождений биграмм.Таким образом, это гарантирует, что ни одна биграмма не встречается в грамматике более одного раза. Например, в последовательности S→abaaba , когда уже отсканированы первые четыре символа, образуются биграммы ab, ba, aa . При чтении пятого символа формируется новая биграмма «ab», которая уже существует. Следовательно, оба экземпляра «ab» заменяются новым правилом (скажем, A) S. в Теперь грамматика становится S→AaAa, A→ab , и процесс продолжается до тех пор, пока в грамматике не останется повторяющихся биграмм.

Утилита правил

Это ограничение гарантирует, что все правила используются более одного раза в правых частях всех продукций грамматики, т. е. если правило встречается только один раз, его следует удалить из грамматики и заменить его символами из которым он создан. Например, в приведенном выше примере, если сканировать последний символ и применить уникальность биграммы для «Aa», то грамматика выдаст: S→BB, A→ab, B→Aa . Теперь правило «A» встречается в грамматике только один раз в B→Aa . Следовательно, A удаляется, и, наконец, грамматика становится

S→BB, B→aba .

Это ограничение помогает уменьшить количество правил в грамматике.

Краткое описание метода

Алгоритм работает путем сканирования последовательности терминальных символов и построения списка всех прочитанных пар символов. Всякий раз, когда обнаруживается второе вхождение пары, два вхождения в последовательности заменяются изобретенным нетерминальным символом , список пар символов корректируется в соответствии с новой последовательностью, и сканирование продолжается. Если нетерминальный символ пары используется только в определении только что созданного символа, используемый символ заменяется его определением, а символ удаляется из определенных нетерминальных символов. После завершения сканирования преобразованную последовательность можно интерпретировать как правило верхнего уровня в грамматике исходной последовательности. Определения правил для содержащихся в нем нетерминальных символов можно найти в списке пар символов. Эти определения правил сами могут содержать дополнительные нетерминальные символы, определения правил которых также можно прочитать из любого места в списке пар символов. ^[3]

См. также

Ссылки

^ Невилл-Мэннинг, CG ; Виттен, Айленд (1997). «Идентификация иерархической структуры в последовательностях: алгоритм линейного времени». arXiv : cs/9709102 . Бибкод : 1997cs........9102N . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Невилл-Мэннинг, CG ; Виттен, Айленд (1997). «Линейное время, инкрементальный вывод иерархии для сжатия». Труды ДКК '97. Конференция по сжатию данных . стр. 3–11. CiteSeerX 10.1.1.30.2305 . дои : 10.1109/DCC.1997.581951 . ISBN 978-0-8186-7761-8 . S2CID 14324301 .
^ GrammarViz 2.0 - Sequitur и параллельные реализации Sequitur на Java, обнаружение шаблонов временных рядов на основе Sequitur

Внешние ссылки

sequitur.info — эталонная реализация алгоритма Sequitur на C++, Java и других языках.

[Nevill-manning1997-1] Невилл-Мэннинг, CG ; Виттен, Айленд (1997). «Идентификация иерархической структуры в последовательностях: алгоритм линейного времени». arXiv : cs/9709102 . Бибкод : 1997cs........9102N . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[Nevill-manning1997_2-2] Невилл-Мэннинг, CG ; Виттен, Айленд (1997). «Линейное время, инкрементальный вывод иерархии для сжатия». Труды ДКК '97. Конференция по сжатию данных . стр. 3–11. CiteSeerX 10.1.1.30.2305 . дои : 10.1109/DCC.1997.581951 . ISBN 978-0-8186-7761-8 . S2CID 14324301 .

[3] GrammarViz 2.0 - Sequitur и параллельные реализации Sequitur на Java, обнаружение шаблонов временных рядов на основе Sequitur

[1]

[2]

[3]