Как работает алгоритм CYK?

Алгоритм CYK принимает в качестве входных данных CFG в нормальной форме Хомского. Это означает, что каждое производство имеет форму

• S → a, для некоторого терминала a, или
• S → AB, для некоторых нетерминалов A и B.

Теперь представьте, что у вас есть строка w, и вы хотите узнать, можете ли вы извлечь ее из грамматики, начальный символ которой — S. Есть два варианта:

1. Если w — длина одного символа, то единственный способ проанализировать это — использовать продукцию вида S → a для некоторого символа a. Посмотрите, соответствует ли какой-либо из односимвольных произведений a.
2. Если w длиннее, чем один символ, то единственный способ проанализировать это — использовать произведение вида S → AB для некоторых нетерминалов A и B. Это означает, что нам нужно разделить строку w на две части x и y. где A выводит x, а B выводит y. Один из способов сделать это — попробовать все возможные способы разделения w на две части и посмотреть, работает ли какая-либо из них.

Обратите внимание, что здесь опция (2) оказывается проблемой рекурсивного разбора: чтобы узнать, можете ли вы вывести w из S, посмотрите, можете ли вы вывести x из A и y из B.

С этим пониманием, вот псевдокод для рекурсивной функции, которую вы можете использовать, чтобы увидеть, выводит ли нетерминал S строку w:

bool canDerive(nonterminal S, string w) {
return canDeriveRec(S, w, 0, w.size());
}

/* Can you derive the substring [start, end) of w from S? */
bool canDeriveRec(nonterminal S, string w, int start, int end) {
/* Base case: Single characters */
if (end - start == 1) {
return whether there is a production S -> a, where a = w[start];
}

/* Recursive case: Try all possible splits */
for (each production S -> AB) {
for (int mid = start + 1; mid < end; mid++) {
if (canDeriveRec(A, w, start, mid) &&
canDeriveRec(B, w, mid, end)) {
return true;
}
}
}
return false;
}

Этот алгоритм работает правильно, но если вы наметите форму рекурсии, вы обнаружите, что

1. он делает кучу избыточных рекурсивных вызовов, но
2. не так много разных возможных рекурсивных вызовов.

На самом деле количество возможных вызовов составляет O (n² N), где n — длина входной строки (для каждой возможной комбинации начального и конечного индексов), а N — количество нетерминалов в грамматике. Эти наблюдения показывают, что этот алгоритм выиграл бы либо от запоминания, либо от динамического программирования, в зависимости от того, какой подход вам кажется более приятным.

Алгоритм CYK — это то, что вы получаете, когда вы берете вышеупомянутый рекурсивный алгоритм и запоминаете результат, или эквивалентно, когда вы конвертируете вышеупомянутый рекурсивный алгоритм в задачу динамического программирования.

Есть O (n² N) возможные рекурсивные вызовы. Для каждого пробного производства это делает O (n) работу. Если для нетерминала имеется в среднем P производств, это означает, что общее время выполнения равно O (n³ NP), который является O (n³) для фиксированной грамматики.