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

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

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

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

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

S  NP VPVP  VP PP | V NP | VPP  P NPNP  Det N | sheV  eatsP  withN  fish | forkDet  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 idef 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% скидку на первый месяц аренды сервера любой конфигурации!