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

В информатике , то алгоритм Кок-младший-Касами (альтернативно называемый CYK или CKY ) является синтаксический алгоритм для контекстно-свободных грамматик опубликованных Itiroo Сакаи в 1961 году алгоритм был назван в честь некоторых из его rediscoverers: Джон Кок , Даниэль Младшей , Тадао Касами и Джейкоб Т. Шварц . Он использует восходящий анализ и динамическое программирование .

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

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

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

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

Алгоритм

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

Алгоритм в псевдокоде следующий:

let the input be a string I consisting of n characters: a1 ... an.
let the grammar contain r nonterminal symbols R1 ... Rr, with start symbol R1.
let P[n,n,r] be an array of booleans. Initialize all elements of P to false.

for each s = 1 to n
    for each unit production Rv → as
        set P[1,s,v] = true

for each l = 2 to n -- Length of span
    for each s = 1 to n-l+1 -- Start of span
        for each p = 1 to l-1 -- Partition of span
            for each production Ra    → Rb Rc
                if P[p,s,b] and P[l-p,s+p,c] then set P[l,s,a] = true

if P[n,1,1] is true then
    I is member of language
else
    I is not member of language

let the input be a string I consisting of n characters: a1 ... an.
let the grammar contain r nonterminal symbols R1 ... Rr, with start symbol R1.
let P[n,n,r] be an array of real numbers. Initialize all elements of P to zero.
let back[n,n,r] be an array of backpointing triples.
for each s = 1 to n
  for each unit production Rv →as
    set P[1,s,v] = Pr(Rv →as)
for each l = 2 to n -- Length of span
  for each s = 1 to n-l+1 -- Start of span
    for each p = 1 to l-1 -- Partition of span       
      for each production Ra → Rb Rc
        prob_splitting = Pr(Ra →Rb Rc) * P[p,s,b] * P[l-p,s+p,c]
        if P[p,s,b] > 0 and P[l-p,s+p,c] > 0 and P[l,s,a] <  prob_splitting then 
          set P[l,s,a] = prob_splitting
          set back[l,s,a] = <p,b,c>

Как проза

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

Пример

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

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

${\ displaystyle {\ begin {align} {\ ce {S}} & \ {\ ce {-> NP \ VP}} \\ {\ ce {VP}} & \ {\ ce {-> VP \ PP} } \\ {\ ce {VP}} & \ {\ ce {-> V \ NP}} \\ {\ ce {VP}} & \ {\ ce {-> ест}} \\ {\ ce {PP }} & \ {\ ce {-> P \ NP}} \\ {\ ce {NP}} & \ {\ ce {-> Det \ N}} \\ {\ ce {NP}} & \ {\ ce {-> she}} \\ {\ ce {V}} & \ {\ ce {-> ест}} \\ {\ ce {P}} & \ {\ ce {-> with}} \\ { \ ce {N}} & \ {\ ce {-> fish}} \\ {\ ce {N}} & \ {\ ce {-> fork}} \\ {\ ce {Det}} & \ {\ ce {-> a}} \ end {выровнено}}}$

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

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

Расширения

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

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

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

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

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

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

Алгоритм Valiant

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

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

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

• Парсер GLR
• Парсер Эрли
• Парсер Packrat
• Внутренний – внешний алгоритм

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

Источники

• Сакаи, Итироо (1962). Синтаксис в универсальном переводе . 1961 Международная конференция по машинному переводу языков и прикладному языковому анализу, Теддингтон, Англия. II . Лондон: Канцелярия Ее Величества. С. 593–608.
• Кок, Джон ; Шварц, Джейкоб Т. (апрель 1970 г.). Языки программирования и их компиляторы: Предварительные примечания (PDF) (Технический отчет) (2-е исправленное изд.). CIMS , Нью-Йоркский университет .
• Хопкрофт, Джон Э .; Ульман, Джеффри Д. (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 . DOI : 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 . DOI : 10.1145 / 505241.505242 .
• Сипсер, Майкл (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 .
• Младший, Дэниел Х. (февраль 1967 г.). «Распознавание и парсинг контекстно-свободных языков за время n ³ » . Сообщить. Контроль . 10 (2): 189–208. DOI : 10.1016 / s0019-9958 (67) 80007-х .

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

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