Алгоритм CYK

Алгоритм анализа для контекстно-свободных грамматик

В информатике алгоритм Кока–Янгера–Касами (также называемый CYK или CKY ) — это алгоритм синтаксического анализа для контекстно-свободных грамматик, опубликованный Итироо Сакаи в 1961 году. ^{[1] [2]} Алгоритм назван в честь некоторых из его переоткрывателей: Джона Кока , Дэниела Янгера, Тадао Касами и Джейкоба Т. Шварца . Он использует синтаксический анализ снизу вверх и динамическое программирование .

Стандартная версия CYK работает только с контекстно-свободными грамматиками, заданными в нормальной форме Хомского (CNF). Однако любая контекстно-свободная грамматика может быть алгоритмически преобразована в грамматику CNF, выражающую тот же язык (Sipser 1997).

Важность алгоритма CYK обусловлена ​​его высокой эффективностью в определенных ситуациях. Используя нотацию O большое , худшее время выполнения CYK равно , где — длина анализируемой строки, а — размер грамматики CNF (Hopcroft & Ullman 1979, стр. 140). Это делает его одним из самых эффективных ^{[ требуется цитирование ]} алгоритмов синтаксического анализа с точки зрения асимптотической сложности в худшем случае , хотя существуют и другие алгоритмы с лучшим средним временем выполнения во многих практических сценариях. ${\displaystyle {\mathcal {O}}\left(n^{3}\cdot \left|G\right|\right)}$ ${\displaystyle n}$ ${\displaystyle \left|G\right|}$ ${\displaystyle G}$

Стандартная форма

Алгоритм динамического программирования требует, чтобы контекстно-свободная грамматика была представлена ​​в нормальной форме Хомского (CNF), поскольку она проверяет возможности разделения текущей последовательности на две меньшие последовательности. Любая контекстно-свободная грамматика, которая не генерирует пустую строку, может быть представлена ​​в CNF с использованием только правил производства форм и ; чтобы разрешить пустую строку, можно явно разрешить , где — начальный символ. ^[3] ${\displaystyle A\rightarrow \alpha }$ ${\displaystyle A\rightarrow BC}$ ${\displaystyle S\to \varepsilon }$ ${\displaystyle S}$

Алгоритм

Как псевдокод

Алгоритм в псевдокоде выглядит следующим образом:

пусть входными данными будет строка I, состоящая из n символов: a 1 ... a n . пусть грамматика содержит r нетерминальных символов R 1 ... R r , с начальным символом R 1 . пусть  P [ n , n , r ] будет массивом булевых значений. Инициализируйте все элементы P значением false. пусть  back [ n , n , r ] будет массивом списков троек возврата. Инициализируйте все элементы back пустым списком.для каждого  s = 1 до n  для каждой единицы продукции R v → a s  set  P [ 1 , s , v ] = trueдля каждого  l = 2 до n  -- Длина промежутка  для каждого  s = 1 до n - l +1 -- Начало промежутка  для каждого  p = 1 до l -1 -- Разбиение промежутка  для каждого произведения R a → R b  R c  если  P [ p , s , b ] и P [ l - p , s + p , c ], то  устанавливаем  P [ l , s , a ] = true, добавить <p,b,c> к задним [ l , s , a ]если  P [n, 1 , 1 ] истинно, то  I является членом языка вернуться  назад — повторяя шаги назад, можно легко построить все возможные деревья разбора строки. в противном случае  вернуть «не является членом языка»

Вероятностный CYK (для поиска наиболее вероятного синтаксического анализа)

Позволяет восстановить наиболее вероятный синтаксический анализ с учетом вероятностей всех продукций.

