Грамматический разбор для естественных языков. Ч.2: Алгоритм Кока—Янгера—Касами (CYK)

Часть .1: Языки описания языков

В идеале нам хотелось бы разбирать текст за линейное время и за один проход. Регулярные выражения это позволяют, но уже с CFG это не получится: например, S → A | B; A → a | x A; B → b | x B превращает строку x…xa в дерево из узлов A, а строку x…xb в дерево из узлов B — и пока разборщик не увидит последний символ строки, он не знает, что делать со всеми предыдущими символами. Поэтому на грамматики для языков программирования накладывают дополнительные ограничения — по сути, чтобы для разбора не приходилось «заглядывать вперёд» — позволяющие разбирать текст программы за один проход. Кто ковырялся в компиляторах, тот наверняка знаком с LL- и LR-разбором, и имеет опыт «подгонки» грамматики языка под требования конкретного алгоритма разбора. Но при работе с естественными языками нет возможности «подправить» язык для удобства разбора — приходится работать с тем языком, какой есть.

В 1960-х был разработан алгоритм CYK для разбора произвольного CFG. Считается, что впервые его опубликовали — независимо друг от друга — И. Сакаи из японского НИИ Минобороны в 1961 и Дж. Кок из Нью-Йоркского университета в 1962. В 1966 тот же самый алгоритм публиковали — опять независимо — Д. Янгер из General Electric и Т. Касами из Университета Иллинойса. Янгер в своей публикации упоминает имена Кока и Сакаи, но не ссылается ни на какие конкретные их работы: по всей видимости, работы Кока и Сакаи Янгеру — как и мне сейчас — не были доступны. Чтобы никому из изобретателей алгоритма не было обидно, его называют в честь сразу троих, хотя они, скорее всего, даже не были между собой знакомы.

Идея CYK заключается в разборе «снизу вверх» — от терминалов к S — и использовании динамического программирования для избежания повторных вычислений: вначале составим все узлы, выводимые непосредственно из терминалов, и поместим их на «доску». На каждом шаге алгоритма возьмём с доски один узел, составим все возможные узлы с его участием, и добавим на доску ещё и их. Если на доске появился S для всего текста целиком, значит разбор удался; если все узлы с доски обработаны, но S там так и не появился — значит, разбор не удался. Википедия в качестве примера разбирает предложение «She eats the fish with a fork.» по следующей грамматике:

S → NP VP VP → VP PP | V NP | V PP → P NP NP → Det N | she V → eats P → with N → fish | fork Det → a | the

Какова сложность CYK для CFG? На доске может быть как максимум  узлов — для каждого нетерминального символа и для каждой подстроки входного текста; поэтому доску удобно хранить в виде трёхмерного массива, индексы которого — нетерминал, начало подстроки и конец подстроки. На каждом шаге обрабатывается один узел с доски — значит, для разбора потребуются  шагов. На каждом шаге проверяются все правила грамматики, и для каждого правила, где обрабатываемый узел подходит под правую часть, будут проверены все узлы с доски, могущие участвовать в правой части вместе с обрабатываемым узлом. Осталось определить сложность такого шага.

Исходный алгоритм CYK работал с CFG в нормальной форме Хомского (CNF) — в правой части каждого правила вывода допускались либо один терминал, либо два нетерминала. Для правила A → BC «все узлы с доски, могущие участвовать в правой части вместе с обрабатываемым узлом» — это как максимум  узлов с индексами (C, end_B, ?) и/или как максимум  узлов с индексами (B, ?, start_C). (Если B=C, то подходят оба набора вариантов.) Получается, что сложность одного шага CYK для CNF — это , а сложность всего разбора — это .

А если CFG не в CNF? Для правила A → BCD придётся обработать:

• как максимум  узлов с индексами (C, end_B, ?), и для каждого из них — как максимум  узлов с индексами (D, end_C, ?);

• как максимум  пар узлов с индексами (B, ?, start_C), и (D, end_C, ?);

• как максимум  узлов с индексами (C, ?, start_D), и для каждого из них — как максимум  узлов с индексами (B, ?, start_C).

Значит, если в правой части правила вывода допустить до трёх нетерминалов, то сложность одного шага CYK будет , а сложность всего разбора будет . Обобщая на произвольную CFG — видим, что сложность разбора при помощи CYK будет , где  — максимальная длина правой части правил вывода («ранг грамматики»).

Теперь обобщим CYK для MCFG, сохраняя его центральную идею: на каждом шаге алгоритма берём с доски один узел, составляем все возможные узлы с его участием, и добавляем их на доску. Разбор «Я тебя детям просил помочь!» по грамматике, приведённой в ч.1 и для удобства повторённой здесь, получится таким:

VP(X,Y) ← NP(X),V(Y) CP(X,Y) ← VP(X,Y) VP(X,YZW) ← NP(X),V(Z),CP(Y,W) S(XYZ) ← NP(X),VP(Y,Z) NP(я) ← ε NP(тебя) ← ε NP(детям) ← ε V(просил) ← ε V(помочь) ← ε

Как реализовать такой разбор, и какой получится его сложность? Трёхмерной доской уже не обойтись: узлы двухместных предикатов, таких как VP и CP, могут существовать для любой пары подстрок входного текста, так что понадобится индексация пятёрками (нетерминал, начало₁, конец₁, начало₂, конец₂). Одно уже это повышает число шагов разбора до . Теперь надо понять, какие узлы такой пятимерной доски могут участвовать вместе с обрабатываемым узлом в применении правила вывода — например, правила P(XY,ZW) ← P(X,Z),P(Y,W) из приведённой в ч.1 грамматики языка дважды повторённых строк. Подходящие узлы будут находиться по индексам (P, end_X, ?, end_Z, ?) и (P, ?, start_Y, ?, start_W), так что их будет штук. В предположении, что «размерность грамматики» равна 2 (т.е. предикаты как максимум двухместные) и её ранг тоже равен 2 (т.е. правила вывода допускают конкатенацию как максимум двух переменных) — получаем, что сложность CYK-разбора будет .

