Алгоритм Sequitur - Sequitur algorithm

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

Ограничения

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

S → abcab,

алгоритм произведет

S → AcA, A → ab.

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

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

Каждый раз, когда новый символ сканируется из последовательности, к нему добавляется последний отсканированный символ, чтобы сформировать новый биграмма. Если эта биграмма была сформирована ранее, то создается новое правило для замены обоих вхождений биграмм, поэтому оно гарантирует, что никакая биграмма не встречается в грамматике более одного раза. Например, в последовательности S → абааба, когда первые четыре символа уже отсканированы, образуются биграммы. 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 → аба.

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

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

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

Смотрите также

Рекомендации

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

внешняя ссылка