пусть входными данными будет строка I, состоящая из n символов: a 1 ... a n . пусть грамматика содержит r нетерминальных символов R 1 ... R r , с начальным символом R 1 . пусть  P [ n , n , r ] будет массивом действительных чисел. Инициализируем все элементы P нулем. пусть  back [ n , n , r ] будет массивом троек обратной точки. для каждого  s = 1 до n  для каждой единицы продукции R v → as set P [ 1 , s , v  ] = Pr( R v → as ) для каждого l = 2 до n -- Длина промежутка для каждого s = 1 до n - l +1 -- Начало промежутка для каждого p = 1 до l -1 -- Разбиение промежутка для каждого производства R a → R b R c prob_splitting = Pr( R a → R b R c ) * P [ p , s , b ] * P [ l - p , s + p , c ] if prob_splitting > P [ l , s , a ] then set P [ l , s , a ] = prob_splitting set back [ l , s , a ] = <p,b,c>             если  P [n, 1 , 1 ] > 0 , то найти дерево разбора, пройдя по нему в обратном направлении  , вернуть дерево разбора, иначе  вернуть «не является членом языка»

Как проза

Неформально этот алгоритм рассматривает каждую возможную подстроку входной строки и устанавливает ее как истинную, если подстрока длины, начинающаяся с , может быть сгенерирована из нетерминала . После того, как он рассмотрел подстроки длины 1, он переходит к подстрокам длины 2 и так далее. Для подстрок длины 2 и больше он рассматривает каждое возможное разбиение подстроки на две части и проверяет, есть ли какая-либо продукция, которая соответствует первой части и соответствует второй части. Если это так, он записывает как соответствующую всей подстроке. После завершения этого процесса входная строка генерируется грамматикой, если подстрока, содержащая всю входную строку, соответствует начальному символу. ${\displaystyle P[l,s,v]}$ ${\displaystyle l}$ ${\displaystyle s}$ ${\displaystyle R_{v}}$ ${\displaystyle A\to B\;C}$ ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle A}$

Пример

Разбор предложений с использованием алгоритма CYK

Вот пример грамматики:

${\displaystyle {\begin{aligned}{\ce {S}}&\ {\ce {->NP\ VP}}\\{\ce {VP}}&\ {\ce {->VP\ PP}}\\{\ce {VP}}&\ {\ce {->V\ NP}}\\{\ce {VP}}&\ {\ce {->eats}}\\{\ce {PP}}&\ {\ce {->P\ NP}}\\{\ce {NP}}&\ {\ce {->Det\ N}}\\{\ce {NP}}&\ {\ce {->she}}\\{\ce {V}}&\ {\ce {->eats}}\\{\ce {P}}&\ {\ce {->with}}\\{\ce {N}}&\ {\ce {->fish}}\\{\ce {N}}&\ {\ce {->fork}}\\{\ce {Det}}&\ {\ce {->a}}\end{aligned}}}$

Теперь предложение she eats a fish with a fork анализируется с помощью алгоритма CYK. В следующей таблице, в , i - это номер строки (начиная снизу с 1), а j - это номер столбца (начиная слева с 1). ${\displaystyle P[i,j,k]}$

Для удобства чтения таблица CYK для P представлена ​​здесь как двумерная матрица M , содержащая набор нетерминальных символов, таких, что R _k находится в ⁠ ⁠ ${\displaystyle M[i,j]}$ тогда и только тогда, ⁠ ⁠ ${\displaystyle P[i,j,k]}$ . В приведенном выше примере, поскольку начальный символ S находится в ⁠ ⁠ ${\displaystyle M[7,1]}$ , предложение может быть сгенерировано грамматикой.

Расширения

Генерация дерева разбора

