Алгоритм следующий
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
Внешние ссылки [ править ]
сжатия данных Методы | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| без потерь |
| ||||||||
| с потерями |
| ||||||||
| Аудио |
| ||||||||
| Изображение |
| ||||||||
| видео |
| ||||||||
| Теория | |||||||||
| Сообщество | |||||||||
| Люди | |||||||||
