Алгоритм CYK
-
Алгоритм Кока–Янгера–Касами (CYK)
- Алгоритм синтаксического анализа контекстно-свободных грамматик
- Опубликован Итиро Сакаи в 1961 году
- Назван в честь Джона Кока, Дэниела Янгера, Тадао Касами и Джейкоба Т. Шварца
-
Основные характеристики
- Использует восходящий синтаксический анализ и динамическое программирование
- Работает только с контекстно-свободными грамматиками в нормальной форме Хомского (CNF)
- Преобразует любую контекстно-свободную грамматику в CNF
-
Эффективность
- Наихудшее время работы в наихудшем случае: O(n^3 ⋅ |G|)
- Один из наиболее эффективных алгоритмов с точки зрения асимптотической сложности
-
Стандартная форма
- Требует преобразования грамматики в CNF
- Любая контекстно-свободная грамматика может быть преобразована в CNF
-
Алгоритм
- Рассматривает все возможные подстроки входной строки
- Устанавливает P[l,s,v] истинным, если подстрока может быть сгенерирована из нетерминального символа
- Переходит к подстрокам длиной 2 и более, проверяя производные
- Завершает процесс, если подстрока совпадает с начальным символом
-
Пример
- Грамматика: «она ест рыбу вилкой»
- Таблица CYK: P[i,j,k] содержит истинность для подстрок
- Предложение может быть сгенерировано, так как начальный символ находится в M[7,1]
-
Расширения
- Создание дерева синтаксического анализа: сохранение узлов дерева в массиве
- Разбор контекстно-свободных грамматик, отличных от CNF: обобщение алгоритма
- Синтаксический анализ взвешенных контекстно-свободных грамматик: сохранение весов в таблице P
-
Численная стабильность
- Суммирование логарифмической вероятности вместо умножения вероятностей
-
Алгоритм Вэлианта
- Время работы: O(n^2.38 ⋅ |G|)
- Зависимость от эффективного умножения матриц
- Ли доказал, что любой алгоритм может быть преобразован в алгоритм умножения матриц
-
Дополнительные ресурсы
- Анализатор GLR
- Анализатор Earley
- Анализатор пакетов
- Алгоритм «внутри–снаружи»