Приведенный выше алгоритм является распознавателем , который будет определять только, находится ли предложение в языке. Его просто расширить до синтаксического анализатора , который также строит дерево синтаксического анализа , сохраняя узлы дерева синтаксического анализа как элементы массива, вместо логического значения 1. Узел связан с элементами массива, которые использовались для его создания, чтобы построить структуру дерева. Если необходимо создать только одно дерево синтаксического анализа, необходим только один такой узел в каждом элементе массива. Однако, если необходимо сохранить все деревья синтаксического анализа неоднозначного предложения, необходимо сохранить в элементе массива список всех способов, которыми соответствующий узел может быть получен в процессе синтаксического анализа. Иногда это делается с помощью второй таблицы B[n,n,r] так называемых обратных указателей . Конечным результатом является общий лес возможных деревьев синтаксического анализа, где общие части деревьев факторизуются между различными синтаксическими анализами. Этот общий лес можно удобно интерпретировать как неоднозначную грамматику, генерирующую только проанализированное предложение, но с той же неоднозначностью, что и исходная грамматика, и те же деревья синтаксического анализа вплоть до очень простого переименования нетерминалов, как показано Лэнгом (1994).

Анализ контекстно-свободных грамматик, не являющихся CNF

Как отметили Ланге и Лейсс (2009), недостатком всех известных преобразований в нормальную форму Хомского является то, что они могут привести к нежелательному раздуванию размера грамматики. Размер грамматики равен сумме размеров ее правил производства, где размер правила равен единице плюс длина его правой части. Используя для обозначения размера исходной грамматики, раздувание размера в худшем случае может варьироваться от до , в зависимости от используемого алгоритма преобразования. Для использования в обучении Ланге и Лейсс предлагают небольшое обобщение алгоритма CYK, «без ущерба для эффективности алгоритма, ясности его представления или простоты доказательств» (Ланге и Лейсс 2009). ${\displaystyle g}$ ${\displaystyle g^{2}}$ ${\displaystyle 2^{2g}}$

Анализ взвешенных контекстно-свободных грамматик

Также возможно расширить алгоритм CYK для разбора строк с использованием взвешенных и стохастических контекстно-свободных грамматик . Веса (вероятности) затем хранятся в таблице P вместо булевых значений, поэтому P[i,j,A] будет содержать минимальный вес (максимальную вероятность) того, что подстрока от i до j может быть получена из A. Дальнейшие расширения алгоритма позволяют перечислять все разборы строки от наименьшего к наибольшему весу (от наибольшей к наименьшей вероятности).

Численная стабильность

Когда вероятностный алгоритм CYK применяется к длинной строке, вероятность разделения может стать очень маленькой из-за умножения многих вероятностей. С этим можно справиться, суммируя логарифмическую вероятность вместо умножения вероятностей.

Алгоритм Валианта

Худшее время выполнения CYK составляет , где n — длина анализируемой строки, а | G | — размер грамматики CNF G . Это делает его одним из самых эффективных алгоритмов для распознавания общих контекстно-свободных языков на практике. Валиант (1975) дал расширение алгоритма CYK. Его алгоритм вычисляет ту же таблицу синтаксического анализа, что и алгоритм CYK; однако он показал, что алгоритмы для эффективного умножения матриц с 0-1-элементами могут быть использованы для выполнения этого вычисления. ${\displaystyle \Theta (n^{3}\cdot |G|)}$

Используя алгоритм Копперсмита–Винограда для умножения этих матриц, это дает асимптотическое худшее время выполнения . Однако постоянный член, скрытый нотацией Big O, настолько велик, что алгоритм Копперсмита–Винограда имеет смысл только для матриц, которые слишком велики для обработки на современных компьютерах (Knuth 1997), и этот подход требует вычитания и поэтому подходит только для распознавания. Зависимости от эффективного умножения матриц нельзя полностью избежать: Ли (2002) доказал, что любой синтаксический анализатор для контекстно-свободных грамматик, работающий во времени, может быть эффективно преобразован в алгоритм, вычисляющий произведение -матриц с 0-1-элементами за время , и это было расширено Аббудом и др. ^[4] для применения к грамматике постоянного размера. ${\displaystyle O(n^{2.38}\cdot |G|)}$ ${\displaystyle O(n^{3-\varepsilon }\cdot |G|)}$ ${\displaystyle (n\times n)}$ ${\displaystyle O(n^{3-\varepsilon /3})}$

