Часть .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, forkNeatsVP

SheNP, eatsV

[the fish]NP

5, 6

fishN, withP, aDet, forkNeatsVP, [the fish]NP

SheNP, eatsV, theDet

7

aDet, forkNeatsVP, [the fish]NP

SheNP, eatsV, theDet, fishN, withP

[a fork]NP

8

forkNeatsVP, [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

SheNPeatsV, theDet, fishN, withP, aDet, forkN, eatsVP

[eats the fish]VP

11

[a fork]NP, [She eats]S, [eats the fish]VP

SheNP, eatsV, theDet, fishNwithP, 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? На доске может быть как максимум |N|\cdot\frac{n\cdot(n+1)}2 узлов — для каждого нетерминального символа и для каждой подстроки входного текста; поэтому доску удобно хранить в виде трёхмерного массива, индексы которого — нетерминал, начало подстроки и конец подстроки. На каждом шаге обрабатывается один узел с доски — значит, для разбора потребуются O(n^2) шагов. На каждом шаге проверяются все правила грамматики, и для каждого правила, где обрабатываемый узел подходит под правую часть, будут проверены все узлы с доски, могущие участвовать в правой части вместе с обрабатываемым узлом. Осталось определить сложность такого шага.

Исходный алгоритм CYK работал с CFG в нормальной форме Хомского (CNF) — в правой части каждого правила вывода допускались либо один терминал, либо два нетерминала. Для правила A > BC "все узлы с доски, могущие участвовать в правой части вместе с обрабатываемым узлом" — это как максимум n узлов с индексами (C, endB, ?) и/или как максимум n узлов с индексами (B, ?, startC). (Если B=C, то подходят оба набора вариантов.) Получается, что сложность одного шага CYK для CNF — это O(n), а сложность всего разбора — это O(n^3).

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

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

  • как максимум n^2 пар узлов с индексами (B, ?, startC), и (D, endC, ?);

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

Значит, если в правой части правила вывода допустить до трёх нетерминалов, то сложность одного шага CYK будет O(n^2), а сложность всего разбора будет O(n^4). Обобщая на произвольную CFG — видим, что сложность разбора при помощи CYK будет O(n^{r+1}), где r — максимальная длина правой части правил вывода ("ранг грамматики").

Теперь обобщим 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). Одно уже это повышает число шагов разбора до O(n^4). Теперь надо понять, какие узлы такой пятимерной доски могут участвовать вместе с обрабатываемым узлом в применении правила вывода — например, правила P(XY,ZW) < P(X,Z),P(Y,W) из приведённой в ч.1 грамматики языка дважды повторённых строк. Подходящие узлы будут находиться по индексам (P, endX, ?, endZ, ?) и (P, ?, startY, ?, startW), так что их будет O(n^2) штук. В предположении, что "размерность грамматики" равна 2 (т.е. предикаты как максимум двухместные) и её ранг тоже равен 2 (т.е. правила вывода допускают конкатенацию как максимум двух переменных) — получаем, что сложность CYK-разбора будет O(n^6).

А если ранг выше, как в вышеприведённой грамматике, где правило VP(X,YZW) < NP(X),V(Z),CP(Y,W) включает конкатенацию трёх переменных? В этом случае подходящие для V узлы будут находиться по индексам (CP, ?, startZ, endZ, ?) и (NP, ?, ?, ?, ?), так что их будет уже O(n^4) штук. Аналогично, подходящие для NP узлы будут находиться по индексам (CP, ?, ?, ?, ?) и (V, endY, startW, ?, ?), и их тоже будетO(n^4) штук. Получаются O(n^4) шагов сложностью O(n^4) каждый. Огромное число бесполезных шагов заметно и в приведённом примере разбора: в предложении, где три NP и два V, из каждой их попарной комбинации выводится по узлу VP и CP.

В целом можно видеть, что алгоритм разбора остаётся полиномиальным, но показатель степени быстро растёт по мере усложнения грамматики: обобщая приведённые рассуждения, получим сложность O(n^{d\cdot(r+1)}), где d — размерность грамматики. Это значит, что разбор можно существенно упростить, заменяя конкатенацию более чем двух переменных на новый нетерминал, например правило 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 секунд) для d\le2,\ r\le4, но способной работать и вне этих ограничений. Вместо 2d+1-мерного массива для доски я использую двухуровневый 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% скидку на первый месяц аренды сервера любой конфигурации!