Из Википедии, бесплатной энциклопедии
  (Перенаправлено из алгоритма SEQUITUR )
Перейти к навигации Перейти к поиску

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]

См. Также [ править ]

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

  1. ^ Невилл-Мэннинг, CG ; Виттен, IH (1997). «Идентификация иерархической структуры в последовательностях: алгоритм линейного времени». arXiv : cs / 9709102 . Bibcode : 1997cs ........ 9102N . Цитировать журнал требует |journal=( помощь )
  2. ^ Невилл-Мэннинг, 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.
  3. ^ GrammarViz 2.0 - Sequitur и параллельные реализации Sequitur в Java, обнаружение шаблонов временных рядов на основе Sequitur

Внешние ссылки [ править ]

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