Смотрите также

• GLR-парсер
• Ранний парсер
• Анализатор Packrat
• Алгоритм «изнутри-снаружи»

Ссылки

1. Грюн, Дик (2008). Методы анализа: практическое руководство (2-е изд.). Нью-Йорк: Springer. С. 579. ISBN 978-0-387-20248-8.
2. Итироо Сакаи, «Синтаксис в универсальном переводе». В трудах Международной конференции 1961 года по машинному переводу языков и прикладному языковому анализу, Канцелярия Ее Величества, Лондон, стр. 593-608, 1962.
3. Sipser, Michael (2006). Введение в теорию вычислений (2-е изд.). Boston: Thomson Course Technology. Определение 2.8. ISBN 0-534-95097-3. OCLC  58544333.
4. Аббуд, Амир; Бэкурс, Артурс; Уильямс, Вирджиния Василевска (2015-11-05). «Если текущие алгоритмы клики оптимальны, то и парсер Valiant оптимален». arXiv : 1504.01431 [cs.CC].

Источники

• Сакаи, Итиро (1962). Синтаксис в универсальном переводе . Международная конференция по машинному переводу языков и прикладному языковому анализу 1961 г., Теддингтон, Англия. Т. II. Лондон: Канцелярия Ее Величества. С. 593–608.
• Кок, Джон ; Шварц, Джейкоб Т. (апрель 1970 г.). Языки программирования и их компиляторы: Предварительные замечания (PDF) (Технический отчет) (2-е пересмотренное издание). CIMS , Нью-Йоркский университет .
• Хопкрофт, Джон Э .; Ульман, Джеффри Д. (1979). Введение в теорию автоматов, языки и вычисления. Чтение/МА: Addison-Wesley. ISBN 0-201-02988-X.
• Касами, Т. (1965). Эффективный алгоритм распознавания и синтаксического анализа для контекстно-свободных языков (Технический отчет). AFCRL . 65-758.
• Кнут, Дональд Э. (14 ноября 1997 г.). Искусство программирования. Том 2: Получисленные алгоритмы (3-е изд.). Addison-Wesley Professional. стр. 501. ISBN 0-201-89684-2.
• Лэнг, Бернард (1994). «Распознавание может быть сложнее синтаксического анализа». Comput. Intell. 10 (4): 486–494. CiteSeerX  10.1.1.50.6982 . doi :10.1111/j.1467-8640.1994.tb00011.x. S2CID  5873640.
• Ланге, Мартин; Лейсс, Ганс (2009). «К CNF или не к CNF? Эффективная, но презентабельная версия алгоритма CYK». Informatica Didactica . 8 .
• Ли, Лиллиан (2002). «Быстрый контекстно-свободный синтаксический анализ грамматики требует быстрого умножения булевых матриц». J. ACM . 49 (1): 1–15. arXiv : cs/0112018 . doi :10.1145/505241.505242. S2CID  1243491.
• Сипсер, Майкл (1997). Введение в теорию вычислений (1-е изд.). IPS. стр. 99. ISBN 0-534-94728-X.
• Валиант, Лесли Г. (1975). «Общее контекстно-свободное распознавание за время, меньшее, чем кубическое». J. Comput. Syst. Sci. 10 (2): 308–314. doi : 10.1016/s0022-0000(75)80046-8 .
• Younger, Daniel H. (февраль 1967). «Распознавание и анализ контекстно-свободных языков во времени n3». Inform. Control . 10 (2): 189–208. doi : 10.1016/s0019-9958(67)80007-x .

Внешние ссылки

• Интерактивная визуализация алгоритма CYK
• Демонстрация анализа CYK в JavaScript
• Exorciser — это Java-приложение для генерации упражнений по алгоритму CYK, а также по конечным автоматам, алгоритмам Маркова и т. д.