32
Синтаксический анализ – самая сложная часть анализа текста. Здесь
необходимо определить роли слов и их связи между собой. Результатом этого
этапа является набор деревьев, показывающих такие связи. Выполнение
задачи осложняется огромным количеством альтернативных вариантов,
возникающих в ходе разбора, связанных как с многозначностью входных
данных (одна и та же словоформа может быть получена от различных
нормальных форм), так и неоднозначностью самих правил разбора.
Постсинтасический анализ служит двум целям. С одной стороны нам
необходимо уточнить смысл, заложенный в слова и выраженный при помощи
различных средств языка: предлогов, префиксов или аффиксов, создающих ту
или иную словоформу. С другой стороны, одна и та же мысль может быть
выражена различными конструкциями языка. В случае с многоязыковой
диалоговой системой, одну и ту же мысль можно выразить различными
синтаксическими конструкциями. В связи с этим дерево необходимо
нормализовать, т.е. конструкция, выражающая некоторое действие различным
образом для различных языков или ситуаций, должна быть сведена к одному
и тому же нормализованному дереву. Кроме того, на этом же этапе может
проводиться обработка разрывных изменяемых словосочетаний, в которых
слова словосочетания могут изменяться и могут быть разделены другими
словами («белый офицер» vs «белый корниловский офицер»).
Семантический анализ проводит анализ текста «по смыслу». С одной
стороны, семантический анализ уточняет связи, которые не смог уточнить
постсинтаксический анализ, так как многие роли выражаются не только при
помощи средств языка, но и с учетом значения слова. С другой стороны,
семантический анализ позволяет отфильтровать некоторые значения слов или
даже целые варианты разбора как «семантически несвязные».
Этапом семантического анализа заканчивается анализ входного текста.
Последующие этапы требуются для генерации отклика, например, в ходе
диалога с пользователем или при переводе документов с иностранного языка
33
для их дальнейшей обработки аналитиком. Сам отклик может, например,
выбираться из некоторого корпуса текстов или генерироваться «на лету». В
случае генерации ответа необходимо провести следующие этапы синтеза:
Генерация внутреннего представления отклика. Прежде, чем давать
какой-либо отклик, диалоговая система должна сформулировать ответ. Для
этого ей, например, может потребоваться собрать и проанализировать какую-
то информацию. Отклик системы будет зависеть от состояния диалога и
других параметров. После этого необходимо определить форму ответа (или
вопроса), подставить в него конкретные слова и значения и лишь затем
приступать к синтаксическому синтезу текста отклика.
Предсинтаксический синтез. Задачи данного этапа прямо
противоположны задачам постсинтаксического анализа. Здесь мы обязаны
вернуть в предложение языкозависимые конструкции, пытаясь раскрыть роль
слов средствами языка. В зависимости от контекста необходимо выбрать ту
или иную форму выражения роли слов и основных идей предложения,
расшифровать словосочетания, развернуть нормализованное дерево.
Синтаксический синтез превращает дерево предложения в линейный
порядок слов. При этом осуществляется согласование параметров слов между
собой.
Предморфологический синтез разъединяет слова, объединенные в целях
экономии смысла в единую лексическую единицу. Здесь же может
осуществляться обратная задача: слияния отдельных слов в одно, если того
требуют правила языка. Морфологический синтез по нормальной форме слова
и его параметрам находит соответствующую словоформу.
Графематический синтез объединяет слова в единый текст, следит за
соответствием фрагментов входного текста фрагментам выходного. На этом
синтез отклика заканчивается.
Генерация отклика в разной мере присуща всем видам диалоговых
систем, некоторым видам систем составления рефератов текста,
34
статистического анализа текста, генерации текстов. Вопросно-ответные
системы могут генерировать отклик как результат обработки запроса
пользователя, системы общения обязаны делать это по определению,
исполнительные системы могут комментировать происходящее или
генерировать ответ на запрос пользователя. Но действия систем не
ограничиваются только генерацией ответов. Вопросно-ответные системы
должны сконвертировать запрос пользователя в какой-либо запрос на
формальном языке (например, SQL при поиске в базе данных) и на основании
полученных результатов решить, какой вид ответа необходимо выбрать.
Исполнительная система должна определить алгоритм выполнения запроса
пользователя и реализовать его.
2.2. Синтаксически анализ.
Синтаксический анализ занимает одно из важнейших мест в цепочке
обработки текстов на естественном языке (ЕЯ) во многих программных
приложениях. Он применяется в информационно-поисковых и
информационно- аналитических системах, в системах машинного перевода и
извлечения информации из текстов. На сегодняшний день синтаксический
анализ является одной из самых актуальных и активно исследуемых проблем
компьютерной лингвистики.
В области обработки текстов на естественном языке, как и в
информатике в целом, под синтаксическим анализом понимается
сопоставление лексем некоторого языка (естественного или формального) с
его формальной грамматикой. Единицей синтаксического анализа текстов на
ЕЯ обычно является предложение.
С одной стороны, синтаксический анализ – это решение задачи
распознавания. Он определяет, является ли предложение грамматически
верным с точки зрения общепринятых правил построения фраз в некотором
ЕЯ. Например, в английском языке артикль ставится перед определяемым
словом, в русском языке определяемое и определитель должны быть
35
согласованы в роде, числе и падеже. Это востребовано в системах
автоматической проверки качества текстов в текстовых редакторах.
С другой стороны, что более важно, в задаче понимания текста машиной
синтаксический анализ – это построение определенной структуры, которая
позволяет приблизиться к некоторому эксплицитному формализованному
представлению смысла текста. Но, в отличие от «глубокой» семантической
структуры, которая строится в результате семантического анализа,
синтаксическая структура обычно не связывает ЕЯ-конструкции с их
значениями в некоторой предметной области. Синтаксическая структура
может выступать либо как промежуточный результат, который является
входом для семантического анализа, либо как удобное представление текста
на ЕЯ для решения высокоуровневых прикладных задач, например, в
информационно-аналитических системах или системах машинного перевода
[8, 9].
Большинство моделей синтаксической структуры предложения ЕЯ
опираются либо на грамматику составляющих, предложенной в работах
Ноама Хомского [10], либо на грамматику зависимостей, для которой
основополагающими считаются работы Люсьена Тенье
ра [11] и Игоря
Мельчука [12].
На начальном этапе исследований в области компьютерной лингвистики
большее внимание уделялось грамматике составляющих. Эта модель
предполагает, что предложение ЕЯ может быть представлено в виде иерархии
составляющих – проективных синтаксических групп, которые не могут
частично пересекаться, но которые в свою очередь состоят из более мелких
групп (быть вложенными), вплоть до атомарных групп – слов предложения.
Такую иерархическую структуру называют деревом составляющих.
Идея о том, что слова в предложении ЕЯ группируются в составляющие,
основывается на лингвистическом наблюдении того, что цепочки слов в
предложении могут функционировать как единое целое и подчиняются
36
единым грамматическим правилам. Составляющие можно перенести в
середину или в конец предложения целиком, но частично их перенести без
потери смысла нельзя.
Грамматика составляющих в иерархии Хомского – это контекстно
свободная (КС) грамматика. Исследователи в целом согласны с тем, что
естественные языки не являются регулярными, например, в работах [10, 13,
14] показывается, что английский язык не может быть распознан регулярными
грамматиками. Исследователи также пришли к выводу, что существуют
языки, содержащие конструкции, которые могут быть распознаны только с
помощью контекстно зависимых грамматик. Например, в работах [15, 16]
показывается, что в швейцарском немецком существуют конструкции,
которые не распознаются КС-грамматиками. Тем не менее, хотя естественные
языки могут выходить за рамки класса контекстно-свободных языков,
моделирование синтаксических правил с помощью КС-грамматик дает
хорошее приближение к реальности и позволяет решать большинство
прикладных задач. Грамматика зависимостей предполагает, что предложения
текста можно структурировать в виде деревьев зависимостей, в которых слова
связаны ориентированными дугами, обозначающими синтаксическое
подчинение между главным и зависимым словом [17, 12, 18] Главное отличие
синтаксических деревьев зависимостей от деревьев составляющих в том, что
здесь отсутствуют нетерминальные вершины, обозначающие составляющие, а
синтаксические связи имеют пометки, которые обозначает их тип. Типы
связей определяют грамматические функции слов в предложении или общие
семантические отношения между словами. Существующие грамматические
теории зависимостей могут расходиться в том, по каким правилам
устанавливаются связи, какие слова в этих связях являются управляющими, а
какие зависимыми, а также какие существуют типы синтаксических связей.
Можно привести множество традиционно спорных случаев. Например, в
одних теориях считается, что предлог управляет словом, к которому он
37
относится, в других теориях делается обратное предположение. Тем не менее,
существует ряд общих принципов, которые обосновывают наличие
синтаксической зависимости между словами в выражении на ЕЯ. В [20]
оаким Нивре приводит некоторые из них:
Управляющее слово определяет синтаксическую категорию выражения
и часто может его заменить.
Управляющее слово определяет семантическую категорию выражения,
зависимое уточняет семантическую характеристику.
Управляющее слово – обязательное, подчиненное – может быть
необязательным.
Управляющее слово выбирает зависимое и определяет, является ли оно
обязательным.
Форма зависимого слова согласуется с формой управляющего.
Позиция зависимого слова зависит от управляющего. Выбор деревьев
зависимостей или деревьев составляющих для описания синтаксической
структуры предложений ЕЯ связывают с двумя свойствами языков:
проективностью их синтаксических конструкций и наличием свободного
порядка слов. Свойство проективности в терминах синтаксического дерева
зависимостей говорит о следующем: если все стрелки зависимостей
проведены по одну сторону от прямой, на которой записано предложение, то
ни одна из стрелок не пересекает никакую другую стрелку, а также никакая
стрелка не накрывает корневой узел [21, 22]. В терминах деревьев
составляющих проективность означает, что составляющие не могут
разрываться на несколько отдельных, несмежных частей. Грамматики
составляющих широко применяются для анализа языков с фиксированным
порядком слов, в которых мало конструкций, нарушающих свойство
проективности, так как в грамматиках составляющих обычно не
предусмотрены непроективные синтаксические отношения между словами.
Например, такими языками являются английский, немецкий, турецкий.
38
Считается, что грамматики зависимостей хорошо отражают специфику языков
со свободным порядком слов, в которых между словами может присутствовать
значительное количество непроективных связей. К таким
языкам, относятся немецкий, чешский, русский, а также другие
восточнославянские языки.
Наличие свободного порядка слов в ЕЯ также влияет на трудоемкость
его описания с помощью разных формализмов. Для анализа конструкций в
языках со свободным порядком слов в грамматиках составляющих может
потребоваться большое количество правил отдельно для каждого возможного
случая расстановки слов [23], когда как правила грамматики зависимостей
зачастую абстрагируются от порядка слов.
2.2.1. Методы построения синтаксических деревьев составляющих.
Поскольку естественные языки с достаточной степенью общности
можно приблизить контекстно-свободными языками, для их синтаксического
анализа могут применяться контекстно-свободные грамматики и
соответствующие алгоритмы для их распознавания. Однако от формальных
КС-языков, таких как языки программирования, которые обычно могут быть
эффективно проанализированы за линейное время от длины входной строки,
естественные языки отличаются высокой неоднозначностью [23].
Неоднозначность может возникать на всех уровнях обработки текстов на ЕЯ.
На этапе морфологического анализа может возникать несколько вариантов
разбора слов, которые обладают различными морфологическими
характеристиками (лексическая, частеречная, падежная омонимия, и др.). КС-
грамматики ЕЯ обычно содержат большое число недетерминированных
правил, что при разборе с помощью классических алгоритмов приводит к
большому числу возвратов и, как следствие, к чрезвычайно низкой
вычислительной эффективности анализа. Помимо этого, грамматики ЕЯ
обычно допускают несколько возможных вариантов разбора, т.е. допускают
синтаксическую (или структурную) омонимию. Часто этот тип омонимии не
39
может быть разрешен только лишь за счет лингвистических соображений и
для определения подходящего разбора требует знаний о семантике слов и
конструкций. Заметим, что нередки случаи, когда несколько вариантов
синтаксического разбора правильны и с точки зрения семантики.
Чтобы разрешить омонимию в подобных случаях требуются знания о
прагматике текста или об его экстралингвистическом контексте [24]. В
отсутствие знаний о семантике и прагматике текста синтаксический
анализатор должен либо выдавать все возможные варианты разбора, либо
стремиться найти лучший вариант в соответствии с некоторым критерием,
опирающимся на уже построенные морфологические или синтаксические
структуры предложения. Таким образом, неоднозначность ЕЯ делает
классические алгоритмы разбора по КС-грамматикам неприменимыми.
Чтобы справиться с такими двумя проблемами, возникающими при
анализе текстов на ЕЯ с помощью КС-грамматик как большое количество
возвратов и необходимость сохранять несколько вариантов разбора,
исследователи предложили ряд алгоритмов, использующих принципы
динамического программирования. Основная идея применения
динамического программирования при анализе с помощью КС-грамматик
заключается в компактном хранении всех построенных в ходе разбора
поддеревьев, чтобы при возникновении возврата не было необходимости
заново воссоздавать когда-то уже построенные поддеревья.
Один из наиболее простых алгоритмов синтаксического анализа,
использующих принципы динамического программирования – это алгоритм
Кокка – Янгера – Касами (Cocke – Younger – Kasami, сокр. CYK, также
встречается название CKY) [25, 26]. Для его работы необходимо
преобразовать грамматику в нормальную форму Хомского, в которой все
правила в правой части имеют либо терминал, либо пару нетерминалов. Эта
форма позволяет при разборе использовать верхнетреугольную таблицу для
хранения всех распознанных нетерминалов (синтаксических групп). Каждая
40
ячейка [i, j] обозначает составляющую, которая включает в себя токены с i-ой
позиции по j- ую, в ней хранятся все распознанные нетерминалы этой
составляющей. Распознавание нетерминалов в ячейке [i, j] осуществляется
путем сопоставления нетерминалов из ячеек левее и ячеек ниже заданной с
правилами грамматики. Алгоритм проводит разбор снизу-вверх, заполняя
сначала левые и нижние ячейки. Предложение считается распознанным, если
в правую верхнюю ячейку удалось занести нетерминал S, обозначающий
предложение. Недостатком оригинального алгоритма CYK является то, что он
работает только с КС- грамматиками, приведенными к нормальной форме
Хомского. Поэтому, чтобы получить дерево составляющих в терминах
исходной грамматики необходимо обратное преобразование, на что требуются
дополнительные вычислительные затраты и затраты памяти.
Еще один алгоритм, использующий принципы динамического
программирования, был предложен Джеем Эрли [27]. Этот алгоритм
выполняет разбор сверху-вниз. Для хранения промежуточного дерева
алгоритм использует таблицу состояний. Под состоянием понимается
«правило с точкой», т.е. правило, в правой части которого отмечено на сколько
оно выполнено в заданной позиции в тексте. Алгоритм последовательно
просматривает предложение и заполняет таблицу состояний слева направо.
Разбор начинается с добавления в левую ячейку таблицы правила, в левой
части которого находится нетерминал S. Затем алгоритм в зависимости от
текущих состояний и текущего слова выполняет действия: предсказание,
сканирования, выполнение. Разбор считается выполненным, если в последней
записи таблицы присутствует правило, в левой части которого находится
нетерминал S.
Мартин Кей обобщил два вышеупомянутых подхода, представив схему
построения эффективных алгоритмов разбора по КС-грамматикам – «chart
parser» [28]. В этой схеме он предложил хранить частично построенные
деревья в виде графа, а также ввел понятие стратегии. Изменяя стратегию,
41
можно построить алгоритм разбора снизу-вверх типа CYK или сверху-вниз
типа Эрли, или же реализовать более сложную стратегию, которая, например,
на основе ряда эвристик могла бы выбирать следующее действие, меняя
направление разбора. Алгоритмы CYK, Эрли и другие разновидности «chart
parser» в худшем случае обладают сложностью O(n
3
), где n – количество слов
в предложении.
Принципиально другой подход для разбора по неоднозначным
грамматикам был предложен в обобщенном восходящим магазинном
анализаторе (Generalized Left-to-right Rightmost, сокр. GLR) Масару Томита
[29]. Анализатор работает по схожим принципам, что и LR (left rightmost)
анализаторы типа перенос-свертка, которые предназначены для разбора по
детерминированным грамматикам. Но, чтобы эффективно обрабатывать
неоднозначности в грамматике, в анализаторе GLR предусмотрена
возможность эффективного разветвления стека. Как и в других рассмотренных
анализаторах наличие разветвления в соответствии с принципами
динамического программирования не приводит к дублированию информации
на стеке за счет его представления в виде графа. Хотя в худшем случае
сложность алгоритма GLR такая же, как и у разновидностей «chart parser» –
O(n
3
), сложность распознавания у GLR зависит от степени
недетерминированности грамматики. В случае, если грамматика
детерминированная, сложность алгоритма – O(n). Это выгодно отличает его от
других рассмотренных алгоритмов.
Создание КС-грамматик для разбора ЕЯ языков является очень
трудоемкой задачей. Для применения в реальных прикладных задачах
грамматики должны содержать тысячи правил. Поддерживать и отлаживать
эти грамматики весьма сложно. Еще одним принципиальным недостатком
разбора с помощью вручную составленных КС-грамматик является тот факт,
что несколько разборов могут быть верными с грамматической точки зрения,