Часть .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
Шаг |
Необработанные узлы на доске |
Обработанные узлы на доске |
Добавляемые на доску узлы |
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
"все узлы с доски, могущие участвовать в
правой части вместе с обрабатываемым узлом" это как
максимумузлов
с индексами (C, endB, ?) и/или как максимумузлов
с индексами (B, ?, startC). (Если B=C, то подходят оба
набора вариантов.) Получается, что сложность одного шага CYK для
CNF это,
а сложность всего разбора это.
А если CFG не в CNF? Для правилаA BCD
придётся
обработать:
-
как максимумузлов с индексами (C, endB, ?), и для каждого из них как максимумузлов с индексами (D, endC, ?);
-
как максимумпар узлов с индексами (B, ?, startC), и (D, endC, ?);
-
как максимумузлов с индексами (C, ?, startD), и для каждого из них как максимумузлов с индексами (B, ?, startC).
Значит, если в правой части правила вывода допустить до трёх нетерминалов, то сложность одного шага 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(помочь)
Шаг |
Необработанные узлы |
Обработанные узлы |
Добавляемые узлы |
1 |
ЯNP, тебяNP, детямNP, просилV, помочьV |
||
24 |
Я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 |
1012 |
(Я, помочь)VP, (тебя, помочь)VP, (детям, помочь)VP, (Я, просил)СP, (тебя, просил)СP, [тебя детям просил]S, (детям, просил)СP |
ЯNP, тебяNP, детямNP, просилV, помочьV, (Я, просил)VP, (тебя, просил)VP, (детям, просил)VP |
(Я, помочь)СP, (тебя, помочь)СP, (детям, помочь)CP |
1318 |
(Я, просил)С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), так что их будет
штук. В предположении, что "размерность грамматики" равна 2 (т.е.
предикаты как максимум двухместные) и её ранг тоже равен 2 (т.е.
правила вывода допускают конкатенацию как максимум двух переменных)
получаем, что сложность CYK-разбора будет
.
А если ранг выше, как в вышеприведённой грамматике, где правило
VP(X,YZW) NP(X),V(Z),CP(Y,W)
включает конкатенацию
трёх переменных? В этом случае подходящие для V узлы будут
находиться по индексам (CP, ?, startZ, endZ,
?) и (NP, ?, ?, , ), так что их будет уже
штук. Аналогично, подходящие для NP узлы будут находиться по
индексам (CP, ?, ?, ?, ?) и (V, endY, startW,
, ), и их тоже будет
штук. Получаются
шагов сложностью
каждый. Огромное число бесполезных шагов заметно и в приведённом
примере разбора: в предложении, где три 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% скидку на первый месяц аренды сервера любой конфигурации!