Войти
Sequitur (или алгоритм Невилла-Мэннинга ) рекурсивный алгоритм, разработанный Крейгом Невиллом-Мэннингом и Яном Х. Виттеном в 1997 году, который выводит иерархическую структуру (контекстно-свободную грамматику ) из последовательности дискретных символы. Алгоритм работает в линейном пространстве и времени. Его можно использовать в программных приложениях сжатия данных.
Алгоритм sequitur строит грамматику, заменяя повторяющиеся фразы в заданной последовательности новыми правилами и, следовательно, дает краткое представление последовательности. Например, если последовательность
, алгоритм выдаст
При сканировании входной последовательности алгоритм следует двум ограничениям для создания своей грамматики. эффективно: уникальность диграммы и утилита правил .
Каждый раз, когда новый символ сканируется из последовательности, к нему добавляется последний отсканированный символ, чтобы сформировать новый биграмма. Если эта биграмма была сформирована раньше, то создается новое правило для замены обоих вхождений биграмм. Следовательно, это гарантирует, что никакая биграмма не встречается в грамматике более одного раза. Например, в последовательности S → abaaba, когда первые четыре символа уже отсканированы, образуются биграммы ab, ba, aa . При чтении пятого символа образуется новая биграмма «ab», которая уже существует. Следовательно, оба экземпляра 'ab' заменяются новым правилом (скажем, A) в S. Теперь грамматика принимает вид S → AaAa, A → ab, и процесс продолжается до тех пор, пока не перестанет существовать повторяющаяся биграмма. в грамматике.
Это ограничение гарантирует, что все правила используются более одного раза в правых частях всех производных грамматики, т. Е. Если правило встречается только один раз, оно должно быть удаляется из грамматики, и его вхождение должно быть заменено символами, из которых оно создано. Например, в приведенном выше примере, если отсканировать последний символ и применить уникальность биграммы для «Aa», грамматика выдаст: S → BB, A → ab, B → Aa . Теперь правило A встречается в грамматике только один раз в B → Aa . Следовательно, A удаляется, и, наконец, грамматика становится
. Это ограничение помогает уменьшить количество правил в грамматике.
Алгоритм работает путем сканирования последовательности оконечных символов и построения списка всех пар символов, которые он прочитал. Когда обнаруживается второе вхождение пары, эти два вхождения заменяются в последовательности изобретенным нетерминальным символом, список пар символов корректируется для соответствия новой последовательности, и сканирование продолжается. Если нетерминальный символ пары используется только в определении только что созданного символа, используемый символ заменяется его определением, и символ удаляется из определенных нетерминальных символов. После завершения сканирования преобразованную последовательность можно интерпретировать как правило верхнего уровня в грамматике для исходной последовательности. Определения правил для нетерминальных символов, которые он содержит, можно найти в списке пар символов. Эти определения правил могут сами по себе содержать дополнительные нетерминальные символы, определения правил которых также можно прочитать из любого места в списке пар символов.