А если ранг выше, как в вышеприведённой грамматике, где правило VP(X,YZW) ← NP(X),V(Z),CP(Y,W) включает конкатенацию трёх переменных? В этом случае подходящие для V узлы будут находиться по индексам (CP, ?, start_Z, end_Z, ?) и (NP, ?, ?, ∅, ∅), так что их будет уже штук. Аналогично, подходящие для NP узлы будут находиться по индексам (CP, ?, ?, ?, ?) и (V, end_Y, start_W, ∅, ∅), и их тоже будет штук. Получаются шагов сложностью каждый. Огромное число бесполезных шагов заметно и в приведённом примере разбора: в предложении, где три NP и два V, из каждой их попарной комбинации выводится по узлу VP и CP.

В целом можно видеть, что алгоритм разбора остаётся полиномиальным, но показатель степени быстро растёт по мере усложнения грамматики: обобщая приведённые рассуждения, получим сложность , где  — размерность грамматики. Это значит, что разбор можно существенно упростить, заменяя конкатенацию более чем двух переменных на новый нетерминал, например правило VP(X,YZW) ← NP(X),V(Z),CP(Y,W) на пару правил CP'(Y,ZW) ← V(Z),CP(Y,W); VP(X,YZ) ← NP(X),CP'(Y,Z). Полученное таким образом дерево разбора дальше от теоретического описания структуры предложения, но тем не менее, такая «нормализация» грамматик широко применяется.

Как отмечалось в ч.1, тексты на естественных языках часто допускают несколько возможных разборов, и среди этих возможных разборов требуется выбрать наиболее вероятный. Самое лобовое решение — это присвоить каждому правилу вывода вероятность (например, VP(X,Y) ← 75% NP(X),V(Y); VP(X,YZW) ← 25% NP(X),V(Z),CP(Y,W) — такую вероятностную грамматику называют PMCFG), и тогда вероятность разбора — это произведение вероятностей всех использованных в нём правил вывода. Намного удобнее, чем с микроскопическими вероятностями, работать с их логарифмами: тогда перемножение вероятностей заменяется сложением их логарифмов.

В заключение поделюсь моей реализацией CYK для PMCFG на Python, практически применимой (требовалось разбирать предложения до 10 слов в пределах 5 секунд) для , но способной работать и вне этих ограничений. Вместо -мерного массива для доски я использую двухуровневый dict, в котором ключи первого уровня — нетерминалы, второго — объекты Chunk, а значения — логарифмы вероятностей. Для каждой комбинации из нетерминала и набора подстрок может существовать только один экземпляр Chunk, так что для сравнения объектов достаточно сравнить их id — это многократно ускоряет поиск в dict по сравнению с использованием в качестве ключа обычной записи (data class).

class Chunk:     instances = {}     def __new__(cls, symbol, inputs):         key = symbol, tuple(inputs)         i = cls.instances.get(key)         if i:            return i         i = super(Chunk, cls).__new__(cls)         i.symbol = symbol         i.inputs = inputs         cls.instances[key] = i         return i   def parse(grammar, string):     chart = {n: {} for n in grammar.non_terminals}     agenda = {Chunk(rule.left.symbol, [(i, i + 1)]): rule.prob               for i in range(len(string)) for rule in grammar.rules               if rule.terminating and rule.left.inputs[0] == string[i]}     goal = Chunk(grammar.start, [(0, len(string))])     while agenda and goal not in chart[grammar.start]:         (best, prob) = max(agenda.items(), key=lambda x: x[1])         chart[best.symbol][best] = prob         del agenda[best]         for rule in grammar.rules:             if not rule.terminating and any(best.symbol == prod.symbol for prod in rule.right):                 right = list(rule.right)                 for perm in itertools.product(*(chart[prod.symbol].keys() for prod in right)):                     if best in perm:                         sat = satisfies(perm, rule.left, right, chart)                         if sat is not None:                             chunk = sat[0]                             new_prob = sat[1] + rule.prob                             if (chunk not in chart[chunk.symbol]) and \                                ((chunk not in agenda) or (agenda[chunk] != new_prob)):                                 agenda[chunk] = new_prob     return chart[grammar.start].get(goal)   def satisfies(perm, left, right, chart):     mapping = {}     prob = 0     for chunk, pred in zip(perm, right):         for c_i, p_i in zip(chunk.inputs, pred.inputs):             mapping[p_i] = c_i         prob += chart[chunk.symbol][chunk]     inputs = []     for r in left.inputs:         if len(r) == 1:             inputs.append(mapping[r])         else:             mapped = [mapping[c] for c in r]             for k in range(len(mapped) - 1):                 if mapped[k][1] != mapped[k + 1][0]:                     return None             inputs.append((mapped[0][0], mapped[-1][1]))     if len(inputs) > 1:         for i in range(len(inputs) - 1):             if inputs[i][1] > inputs[i + 1][0]:                 return None     return Chunk(left.symbol, inputs), prob 

Самые внимательные заметят, что эта реализация допускает терминалы только в правилах вида N(t) ← ε, по аналогии с CNF. Это отчасти дань традиции, предписывающей категоризовать каждое слово перед составлением синтаксических конструкций с его участием.

Облачные серверы от Маклауд быстрые и безопасные.

Зарегистрируйтесь по ссылке выше и получите 10% скидку на первый месяц аренды сервера любой конфигурации!