52
• Стек STACK из частично обработанных токенов, где STACK [i] - это
i+1-й знак от верхней части стека c вершиной в STACK [0].
• Список INPUT из оставшихся входных токенов, где INPUT[i] это i+1
токен из списка с первым токеном INPUT[0].
• Стек CONTEXT из неприкрепленных токенов встречающихся между
токеном вершины стека и следующим входным токеном, с вершиной
CONTEXT[0] ближайшей к STACK[0] (и самой дальней от INPUT[0]).
• Функция HEAD определяющая частично построенные структуры
зависимостей, где HEAD[i] – синтаксическое начало токена (с HEAD[i] = 0
если i ещё не связан с началом)
• Функция DEP обозначающая частично построенные структуры
зависимостей, где DEP[i] – это тип зависимости, связывающий токен i к его
синтаксическому началу (где DEP[i] = ROOT если i ещё не привязан к началу).
• Функция LC определяющая крайний левый починенный токен в
частично построенной структуре зависимостей (с LC[i] = 0 если у i нет
подчиненных токенов слева).
• Функция RC определяющая крайний правый починенный токен в
частично построенной структуре зависимостей (с LC[i] = 0 если у i нет
подчиненных токенов справа).
• Функция LS определяющая следующий левый одноуровневый токен в
частично построенной структуре зависимостей (где LS[i] = 0 если i не имеет
одноуровневых токенов слева).
• Функция RS определяющая следующий правый одноуровневый токен
в частично построенной структуре зависимостей (где LS[i] = 0 если i не имеет
одноуровневых токенов справа).
Алгоритм строит структуры зависимостей инкрементно, обновляя
HEAD и DEP, но он может добавлять только дугу зависимости между
вершиной стека (STACK[0]) и следующим входным токеном (INPUT[0]) в
текущей конфигурации. (Контекстный стек CONTEXT используется только
53
алгоритмами, позволяющими непроективные структуры зависимости, так как
непривязанные токены под дугой зависимости исключаются из проективных
структур зависимостей). MaltParser 0.3 предоставляет два основных алгоритма
анализа, каждый из которых имеет два варианта:
- Алгоритм Нивре - алгоритм линейного времени, ограниченный
проективными структурами зависимостей.
- Алгоритм Ковингтона – алгоритм квадпратичного времени для
неограниченныхструктур зависимостей, который работает, пытаясь связать
каждый последующий токен с каждым предыдущим. В непроективных
модеях, алгоритм использует стек CONTEXT для хранения непривязанных
токенов, встречающихся между STACK[0] и INPUT[0] (слева-направо).
MaltParser использует модели на базе предыстории для прогнозирования
слеудующего действия в детерминистической деривации структур
зависимостей. Это обозначает, что элементы частично построенных структур
зависимостей используются вместе с элементами (размеченной) входной
строки. Точнее, элементы определены в таких терминах как словоформы
(LEX), части речи (POS) или типы зависимостей (DEP) токена определенные
как родственные одному из типов данных STACK, INPUT и CONTEXT,
использующие вспомогательные функции HEAD, LC, RC, LS и RS.
Поэлементная модель будет определена во внешней спецификации с
помощью следующего синтаксиса:
<fspec> ::= <feat>+
<feat> ::= <lfeat>|<nlfeat>
<lfeat> ::= LEX\t<dstruc>\t<off>\t<suff>\n
<nlfeat> ::= (POS|DEP)\t<dstruc>\t<off>\n
<dstruc> ::= (STACK|INPUT|CONTEXT)
<off> ::= <nnint>\t<int>\t<nnint>
\t<int>\t<int>
<suff> ::= <nnint>
54
<int> ::= (...|-2|-1|0|1|2|...)
<nnint> ::= (0|1|2|...)
Пример:
POS STACK 0 0 0 0 0
POS INPUT 1 0 0 0 0
POS INPUT 0 -1 0 0 0
DEP STACK 0 0 1 0 0
DEP STACK 0 0 0 -1 0
Элемент определенный в первой строке – части речи токена,
находящегося наверху стека (TOP). Второй элемент – это часть речи токена
сразу за следующим входным токеном во входном списке (NEXT), в то время
как третий элемент является частью речи токена перед NEXT в оригинальной
входной строке. Четвёртый элемент – тип зависимости начала TOP.
Последний пятый элемент – это тип зависимости самого левого зависимого от
TOP. Используя синтаксический сахар можно скрыть лишние нули и
представить элементы в более понятном виде:
POS STACK
POS INPUT 1
POS INPUT 0 -1
DEP STACK 0 0 1
DEP STACK 0 0 0 -1
Единственное различие между лексическим и нелексическим элементов
состоит в том, что спецификация лексического может содержать восьмую
колонку, обусловленную суффиксом длины n. Приятно считать, что при n = 0,
включается вся словоформа, в ином случае только последние n символов
будут включены в значение модели. Хотя следующий анализ определяет
модель, значение которой является четырехсимвольным суффиксом
словоформы следующего элемента одноуровневого крайнему правому,
зависимого от начала токена сразу под TOP.
55
LEX STACK 1 0 1 1 -1 4
Наконец, стоит отметить, что если какое-либо смещение не определено
в данной конфигурации, модели присваивается нулевое значение.
Хотя поэлементная модель должна быть оптимизирована для каждого
языка и набора данных в отдельности, некоторые элементы будет полезны в
любом из языков, на которых проверялся MaltParser:
• Частеречные элементы TOP и NEXT в радиуме 1-3 токенов.
• Элементы зависимостей для TOP, его крайние левые и крайние правые
зависимые, а также крайние левые зависимые от NEXT.
•.Лексические элементы по крайней мере TOP и NEX, возможно также
начало TOP и один соседний токен.
Объединение элементов приведет к следующему стандартному виду
модели:
POS STACK
POS INPUT
POS INPUT 1
POS INPUT 2
POS INPUT 3
POS STACK 1
DEP STACK
DEP STACK 0 0 0 -1
DEP STACK 0 0 0 1
DEP INPUT 0 0 0 -1
LEX STACK
LEX INPUT
LEX INPUT 1
LEX STACK 0 0 1
MaltParser может работать в двух режимах:
56
• В режиме обучения система принимает на ввод дерево зависимостей и
запускает классификатор для предсказания действий парсера, данных анализа
алгоритма парсинга, поэлементной модели и обучающегося алгоритма.
• В режиме парсера система работает с набором предложений как с
входными данными и строит граф проективной зависимости для каждого
предложения, используя классификатор, запущенный в режиме обучения.
В обоих случаях входящие данные должны быть в режиме Malt-TAB,
который представляет каждый токен как линию, с табуляцией между
словоформой, частеречной частью и (в режиме обучения) началом и типом
зависимости, с пустыми линиями обозначающими границы предложения:
This DT 2 SBJ
is VBZ 0 ROOT
an DT 4 DET
old JJ 4 NMOD
story NN 2 PRD
. . 2 P
So RB 2 PRD
is VBZ 0 ROOT
this DT 2 SBJ
. . 2 P
3.2. Использование AOT для синтаксического анализа.
Цель синтаксического анализа – построение синтаксических групп на
одном морфологическом варианте одной клаузы. Группы строятся с
помощью синтаксических правил ("форматок").
Клауза (фрагмент) – это простое предложение в составе сложного.
Клауза может вкладываться в другую клаузу, в таком случае она станет
подклаузой. С клаузой всегда связан некоторый набор вариантов вершины
клаузы, где вершина клаузы - это некоторый омоним возможного слова
57
данной клаузы. В AOT системе синтаксического анализа подклаузы могут
входить в синтаксические группы наравне с простыми словами.
Морфологический вариант клаузы – это набор юнитов, следующих друг
за другом в данной клаузе. Юнит – это или морфологический омоним одного
слова, или вариант подклаузы данной клаузы. Например, для фразы
Гитара, которую купил Алексей, сломалась
В главной клаузе, совпадающей со всем предложением, есть подклауза
"которую купил Алексей ". Морфологический вариант главной клаузы всегда
будет состоять из четырех юнитов:
1. "Гитара";
2. ", которую купил Алексей ";
3. ",";
4. "сломалась".
Количество морфологических вариантов данной клаузы равно
P
1*
P
2
*...*P
n
, где n – число юнитов, а P
i
– число разных вариантов юнита с
номером i.
Синтаксическая группа определяется следующими параметрами:
1. номер первого и последнего юнита(слова);
2. тип группы (строка);
3. главная подгруппа
4. граммемы группы;
В частном случае группа – один юнит, тогда номер первого и последнего
юнита совпадают, тогда такая группа будет называться атомарной.
Неатомарные группы подчиняются принципу проективности:
Из того, что две группы пересекаются, следует, что одна лежит в другой
(т.е. является ее подотрезком).
Тип групп - это строковая константа (ПРИЛ_СУЩ, ПГ и т.д.). Обычно
одно синтаксическое правило строит один тип групп, но встречаются
58
исключения. Внутреннее устройство группы во многом определяет тип
групп. Например, в группе "ПГ" главная подгруппа – предлог и т.д.
Главная подгруппа – это группа, являющаяся главной в данной группе.
"Главность" – это понятие используемое здесь так же, как в теории HPSG
(Head-Driven Phrase Structure Grammar). К примеру, для ПРИЛ-СУЩ главной
группой будет существительное. Рекурсивно определяется понятие главного
слова группы:
1. Главное слово атомарной группы – само это единственное слово;
2. Главное слово группы - это главное слово главное подгруппы.
Через понятие "главной группы", дается
определение "именной группе": такой, у которой главным словом
является существительное.
Граммемы группы, или т.н. "внешние" граммемы группы, - это
морфологические характеристики, которые должны определять поведение и
сочетаемость группы во "внешнем" для нее мире, т.е. в группах, куда она сама
входит. Внешние граммемы противопоставляются "внутренним" граммемам
группы. "Внутренние" граммемы – это граммемы главного слова
группы. Например, во внешних граммемах группы "Миша и Дима" есть
множественное число, а во внутренних его нет (главная группа однородного
ряда – первая подгруппа, т.е. "Миша"). Например, в группе "два мальчика"
внешние граммемы содержат именительный падеж, а главным словом
является словоформа "мальчика" (без им. падежа).
Синтаксическое правило получает на входе номер слова. От этого слова
правило пытается построить новую группу определенного типа, соблюдая
принцип проективности. На данный момент все правила пытаются объединить
входную группу только с группами, находящимися от нее справа; в нашей
записи правил (см. ниже) входная группа - это первая группа цепочки. Все
правила упорядочены (см. список ниже), поэтому в данной версии
синтаксическая омонимия игнорируется, т.е. строится всегда только один
59
вариант. Классический пример древние стены города наш анализатор
разберет следующим образом: генит_иг( прил_сущ(древние, стены ), города
). Это происходит из-за того, что правило соединения прилагательного,
согласованного с существительным, идет до правила, которое собирает
генитивные цепочки.
Синтаксическое правило оперирует ограниченным числом объектов.
Можно сказать, что они написаны на определенном подъязыке С++.
Основными объектами являются:
1. Уже построенный набор групп, к которому нужно добавить новую
группу.
2. Характеристики отдельных слов – омонимов входного отрезка
текста.
Таким образом, синтаксические правила находятся выше омонимии,
точнее омонимия находится вне этих правил.
Рабочее название синтаксического правила – форматка.
На вход алгоритма подается морфологический вариант клаузы. В
программе задан некоторый порядок применения правил. Этот порядок
соответствует порядку построения групп: от меньших к большим.
Например, сначала надо построить группы МОДИФ-ПРИЛ, а потом ПРИЛ-
СУЩ, чтобы построить структуру на отрезку "очень красивый человек":
ПРИЛ-СУЩ (МОДИФ-ПРИЛ (очень красивый), человек )
Каждое правило применяется к каждому слову входного отрезка слева
направо. Каждое правило для вновь построенной группы указывает ее
главную группу, список граммем (обычно берется из списка граммем главного
слова), тип
Примеры правил:
Построение аналитических форм глагола проводится внутри фрагмента
до построения морфологических вариантов по декартовому произведению.
Аналитическая форма глагола собирается с глаголами "быть' и "стать' (первая
60
компонента) + словоформа (вторая компонента), в которой хотя бы один
омоним Î ПС = {VERB (гл. в личн. форме), ADVERB_PARTICIPLE
(деепричастие), ADJ_SHORT (кр. прил.), PARTICIPLE_SHORT (кр. прич.),
PREDK (предикатив)(кроме "мало" и "много"), COMPARATIVE
(сравнительная степень прил.)}, остальные омонимы удаляются.
В случае инфинитива аналитическая форма глагола линейно занимает
место первой компоненты, иначе место второй компоненты. При построении
формы проверяется согласование (для формы с предикативом первая
компонента должна иметь ср.р.). На гипотезах словоформ клаузы, которые
могут быть второй компонентой аналитической формы глагола, установлен
порядок: первыми рассматриваются словоформы с наименьшим количеством
омонимов, последними всегда рассматриваются гипотезы с сравнительной
степенью прил. При построении аналитической формы с "будем" или "станем"
убираем в этих формах омоним императива.
Запрещается собирать аналитическую форму с инфинитивом
совершенного вида.
Если в лице третьей компоненты мы имеем следующие глаголы
несовершенного вида:
светать, темнеть, холодать, теплеть, смеркаться, - то есть те,
которые могут образовывать безличные предложения, типа "Смеркается.", то
при собирании аналитической формы к нему присоединяется первая
компонента, то есть в примере "утром рано будет светать" свяжется "будет-
светать".
Правила для построения групп с нецелыми числами (цифровой комплекс
(ЦК) - знак препинания – ЦК)
Что: Цепочка: ЦК-знак препинания-ЦК.
Главная группа: первое слово (т.е. первый ЦК).
Тип: Последовательность чисел вперемешку со знаками препинания.
Название СЛОЖ_ЧИСЛ
61
Примеры: 12,2; 123,555.
3.3. Использование ABBYY Compreno для синтаксического
анализа.
Система ABBYY Compreno создана компанией ABBYY 15 лет назад и
не прекращает развиваться. Она представляет собой интеллектуальную
систему анализа текста, основывающуюсь на универсальном дереве понятий,
или USH (Universal Semantic Hierarchy). Это дерево имеет корневыми
элементами некоторые сферы человеческой жизни, которые впоследствии
ветвятся на более конкретные области, а листьями в этом дереве являются
непосредственно слова. Это очень полезная структура для системы
машинного перевода, так как позволяет искать перевод слов, двигаясь по
этому смысловому дереву, которое практически одинаково для любых языков.
В основе платформы Compreno лежит понятие синтаксической
парадигмы, которое является естественным продолжением традиционного
понятия парадигмы в морфологии.. Термин «синтаксическая парадигма» был
использована Кеннет л. Пайк.
Набор категорий и доступных граммем для определенной части речи
состоит из нескольких источников. Во-первых, морфологические категории,
которые
исходят из морфологического словаря (падеж или род прилагательных).
Во-вторых, существуют классификации по категориям лексем; их граммемы
припысываются вручную для некоторых лексем, которые имеют
нетривиальные синтаксические свойства (напр. русские числительные от 2 до
4 обозначены <SmallNumeral>). Они могут рассматриваться как расширение
морфологии. В-третьих, есть классифицирующие категории для классов. В-
четвертых, есть синтаксических категории и специальные категории, такие
как капитализация.