Алгоритм Кока — Янгера — Касами

Материал из NLPub
(перенаправлено с «Алгоритм CYK»)
Перейти к: навигация, поиск

Алгоритм Кока — Янгера — Касами (англ. Cocke–Younger–Kasami (CYK) algorithm) — алгоритм динамического программирования, выполняющий вывод входной строки в заданной контекстно-свободной грамматике.

Применение

Данный алгоритм применяется в задаче синтаксического разбора предложений на естественном языке.

Алгоритм

Вход: предложение и вероятностная контекстно-свободная грамматика .

Инициализация:

   for 
       
       for 
           
           

Алгоритм:

   for 
       
       for 
       
           
           
           for 
               
               
               
               

Выход: таблица с вероятностями терминалов и нетерминалов, записанных в .

Получение дерева

Необходимо проделать дополнительную работу, чтобы преобразовать предоставленные алгоритмом таблицы в дерево разбора предложения. Надо бы про это тоже написать.

# Build a constituent tree from the backpoints table.
def grow(tree, sentence, bp, i, n, x)
  y, z, s = bp[[i, n, x]]
  return tree << sentence[i - 1] unless y || z
  tree << grow([y], sentence, bp, i, s, y)
  tree << grow([z], sentence, bp, s + 1, n, z)
end

Сложность и время работы

В худшем случае, алгоритм выполняется за шагов, где — длина предложения, — размер используемой грамматики.

См. также