Оглавление [Скрыть]
Алгоритм определения последовательности
-
Описание алгоритма Sequitur
- Sequitur – рекурсивный алгоритм для генерации контекстно-свободной грамматики из последовательности символов.
- Разработан Крейгом Невиллом-Мэннингом и Иэном Х. Виттеном в 1997 году.
- Работает в линейном пространстве и времени, может использоваться для сжатия данных.
-
Ограничения алгоритма Sequitur
- Уникальность диграммы: предотвращает повторное появление диграмм в грамматике.
- Полезность правила: все правила должны использоваться более одного раза для сохранения эффективности грамматики.
-
Краткое описание метода Sequitur
- Сканирование последовательности и составление списка пар символов.
- Замена повторяющихся пар символов нетерминальным символом и корректировка списка пар.
- Завершение сканирования приводит к интерпретации последовательности как правила грамматики.
- Правила для нетерминальных символов могут содержать дополнительные нетерминалы, определенные из списка пар символов.
-
Ссылки и рекомендации
- Ссылки на контекстно-свободные грамматики, сжатие данных и другие связанные темы.
- Ссылка на эталонную реализацию алгоритма Sequitur на различных языках программирования.
Полный текст статьи: