Грамматический разбор для естественных языков. Ч.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
Шаг | Необработанные узлы на доске | Обработанные узлы на доске | Добавляемые на доску узлы |
1 | SheNP, eatsV, theDet, fishN, withP, aDet, forkN | ||
2 | SheNP, eatsV, theDet, fishN, withP, aDet, forkN | ||
3 | eatsV, theDet, fishN, withP, aDet, forkN | SheNP | eatsVP |
4 | theDet, fishN, withP, aDet, forkN, eatsVP | SheNP, eatsV | [the fish]NP |
5, 6 | fishN, withP, aDet, forkN, eatsVP, [the fish]NP | SheNP, eatsV, theDet | |
7 | aDet, forkN, eatsVP, [the fish]NP | SheNP, eatsV, theDet, fishN, withP | [a fork]NP |
8 | forkN, eatsVP, [the fish]NP, [a fork]NP | SheNP, eatsV, theDet, fishN, withP, aDet | |
9 | eatsVP, [the fish]NP, [a fork]NP | SheNP, eatsV, theDet, fishN, withP, aDet, forkN | [She eats]S |
10 | [the fish]NP, [a fork]NP, [She eats]S | SheNP, eatsV, theDet, fishN, withP, aDet, forkN, eatsVP | [eats the fish]VP |
11 | [a fork]NP, [She eats]S, [eats the fish]VP | SheNP, eatsV, theDet, fishN, withP, aDet, forkN, eatsVP, [the fish]NP | [with a fork]PP |
12 | [She eats]S, [eats the fish]VP, [with a fork]PP | SheNP, eatsV, theDet, fishN, withP, aDet, forkN, eatsVP, [the fish]NP, [a fork]NP | [She eats the fish]S |
13 | [eats the fish]VP, [with a fork]PP, [She eats the fish]S | SheNP, eatsV, theDet, fishN, withP, aDet, forkN, eatsVP, [the fish]NP, [a fork]NP, [She eats]S | [eats the fish with a fork]VP |
14, 15 | [with a fork]PP, [She eats the fish]S, [eats the fish with a fork]VP | SheNP, eatsV, theDet, fishN, withP, aDet, forkN, eatsVP, [the fish]NP, [a fork]NP, [She eats]S, [eats the fish with a fork]VP | |
16 | [eats the fish with a fork]VP | SheNP, eatsV, theDet, fishN, withP, aDet, forkN, eatsVP, [the fish]NP, [a fork]NP, [She eats]S, [eats the fish with a fork]VP, [with a fork]PP, [She eats the fish]S | [She eats the fish with a fork]S |
Какова сложность CYK для CFG? На доске может быть как максимум
Исходный алгоритм CYK работал с CFG в нормальной форме Хомского (CNF) — в правой части каждого правила вывода допускались либо один терминал, либо два нетерминала. Для правила A → BC
"все узлы с доски, могущие участвовать в правой части вместе с обрабатываемым узлом" — это как максимум
А если CFG не в CNF? Для правила A → BCD
придётся обработать:
как максимум
узлов с индексами (C, endB, ?), и для каждого из них — как максимум узлов с индексами (D, endC, ?); как максимум
пар узлов с индексами (B, ?, startC), и (D, endC, ?); как максимум
узлов с индексами (C, ?, startD), и для каждого из них — как максимум узлов с индексами (B, ?, startC).
Значит, если в правой части правила вывода допустить до трёх нетерминалов, то сложность одного шага 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(помочь) ← ε
Шаг | Необработанные узлы | Обработанные узлы | Добавляемые узлы |
1 | ЯNP, тебяNP, детямNP, просилV, помочьV | ||
2—4 | ЯNP, тебяNP, детямNP, просилV, помочьV | ||
5 | просилV, помочьV | ЯNP, тебяNP, детямNP | (Я, просил)VP, (тебя, просил)VP, (детям, просил)VP |
6 | помочьV, (Я, просил)VP, (тебя, просил)VP, (детям, просил)VP | ЯNP, тебяNP, детямNP, просилV | (Я, помочь)VP, (тебя, помочь)VP, (детям, помочь)VP |
7, 8 | (Я, просил)VP, (тебя, просил)VP, (детям, просил)VP, (Я, помочь)VP, (тебя, помочь)VP, (детям, помочь)VP | ЯNP, тебяNP, детямNP, просилV, помочьV | (Я, просил)СP, (тебя, просил)СP |
9 | (детям, просил)VP, (Я, помочь)VP, (тебя, помочь)VP, (детям, помочь)VP, (Я, просил)СP, (тебя, просил)СP | ЯNP, тебяNP, детямNP, просилV, помочьV, (Я, просил)VP, (тебя, просил)VP | [тебя детям просил]S, (детям, просил)СP |
10—12 | (Я, помочь)VP, (тебя, помочь)VP, (детям, помочь)VP, (Я, просил)СP, (тебя, просил)СP, [тебя детям просил]S, (детям, просил)СP | ЯNP, тебяNP, детямNP, просилV, помочьV, (Я, просил)VP, (тебя, просил)VP, (детям, просил)VP | (Я, помочь)СP, (тебя, помочь)СP, (детям, помочь)CP |
13—18 | (Я, просил)СP, (тебя, просил)СP, [тебя детям просил]S, (детям, просил)СP, (Я, помочь)СP, (тебя, помочь)СP, (детям, помочь)CP | ЯNP, тебяNP, детямNP, просилV, помочьV, (Я, просил)VP, (тебя, просил)VP, (детям, просил)VP, ... | |
19 | (детям, помочь)CP | ЯNP, тебяNP, детямNP, просилV, помочьV, (Я, просил)VP, ... | (тебя, [детям просил помочь])VP |
20 | (тебя, [детям просил помочь])VP | ЯNP, тебяNP, детямNP, просилV, помочьV, (Я, просил)VP, ... | [Я тебя детям просил помочь]S |
Как реализовать такой разбор, и какой получится его сложность? Трёхмерной доской уже не обойтись: узлы двухместных предикатов, таких как VP и CP, могут существовать для любой пары подстрок входного текста, так что понадобится индексация пятёрками (нетерминал, начало1, конец1, начало2, конец2). Одно уже это повышает число шагов разбора до P(XY,ZW) ← P(X,Z),P(Y,W)
из приведённой в ч.1 грамматики языка дважды повторённых строк. Подходящие узлы будут находиться по индексам (P, endX, ?, endZ, ?) и (P, ?, startY, ?, startW), так что их будет
А если ранг выше, как в вышеприведённой грамматике, где правило VP(X,YZW) ← NP(X),V(Z),CP(Y,W)
включает конкатенацию трёх переменных? В этом случае подходящие для V узлы будут находиться по индексам (CP, ?, startZ, endZ, ?) и (NP, ?, ?, ∅, ∅), так что их будет уже
В целом можно видеть, что алгоритм разбора остаётся полиномиальным, но показатель степени быстро растёт по мере усложнения грамматики: обобщая приведённые рассуждения, получим сложность 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% скидку на первый месяц аренды сервера любой конфигурации!