CYK алгоритм - CYK algorithm

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

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

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

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

В динамическое программирование алгоритм требует, чтобы контекстно-свободная грамматика была преобразована в Нормальная форма Хомского (CNF), потому что он проверяет возможность разделения текущей последовательности на две меньшие последовательности. Любая контекстно-свободная грамматика, которая не генерирует пустую строку, может быть представлена ​​в CNF с использованием только правила производства форм ${\displaystyle A\rightarrow \alpha }$ и ${\displaystyle A\rightarrow BC}$.

Алгоритм

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

Алгоритм в псевдокод составляет:

позволять вход будет строкой я состоящий из п символы: а1 ... ап.позволять грамматика содержит р нетерминальные символы р1 ... рр, с начальным символом р1.позволять п[п,п,р] быть массивом логических значений. Инициализировать все элементы п к ложному.для каждого s = От 1 до п    для каждого единичное производство рv → аs        набор п[1,s,v] = правдадля каждого л = От 2 до п - Длина пролета    для каждого s = От 1 до п-л+1 - Начало пролета        для каждого п = От 1 до л-1 - Перегородка пролета            для каждого производство ра    → рб рc                если п[п,s,б] и п[л-п,s+п,c] тогда набор п[л,s,а] = правдаесли п[п,1,1] правда тогда    я является членом языкаеще    я не является членом языка

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

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

позволять вход будет строкой я состоящий из п символы: а1 ... ап.позволять грамматика содержит р нетерминальные символы р1 ... рр, с начальным символом р1.позволять п[п,п,р] быть массивом действительных чисел. Инициализировать все элементы п до нуля.позволять назад[п,п,р] - массив троек обратных указателей.для каждого s = От 1 до п  для каждого единичное производство рv →аs    набор п[1,s,v] = Pr (рv →аs)для каждого л = От 2 до п - Длина пролета  для каждого s = От 1 до п-л+1 - Начало пролета    для каждого п = От 1 до л-1 - Перегородка пролета             для каждого производство ра → рб рc        prob_splitting = Pr (ра →рб рc) * п[п,s,б] * п[л-п,s+п,c]        если п[п,s,б]> 0 и п[л-п,s+п,c]> 0 и п[л,s,а] тогда           набор п[л,s,а] = prob_splitting набор назад[л,s,а] = 

Как проза

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

пример

Разбор предложений с использованием алгоритма 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. В следующей таблице в ${\displaystyle P[i,j,k]}$, я номер строки (начиная с 1 снизу), а j - номер столбца (начиная с 1 слева).

Таблица CYK

S
	Вице-президент
S
	Вице-президент			PP
S		НП			НП
НП	В, ВП	Дет.	N	п	Det	N
она	ест	а	рыбы	с участием	а	вилка

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

Расширения

Создание дерева синтаксического анализа

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

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

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

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

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

Алгоритм Valiant

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

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

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

• Парсер GLR
• Парсер Эрли
• Парсер Packrat

использованная литература

1. Грун, Дик (2008). Методы парсинга: практическое руководство (2-е изд.). Нью-Йорк: Спрингер. ISBN  978-0-387-20248-8.

Источники

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

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

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