Алгоритм CYK

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

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

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

Важность алгоритма CYK обусловлена ​​его высокой эффективностью в определенных ситуациях. Используя нотацию big 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 ] будет массивом списков троек обратных точек. Инициализируйте все элементы обратно в пустой список.для каждого  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 является членом языка return  back - прослеживая шаги назад, можно легко построить все возможные деревья синтаксического анализа строки. иначе  верните «не член языка»

Вероятностный 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 → a s  set  P [ 1 , s , v ] = Pr( R v → a s ) для каждого  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 ] если prob_splitting > P [ l , s , a ] то  установите  P [ l , s , a ] = prob_splitting set  back [ l , s , а ] = <p,b,c>если  P [n, 1 , 1 ] > 0 , то найдите дерево разбора, пройдя назад,  верните дерево разбора , иначе  верните «не член языка»

Как проза

Говоря неформально, этот алгоритм рассматривает каждую возможную подстроку входной строки и устанавливает значение true, если подстрока длины, начинающейся с, может быть сгенерирована из нетерминала . После рассмотрения подстрок длины 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}}}$

Теперь предложение «она ест рыбу вилкой» анализируется с помощью алгоритма CYK. В следующей таблице в i — номер строки (начиная снизу с 1), а j — номер столбца (начиная слева с 1). ${\displaystyle P[i,j,k]}$

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

Расширения

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

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

Разбор контекстно-свободных грамматик, отличных от CNF

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

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

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

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

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

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

Наихудшее время работы CYK равно , где n — длина анализируемой строки, а | г | — размер грамматики 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-е изд.). Нью-Йорк: Спрингер. п. 579. ИСБН 978-0-387-20248-8.
2. Итиро Сакаи, «Синтаксис в универсальном переводе». В материалах Международной конференции 1961 года по машинному переводу языков и прикладному языковому анализу, Канцелярия Ее Величества, Лондон, стр. 593-608, 1962.
3. Сипсер, Майкл (2006). Введение в теорию вычислений (2-е изд.). Бостон: Технология курса Томсона. Определение 2.8. ISBN 0-534-95097-3. ОСЛК  58544333.
4. Аббуд, Амир; Бакурсс, Артурс; Уильямс, Вирджиния Василевска (5 ноября 2015 г.). «Если текущие алгоритмы клики оптимальны, то и парсер Valiant оптимален». arXiv : 1504.01431 [cs.CC].

Источники

• Сакаи, Итироо (1962). Синтаксис в универсальном переводе . 1961 Международная конференция по машинному переводу языков и прикладному языковому анализу, Теддингтон, Англия. Том. II. Лондон: Канцелярия Ее Величества. стр. 593–608.
• Кок, Джон ; Шварц, Джейкоб Т. (апрель 1970 г.). Языки программирования и их компиляторы: Предварительные заметки (PDF) (Технический отчет) (2-е исправленное изд.). CIMS , Нью-Йоркский университет .
• Хопкрофт, Джон Э .; Уллман, Джеффри Д. (1979). Введение в теорию автоматов, языки и вычисления. Ридинг/Массачусетс: Аддисон-Уэсли. ISBN 0-201-02988-Х.
• Касами, Т. (1965). Эффективный алгоритм распознавания и синтаксического анализа контекстно-свободных языков (Технический отчет). АФКРЛ . 65-758.
• Кнут, Дональд Э. (14 ноября 1997 г.). Искусство компьютерного программирования. Том 2: Получисловые алгоритмы (3-е изд.). Аддисон-Уэсли Профессионал. п. 501. ИСБН 0-201-89684-2.
• Ланг, Бернард (1994). «Распознавание может быть сложнее, чем анализ». Вычислить. Интел. 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». Информатика Дидактика . 8 .
• Ли, Лилиан (2002). «Быстрый контекстно-свободный анализ грамматики требует быстрого умножения булевой матрицы». Дж. АКМ . 49 (1): 1–15. arXiv : cs/0112018 . дои : 10.1145/505241.505242. S2CID  1243491.
• Сипсер, Майкл (1997). Введение в теорию вычислений (1-е изд.). ИПС. п. 99. ИСБН 0-534-94728-Х.
• Валиант, Лесли Г. (1975). «Общее контекстно-свободное распознавание менее чем за кубическое время». Дж. Компьютер. Сист. наук. 10 (2): 308–314. дои : 10.1016/s0022-0000(75)80046-8 .
• Младший, Дэниел Х. (февраль 1967 г.). «Распознавание и синтаксический анализ контекстно-свободных языков за время n3». Поставить в известность. Контроль . 10 (2): 189–208. дои : 10.1016/s0019-9958(67)80007-x .

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

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