Содержание к диссертации
Введение
Глава 1. Обзор литературы 6
1.1. Корпусная лингвистика 6
1.2. Синтаксические анализаторы 9
1.3. Лингвистические процессоры интегрального и модульного типа . 11
1.4. Пример развитого синтаксического анализатора. Система Link Grammar Parser 13
1.5. Сетевые грамматики 16
Глава 2. Описание синтаксиса на основе моделей управления. Методика, алгоритмы и программы формирования описания 19
2.1. Модели управления как средство описания естественного языка 19
2.2. Методика построения множества моделей управления 20
2.3. Разработка синтаксического анализатора, основанного на РСП 24
2.4. Управление работой синтаксического анализатора, основанного на РСП .49
2.5. Анализ синтаксических структур фрагментов и выделение из них использованных моделей управления 52
Глава 3. Информационная система для работы с моделями управления 58
3.1. Требования к информационной системе и ее архитектура 58
3.2. Базовая функциональность информационной системы 61
3.3. Структура xrtl-файла. Редактирование моделей управления 61
Глава 4. Синтаксический анализатор на основе моделей управления .66
Глава 5. Примеры работы алгоритмов 79
5.1. Примеры формирования моделей управления 79
5.2. Пример работы синтаксического анализатора на основе моделей управления 96
Заключение 98
Список литературы 99
- Пример развитого синтаксического анализатора. Система Link Grammar Parser
- Разработка синтаксического анализатора, основанного на РСП
- Структура xrtl-файла. Редактирование моделей управления
- Пример работы синтаксического анализатора на основе моделей управления
Введение к работе
Современный мир характеризуется быстрым ростом глобализации и, как следствие, необходимостью общения людей разных культур и разных национальностей, носителей разных языков. И язык является одновременно и основным связующим, и, как это ни парадоксально, основным разделяющим средством. Одним из способов преодоления языкового барьера является использование систем машинного перевода различных типов, компонентами которых являются синтаксические анализаторы.
Другим фактором, определяющим интерес к развитию лингвистических процессоров различного рода, является растущая необходимость упрощения работы с обширными информационными системами (например, такой системой можно считать Интернет в совокупности с поисковыми серверами). В этом случае возникает потребность обеспечения пользователя средством, которое позволит ему максимально удобно формулировать свои запросы. Самым привычным таким средством является естественный язык. В этом случае лингвистический процессор должен уметь преобразовывать запросы на естественном языке в структуры, отражающие семантику, т.е. смысл, и прагматику, т.е. цели запроса.
Синтаксический компонент в составе лингвистического процессора русского языка необходим достаточно широкому кругу систем автоматической обработки текстов на естественном языке. К ним относятся, кроме уже упомянутых систем машинного перевода и информационных систем, системы автоматического синтеза речи (звуковое воспроизведение текста компьютером), распознавания речи (конвертирование компьютером устной речи в письменный текст), системы определения авторства текста и другие. Существующие в настоящее время синтаксические компоненты обладают рядом существенных недостатков: применяемые способы описания языка, как правило, недостаточно точно фиксируют языковые особенности, не допускается использование неграмматичных конструкций, создание и пополнение описания языка требует существенных трудозатрат. В связи с этим является актуальной задачей создание новых способов описания синтаксиса языка и использующих их синтаксических анализаторов, лишенных этих недостатков.
Если рассматривать лингвистические процессоры в аспекте синтаксиса, то наиболее важными, по-видимому, являются следующие вопросы. Во-первых, это
связь синтаксического анализа и анализа на более высоких уровнях. Во-вторых, это выбор способа описания языка, в частности, способ описания синтаксиса. С этими вопросами естественным образом связаны процессы создания и пополнения описания языка и выбор алгоритма анализа.
Сейчас не существует хорошего ответа на эти вопросы. В большинстве систем, ориентированных на глубокое понимание текста, синтаксический компонент в силу ряда причин занимает подчиненное положение, вследствие чего собственно синтаксическая информация, заключенная в тексте, используется далеко не полностью.
Данная работа, посвященная созданию синтаксического компонента лингвистического процессора, предлагает решение этих проблем.
Цели работы
Цель диссертационной работы состоит в разработке новых методов описания синтаксиса языка, позволяющих повысить точность описания по сравнению с традиционными подходами, основанными на использовании различного рода грамматик, а также в создании синтаксического анализатора русского языка, использующего предлагаемые методы и обеспечивающего возможность настройки на стилистические особенности подъязыков.
Поставленная таким образом цель может рассматриваться в рамках более масштабной задачи, а именно задачи создания лингвистического процессора, включающего в себя как синтаксический, так и семантический и прагматический
компоненты.
Научная новизна
Предложен новый метод описания синтаксиса естественного языка, основанный на расширенном и адаптированном понятии модели управления, позволяющий учитывать в рамках одной концепции несколько уровней детализации синтаксической связи слов и обеспечивающий фиксирование стилистических особенностей подъязыков.
Разработана методика автоматического формирования множества моделей управления, обеспечивающая постоянную актуальность описания синтаксиса языка и возможность постоянного пополнения этого описания.
Разработан и реализован адаптивный синтаксический анализатор русского языка на основе моделей управления. Используемый алгоритм анализа позволяет получать все возможные варианты структуры входной фразы, при этом наиболее вероятный вариант возвращается первым, за минимальное время, и далее следуют остальные варианты по убыванию вероятности их использования.
Эти качества позволяют рассчитывать как на широкие перспективы использования предлагаемого решения, так я на дальнейшее развитие в этом направлении (например, добавления семантической информации в обобщенные модели управления; в этом случае можно использовать описываемый синтаксический анализатор для семантического анализа практически без изменений).
Апробация работы
Основные научные выводы и результаты работы представлялись и докладывались на международных конференциях Диалог-2000 (Протвино, 2000 г.), Диалог-2001 (Аксаково, 2001 г.), Диалог-2002 (Протвино, 2002 г.) и Диалог-2003 (Протвино, 2003 г.), а также на научных семинарах МГУ в 1999-2003 гг.
Публикации
По теме диссертации автором опубликованы четыре печатные работы.
Структура и объем диссертации
Диссертация состоит из введения, 5 глав, заключения и списка использованной литературы. Общий объем работы составляет 101 страницу. Список литературы составляет 50 наименований.
Пример развитого синтаксического анализатора. Система Link Grammar Parser
В самом начале работ по анализу естественного языка с помощью вычислительных машин не существовало ни синтаксических теорий, достаточно четких и пригодных для компьютерных реализаций, ни тем более формализованных семантических описаний естественно-языковых структур. Программы разбора представляли собой коллекции "упакованных программ", "помеченных подпрограмм", и т.п., которые постоянно разрастались по мере того, как грамматики расширялись для обработки все более сложных предложений, и вследствие такого усложнения затруднялось их взаимодействие. Далее программы обработки естественного языка развивались по двум основным направлениям, В первом из них использовался процесс сопоставления образцов (pattern matching) для выявления информации, а традиционный синтаксис при этом игнорировался. Второй подход был связан с рассмотрением некоторого ограниченного подмножества естественного языка на основе одного из вариантов контекстно-свободной грамматики. Обзор ранних программ грамматического разбора представлен в [12].
Возникали и развивались многие лингвистические теории, рассматривавшие синтаксис как особый аспект, не связанный с семантикой. Язык трактовался как способ организации цепочек абстрактных символов, а его структура как набор правил манипулирования символами. Основным методом американского структурализма являлся и продолжает оставаться анализ непосредственно составляющих (в Европе в большей степени уделялось внимание грамматикам зависимостей), суть которого состоит в установлении дистрибутивного подобия отдельных языковых единиц, и составляющие рассматриваются как классы эквивалентности. Первой формализацией идеи иерархии составляющих были работы Хомского [13]. С этого момента большая часть генеративистских лингвистических теорий основывалась (пусть даже частично) на контекстно-свободных грамматиках [13, 14], теории управления и связывания [15, 16, 17] и других работах, причем многие из них использовали схематические контекстно-свободные шаблоны, известные как Х-штрих схемы. Вскоре после Хомского контекстно-свободная грамматика была заново открыта Бэкусом, и независимо от него Науром и применена ими для описания языка АЛГОЛ [18]. Решение рассматривать синтаксис на основе трансформационной грамматики Хомского было попыткой некоторых исследователей воспроизвести глубинную структуру предложения, которая затем могла бы быть проанализирована контекстно-свободным базовым компонентом. После ранних работ было создано множество вычислительных моделей обработки естественного языка на основе контекстно-свободных грамматик, поскольку они обеспечивали построение эффективных алгоримов разбора в соответствии с этими грамматиками.
Другим классом грамматических теорий, основывающихся не на контекстно-свободных грамматиках, а на взаимоотношениях между словами, являются грамматики зависимостей [19, 20]; грамматика слов [21], грамматика ограничений [22]. Грамматики зависимостей очень широко применяются в современных статистических системах грамматического разбора, поскольку решающая роль непосредственных отношений между словами становится все более очевидной. В тесной связи с грамматиками зависимостей находится идея разработки обучаемых систем, содержащих глагольные фреймы, учитывающие все возможные аргументы глаголов и их характеристики, включая вероятностные оценки их появления. Одним из таких проектов является система баз данных WordNet [23].
Подобные идеи лежат в основе системы ЯРАП, предназначенной для автоматического (машинного) перевода [24]. Процесс перевода состоит из трех стадий - анализ — межъязыковые операции — синтез; нас в данном случае интересует прежде всего процесс внутриязыкового анализа. Подход выражается принципом словоцентризма [25] в той его трактовке, согласно которой все структурные и другие характеристики предложений и словосочетаний могут быть заданы как свойства словоформ [26]. Лингвистические знания, являющиеся результатом внутриязыкового анализа переводимого текста (в том числе, например, сведения о лексико-синтаксических отношениях в структуре входящих в него словосочетаний), должны быть заданы в конечном итоге в описании отдельных словоформ и распределены в них по составляющим эти словоформы лексико-морфологическим элементам.
Принципиальным теоретическим недостатком такого подхода является, видимо, невозможность адекватного описания языковых конструкций, в которых отсутствует явно выраженная главная словоформа. В этом случае приходится либо искусственно выбирать главное слово в словосочетаниях, либо считать все словосочетание единой лексической единицей. Главной же проблемой применения этого подхода на практике является необходимость формирования огромного количества словарных статей, отражающих все возможные варианты синтаксических отношений для каждого слова.
Одним из центральных вопросов является вопрос о том, каковы задачи и место синтаксического этапа анализа в когнитивной модели в целом, и прежде всего о взаимоотношении синтаксического и более высоких уровней (семантического и прагматического) и вообще о целесообразности разделения этих уровней в модели понимания естественного языка (этот вопрос обсуждался в работах [27], [28], [29], [30], [31], [32], [33], [34], [35]). Существуют два принципиально различных подхода. Один из них предполагает такое устройство системы, при котором каждому уровню лингвистического анализа соответствует отдельный компонент (модуль) системы: морфологический, синтаксический, семантический. Системы модульного типа допускают разные схемы взаимодействия модулей (последовательная работа, параллельный перемежающийся анализ), - это не меняет существа дела: синтаксис и семантика обрабатываются в системе разными механизмами. При этом синтаксический уровень анализа входного текста представлен в системе в явном виде: он выделен в отдельный блок, преобразующий текст в его синтаксическое представление.
Разработка синтаксического анализатора, основанного на РСП
Для адекватного анализа предложений необходимо достаточно мощное средство контроля контекстных условий. Как показывает опыт, проверка совпадения отдельных признаков (рода, числа, падежа, лица и других) недостаточна для отсеивания многих неверных вариантов анализа. Так, например, этим способом мы можем установить, что словосочетание красное знамя правильно, а красного знаменем нет, но в более сложных случаях его явно недостаточно. Поэтому использование операторов языка программирования позволило не ограничивать себя в методах контроля. Формально каждый оператор является функцией, возвращающей значение TRUE или FALSE. Используются операторы двух типов: выполняющиеся после успешной свертки группы, выполняющиеся перед завершением анализа группы. Операторы первого типа имеют три параметра - глобальный и локальный дескрипторы и дескриптор свернутой группы. Глобальный дескриптор при условии удачного анализа текущей группы станет дескриптором свернутой группы на более высоком уровне, а локальный используется аналогично локальным переменным в языках программирования, фактически для хранения промежуточных результатов. Операторы второго типа, как естественно предположить, лишены третьего параметра. Дескриптор можно представлять в виде набора вложенных списков, при этом в каждом списке есть элементы-поля (которые можно создавать и к которым можно обращаться по имени), содержащие либо строки, либо вложенные списки. Описание синтаксиса обращений к дескрипторам содержится в приложении. Описываемая в этой работе грамматика предназначена для анализа предложений русского языка любой степени распространенности и с произвольным (в пределах грамм этичности) порядком слов. В то же время есть языковые конструкции, которые не могут быть разобраны по приводимой здесь грамматике, а именно: неделимые идиомы (Дела как сажа бела), обращения (Ставки сделаны, господа), междометные высказывания (Ну уж это слишком), обороты с союзами как, чем, словно и др. (Он был зеленый, как крокодил), подчинительные конструкции с сочинительными союзами внутри простого предложения (Работа продвигалась медленно, но верно), пояснительные конструкции с запятой и сочинительными союзами (бегемот, или гиппопотам), обособленные уточняющие или поясняющие члены (Рабочие - их было трое - выйти с территории стройплощадки), цитаты и афористические выражения {Действовал по принципу "око за око, зуб за зуб"), частицы (я ни в чем себе не отказывал), однородные сказуемые (По-английски он читал и говорил одинаково хорошо), сложные числительные (две тысячи второй), знаки препинания, отличные от тире, запятой, кавычек и точки, сложные предложения, если их структура отлична от набора простых предложений, связанных сочинительными и подчинительными союзами (при необходимости усовершенствования способа обработки сложных предложений можно воспользоваться результатами [47]) . Заметим, что ограничения эти не носят принципиальный характер, и при возникновении необходимости устранения этих ограничений соответствующие дополнения к грамматике не повлекут за собой изменение уже проделанной работы. Описание расширенной сети переходов состоит из описания подсетей, соответствующих синтаксическим группам. Используются следующие синтаксические группы (для каждой группы приводится ее название, обозначение в РСП, информация о главном слове и пример использования): Инфинитивная группа ($Fnf); главное слово - глагол в неопределенной форме. Пример: смотреть по крайней мере целую неделю. Финитно-глагольная группа ($VP1); главное слово - личная форма т. н. полнозначного глагола. Пример: генерал позабыл распорядиться, Финитно-связочная группа (SVP2); главное слово - личная форма глагола-связки. Пример: был нынешним летом на Норд-Капе. Причастная группа ($Ptl); главное слово - причастие. Пример: уважающий себя. Деепричастная группа ($Pt2); главное слово - деепричастие. Пример: не придерживаясь берлинского произношения. Именная группа ($NP); главное слово - существительное. Пример: настоящий хозяин. Предложная группа ($РР); главное слово - предлог. Пример: на каждую систему ставок. Адвербиальная группа ($Adv); главное слово - наречие. Пример: очень легко. Компаративная группа ($Стр)\ главное слово - например, сравнительная степень прилагательного. Пример: белее снега. Группа категории состояния ($SCP); главное слово - т. н. категория состояния. Пример: совсем невмоготу, Адъективная группа (SAP); главное слово - прилагательное. Пример: как можно скромнее. Простое предложение (55). Пример: Смотрели они, однако, с любопытством. Сложное предложение ($CS). Пример: Как ни эксцентрично было поведение бабушки, но ее триумф покрывал многое. Инфинитивная группа Поскольку группы определяются рекурсивно, друг через друга, невозможно выстроить их в таком порядке, при котором в описании каждой группы использовались бы только описанные ранее группы; к этому можно только стремиться. И естественнее начать описание с инфинитивной группы по следующим причинам. При разборе предложения или фрагмента предложения, если предполагается возможность присутствия в нем финитно-глагольной или финитно-связочной группы (естественно, априори рассматриваются все случаи, тем более настолько распространенные), то большая часть групп, входящих в предложение, включалась в состав именно финитно-глагольной или финитно-связочной группы.
Заметим, что оправданы два альтернативных подхода. Можно считать, что, например, в предложении я поздно пришел домой слово домой (как и поздно) зависит от сказуемого пришел, и это более оправданная точка зрения, а можно рассматривать его как зависящее от финитно-глагольной группы поздно пришел, т. е. как непосредственное составляющее предложения. Чтобы избавиться от избыточного и неоправданного количества вариантов, требовалось выбрать один способ разбора, и был выбран первый. В этом случае все слова, зависящие от сказуемого, разбираются в составе финитно-глагольной или финитно-связочной группы, и описание собствен во предложения должно стать тривиальным (на самом деле это не совсем так, поскольку зависящие слова могут быть отделены в предложении от $VP1 и SVP2 подлежащим, например, домой я пришел поздно, и такие слова считаются зависящими от финитно-глагольной или финитно-связочной групп в целом, поскольку разобрать их в составе этих групп невозможно. Таким образом, все, что может быть разобрано не непосредственно в предложении, разбирается не в нем, а то, что иначе нельзя разобрать, разбирается так же, как и внутри финитно-глагольной или финитно-связочной группы, возможно, с некоторыми обобщениями.
Структура xrtl-файла. Редактирование моделей управления
Эта группа разделена по типу главной части на группу с личным местоимением, $NPPersonalPronoun, группу с "неличным" местоимением, $NPNonPersortalPronoun (эти две группы называются вместе прономинативной), группу с числительным (нумеративную), SNPNumber, и группу с существительным (субстантивную), SNPNoun.
Рассмотрим группу с личным местоимением. Специфика этой группы в том, что зависимые адъективные и причастные группы выделяются запятыми, например, Измученного и несчастного, его ждала работа. Для этих групп допустима как препозиция, так и постпозиция.
Если, например, между двумя адъективными группами нет запятой (как в случае большой каменный), то они считаются неоднородными и разбираются здесь. Если она есть, то это считается однородной адъективной группой и разбирается в $АР.
Операторы ToLocGender, ToLocNumber и ToLocCase используются для проверки идентичности рода, числа и падежа у адъективных и причастных групп и главного слова - личного местоимения. Информацию об этом местоимении получает оператор ToLocNpFromPronoun.
В конце анализа группы работают операторы ToGlobGender, ToGlobNumber, ToGlobCase, ToGlobAnimate и ToGlobPerson, которые копируют информацию о роде, числе, падеже, одушевленности и лице в глобальный дескриптор. Так как одушевленность у личных местоимений не определена, то ее значением становится "Любой" (мужской род для слова "Любой" используется потому, что оно же обозначает произвольное значение для рода, числа, падежа, etc.)
Для группы с "неличным" местоимением допускаются только необособленные (запятыми) адъективные, причастные и предложные группы, например, Ты появишься у двери в чем-то белом без причуд. При этом проверка рода, числа и падежа происходит аналогично. Информация о главном слове также поставляется оператором ToLocNpFromPronoun.
Именная группа с главным словом - числительным может распространятся именной, предложной, адъективной и причастной группами (которые могут стоять и перед, и после числительного) и наречием степени, для которого возможна только препозиция, например, месяца два, двое из группы, каждые три года, потерянные три часа и примерно двадцать соответственно. Для именной и предложной группы в препозиций и предложной в постпозиции проверяется единственность (операторами CheckSingleNp и CheckSinglePp). Определение и контроль соответствия рода, числа и падежа осуществляется аналогично прономинативным группам.
Наиболее распространенной среди именных групп является группа с главным словом - существительным. Во-первых, с ней могут употребляться адъективные и причастные группы (красивый каменный недавно построенный дом), причем как в препозиции, так и в постпозиции. Заметим, что если причастная группа находится в постпозиции, то проверяется (операторами CheckSimplePtJ и CheckComplexPtl), состоит она из нескольких слов (лодка, давно прогнившая) или нет (лодка прогнившая), и в зависимости от этого она выделяется или не выделяется запятыми. Существительные также могут распространяться наречиями (макароны по-флотски), кроме наречий, оканчивающихся на -о, за этим следит оператор CheckNoAdvO. Возможны также т. н. присубстантивные (т. е. при существительном) инфинитивы (например, мастер заливать), но только в постпозиции. Для именных (станция Крюково, газета "Известия", знак почета, долг Иванову, жест рукой) и предложных (бочка с медом) групп наиболее характерна также постпозиция, но допускается расположение и перед главным словом. Именные группы могут быть, как мы видим, в произвольном падеже, кроме винительного (в винительном они могут быть в единственном случае - когда главное слово также находится в этом падеже: императору Николаю Александровичу), что проверяется оператором CheckNonAccusCase.
Оператор ToLocNpFromNoun определяет одушевленность, род, число и падеж существительного, при этом лицо становится третьим. Остальные операторы работают аналогично другим именным группам. Отметим также, что именная группа мажет быть "простой" или состоять из однородных "простых" именных групп. Если она состоит из однородных именных групп, то род этой именной группы будет произвольным, число - множественным (для этого служит оператор DejGenNum). Если одушевленность у однородных групп будет одинаковой, то она станет одушевленностью и всей именной группы, иначе будет произвольной (оператор ToLocWeakAnimate). Это же касается и лица (оператор ToLoc WeakPersori). Предложная группа Эта группа является, видимо, самой простой и состоит из предлога и именной группы. Так как для предлога используется модель управления, то можно считать, что он управляет именной группой. Как отмечается в работе [41], вопрос, является ли предлог главным словом, "синтаксически нерелевантен". Но с практической точки зрения удобнее полагать, что именная группа зависит от предлога, а не наоборот. Модель управления предлога, как отмечалось выше, формально является частным случаем модели управления глагола. Требования для именной группы выглядят так же, как и к дополнению глагола, что позволяет нам использовать те же операторы, что и при разборе финитно-глагольной, финитно-связочной и инфинитивной групп, Например, для предлога в : (А: В о/но (0) П о/но (0) П2 о/но (0)) Соответствующие предложные группы: в машине, в хлебе, в снегу. Заметим, что данное описание этого предлога не претендует на полноту и точность, а используется лишь в качестве примера. Для контроля соответствия именной группы модели управления используются те же операторы, что и в $Inf и др.: ToGlobVerbWord, AddNpInfoForCtrlModel, CheckCtriModel. Характеристикой предложной группы (кроме падежа и одушевленности, за которые отвечают операторы ToLocCase, ToLocAnimaie, ToGlohCase и ToGlobAnimate) является также предлог, копируемый в глобальный дескриптор оператором ToGlobPrep. Адвербиальная группа В состав этой группы могут входить предложные или именные группы, как в препозиции, так и в постпозиции (например, до боли обидно и вниз головой), Наречие степени не может иметь зависимых слов (например, крайне), а наречия на -о (на что оканчивается наречие, определяется операторами CheckWordO и CheckWordNoO) могут распространяться другими наречиями {крайне охотно) и компаративами степени (менее доступно). Для них возможна только препозиция. Если наречие оканчивается на -о, информация об этом заносится в глобальный дескриптор оператором ToGhbWordO, Для однородных групп такие же сведения на более высокий уровень передает оператор ToGlobAdvO, т. к. в качестве главного компонента группы могут выступать однородные адвербиальные группы (например, очень (ровно и красиво)).
Пример работы синтаксического анализатора на основе моделей управления
Если мы достигли самого левого (самого правого) слова при движении влево (вправо), в этом направлении больше не двигаемся. Если можно двигаться в другом направлении, переходим к шагу 4,5.6.1. Если нельзя двигаться больше ни в одном направлении, выходим из цикла с неудачей (т. е. модель управления нельзя применить).
Если текущее слово уже разобрано (поле Parsed), то проверяем, зависит ли это слово (хотя бы косвенно) от нашего главного слова или нет с помощью функции ChecklnderectDependencyO. Если зависимости нет, то останавливаем движение в этом направлении и переходим к шагу 4.5.6.1, поскольку мы исключаем анализ непроективных конструкций. Отметим, что убрав эту проверку, можно без каких либо дополнительных усилий обеспечить анализ непроективных конструкций, и этот факт можно отнести к достоинствам описываемого алгоритма, поскольку он расширяет область его потенциальной применимости.
Если слово не разобрано, проверяем, находится ли оно внутри какой-нибудь группы. Например, в ходе анализа предложения Мама стирала замоченную недавно одежду мы можем оказаться в точке разбора, в которой установлены следующие зависимости: Мама стирала замоченную недавно одежду
Очевидно, слово недавно не может зависеть от слова стирала, поскольку мы исключаем непроективные конструкции, и не следует проверять возможность их объединения с помощью какой-либо модели управления. Это делает функция Checkls WordlnDependentGroupQ.
Если слово находится внутри такой группы, снова переходим к шагу 4.5.6.1. К этому этапу были пройдены все фильтры, отбрасывающие непроективные конструкции, и необходимо проверить, можно ли использовать данную модель управления по отношению к данным главному и зависимому (потенциально) словам. Это делает функция CheckWord. Если нельзя, переходим к шагу 4.5.6.1, иначе завершаем шаг 4.5.6 с результатом -номером установленного зависимого слова. . Если можно использовать указанную модель управления к указанному главному слову и некоторому найденному зависимому слову, то сравниваем оценку этой модели управления н оценку лучшей модели управления из уже найденных (на предыдущих итерациях). Если последняя найденная модель управления имеет более высокую оценку, считаем ее лучшей и запоминаем и ее, и найденное зависимое слово. Переходим (если есть еще модели управления) к шагу 4.5.5. 4.5.8. Проверяем, нашли ли при выполнении шагов 4.5.1 - 4.5.7 наиболее вероятные главное слово, зависимое слово и связывающую их модель управления. Если нашли, то применяем модель управления к этим двум словам и получаем новую точку разбора (функция ApplyQ). Работающий таким образом алгоритм фактически является частным случаем алгоритма поиска по дереву, широко и успешно используемому при решении различных задач, относимых обычно к задачам искусственного интеллекта (напр., [50]). Для решения такого рода задач деревья представляют особый интерес по нескольким причинам. Любой дискретный процесс принятия решений в заданной детерминированной системе может быть представлен в виде дерева. Если корень дерева соответствует начальному состоянию системы, то его дочерние вершины соответствуют состояниям, которые могут быть результатом применения различных операций из числа имеющихся. Далее, для каждой из таких дочерних вершин существует некоторое множество возможных операций, каждая из которых приводит к новому состоянию, представляемому внучатыми вершинами, и т. д. Широкий набор процедур решения проблем (включая методы доказательства теорем) может быть представлен как прохождение по дереву, у которого один или более листьев соответствуют успеху в доказательстве теоремы. Эвристики представляют собой способы определения того выбора, который надо сделать в каждой вершине, чтобы попытаться достигнуть одного из листьев с меньшими затратами труда чем это было бы при достижении листьев посредством полного перебора имеющихся вариантов. В нетривиальных задачах полный перебор следует исключить, поскольку это приводит к комбинаторному взрыву. Возможность возвращения, которая является существенной особенностью универсального решателя задач, легко отображается в дереве как возвращение в предыдущую вершину на данном пути, после чего выбирается другая дочерняя вершина. Таким образом, сам алгоритм в общем случае достаточно простой, и практически единственная значимая проблема, возникающая при его использовании, - это опасность комбинаторного взрыва. Пусть максимальная глубина (максимальная длина пути от корня до листа дерева) ограничена сверху, Lmax и, и максимальное количество дочерних вершин у каждой вершины (количество альтернатив) также ограничено сверху, V т. При выполнении этих требований (заметим, отбрасывающих совсем плохие случаи, при которых вообще нельзя гарантировать завершение анализа) количество операций, прямо пропорциональное количеству вершин в дереве, R kv"3 km", где к — количество операций, выполняемых при работе с каждой вершиной. Оценка числа операций 0(т") говорит о практической неприменимости алгоритма для нетривиальных случаев, и эта оценка достигается, если нет возможности выбора наиболее предпочтительного (из имеющихся) варианта при построении очередной вершины, и именно обеспечение этой возможности является единственным средством для применения этого алгоритма на практике. И именно оценки, приписанные моделям управлений (точнее, эвристика из всех применимых моделей управления в первую очередь используй модель управления с наибольшей оценкой) позволяют исключить необходимость полного перебора, и, более того, достигать количества операций, близкого к О(п), когда в результате последовательного применения наиболее вероятных (на каждом уровне) моделей управления за и шагов все слова оказываются разобранными и получается искомая синтаксическая структура. Отметим следующие особенности предлагаемого подхода: применимые правила вывода (модели управления) полностью определяются операндами (словоформами), ограничена "глубина" дерева, оценки обобщенных моделей управления позволяют использовать очень сильные эвристики.
