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

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

Применение

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

Алгоритм

Вход: предложение $s = x_1...x_n$ и вероятностная контекстно-свободная грамматика $G = (N, \Sigma, R, S, q)$.

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

   for $i \in {1...n}$
       
       for $X \in N$
           
           $\pi(i,i,X) \leftarrow \begin{cases}
                      q(X \rightarrow x_i) & \text{if } X \rightarrow x_i \in R \\
                      0 & \text{otherwise}
                  \end{cases}$

Алгоритм:

   for $l \in {1...(n-1)}$
       
       for $i \in {1...(n-l)}$
       
           $j \leftarrow i + l$
           
           for $X \in N$
               
               $\pi(i,j,X) \leftarrow max_{X \rightarrow Y\mbox{ }Z \in R, s \in \{i...(j-1)\}} (q(X \rightarrow Y\mbox{ }Z) \times \pi(i,s,Y) \times \pi(s+1,j,Z))$
               
               $bp(i,j,X) \leftarrow argmax_{X \rightarrow Y\mbox{ }Z \in R, s \in \{i...(j-1)\}} (q(X \rightarrow Y\mbox{ }Z) \times \pi(i,s,Y) \times \pi(s+1,j,Z))$

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

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

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

# 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

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

В худшем случае, алгоритм выполняется за $O(n^3 \cdot |G|)$ шагов, где $n$ — длина предложения, $|G|$ — размер используемой грамматики.