Введение

Sequitur (или алгоритм Невилла Маннинга — Виттена) — рекурсивный алгоритм, разработанный Крейгом Невилом Маннингом и Ианом Х. Виттеном в 1997 году, который выводит иерархическую структуру (формальную грамматику) из последовательности дискретных символов. Алгоритм работает за линейное время и использует линейный объём памяти. Его можно использовать в приложениях для сжатия данных.

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

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

Резюме метода

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