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

Материал из NLPub
Перейти к: навигация, поиск

Алгоритм Кока — Янгера — Касами (англ. 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| — размер используемой грамматики.

См. также