Секвитур (или алгоритм Невилла-Мэннинга-Виттена ) — рекурсивный алгоритм, разработанный Крейгом Невиллом-Мэннингом и Яном Х. Виттеном в 1997 году [1] , который выводит иерархическую структуру ( контекстно-свободную грамматику ) из последовательности дискретных символов. Алгоритм работает в линейном пространстве и времени. Его можно использовать в программных приложениях для сжатия данных . [2]
Алгоритм секвитура строит грамматику, заменяя повторяющиеся фразы в заданной последовательности новыми правилами и, таким образом, создает краткое представление последовательности. Например, если последовательность
алгоритм произведет
При сканировании входной последовательности алгоритм соблюдает два ограничения для эффективной генерации своей грамматики: уникальность диграммы и полезность правила .
Всякий раз, когда из последовательности сканируется новый символ, он добавляется к последнему сканированному символу для формирования новой диграммы . Если эта диграмма была сформирована ранее, то создается новое правило для замены обоих вхождений диграмм. Таким образом, это гарантирует, что ни одна диграмма не встречается в грамматике более одного раза. Например, в последовательности S→abaaba , когда первые четыре символа уже сканируются, образуются диграммы ab, ba, aa . Когда считывается пятый символ, формируется новая диграмма 'ab', которая уже существует. Таким образом, оба экземпляра 'ab' заменяются новым правилом (скажем, A) в S. Теперь грамматика становится S→AaAa, A→ab , и процесс продолжается до тех пор, пока в грамматике не останется ни одной повторяющейся диграммы.
Это ограничение гарантирует, что все правила используются более одного раза в правых частях всех производных грамматики, т. е. если правило встречается только один раз, его следует удалить из грамматики, а его появление следует заменить символами, из которых оно создано. Например, в приведенном выше примере, если просканировать последний символ и применить уникальность диграммы для 'Aa', то грамматика выдаст: S→BB, A→ab, B→Aa . Теперь правило 'A' встречается только один раз в грамматике в B→Aa . Поэтому A удаляется, и в конечном итоге грамматика становится
Это ограничение помогает сократить количество правил в грамматике.
Алгоритм работает путем сканирования последовательности терминальных символов и построения списка всех пар символов, которые он считывал. Всякий раз, когда обнаруживается второе вхождение пары, два вхождения заменяются в последовательности изобретенным нетерминальным символом , список пар символов корректируется для соответствия новой последовательности, и сканирование продолжается. Если нетерминальный символ пары используется только в определении только что созданного символа, используемый символ заменяется его определением, а символ удаляется из определенных нетерминальных символов. После завершения сканирования преобразованная последовательность может быть интерпретирована как правило верхнего уровня в грамматике для исходной последовательности. Определения правил для нетерминальных символов, которые она содержит, можно найти в списке пар символов. Эти определения правил сами могут содержать дополнительные нетерминальные символы, определения правил которых также можно прочитать из другого места в списке пар символов. [3]
{{cite journal}}: Цитировать журнал требует |journal=( помощь )