автореферат диссертации по документальной информации, 05.25.05, диссертация на тему:Реализация автоматической синтаксической сегментации русского предложения

На правах рукописи

НОЖОВ Игорь Михайлович

Реализация автоматической синтаксической сегментации русского предложения

0S.2S.05 - информационные системы и процессы, правовые аспекты информатики

Автореферат диссертации на соискание ученой степени кандидата технических наук

Москва-2003

Диссертационная работа выполнена в Российском государственном гуманитарном университете.

Научный руководитель:

Научный консультант. Официальные оппоненты:

доктор технических наук, профессор Лахути Делир Гасемович

Кобзарева Татьяна Юрьевна

доктор технических наук, профессор Леонтьева Нина Николаевна

кандидат технических наук,

Ведущая организация:

Пархоменко Владимир Федорович

Всероссийский институт научной и технической информации РАН

Зашита состоится^^ г. в^Ласов на заседании Диссертационного

совета Д 212.198.02 в Российском государственном гуманитарном университете по адресу: г. Москва, Миусская пл., д.6.

С диссертацией можно ознакомиться в библиотеке РГГУ.

Автореферат разослан'

2003 года.

Ученый секретарь диссертационного совета

Меркулов В.Н.

3

Общая характеристика работы

\6\4\

Работа посвящена обоснованию возможности и разработке программных средств автоматической сегментации и частичного синтаксического анализа русского предложения чисто синтаксическими средствами как этапа, обеспечивающего эффективность последующего полного синтаксического и семантического анализа текста.

Синтаксический анализ является одним из наиболее исследованных направлений в теории computer science. Синтаксические анализаторы широко применяются в таких областях как создание компиляторов, проектирование интерфейсов баз данных, искусственный интеллект (ИИ), автоматическая обработка текстов (АОТ), в том числе для автоматизированных информационно-поисковых систем (АИПС, или «поисковых машин»), машинный перевод (МП), анализ химических формул и распознавание хромосом. Синтаксическим анализом (parsing) называется процесс структурирования линейной репрезентации в соответствии с заданной грамматикой. Такое определение, являясь наиболее общим и абстрактным, позволяет охватить весь спектр приложений синтаксических методов. Техникой parsing называется вся совокупность существующих алгоритмов для решения задач синтаксического анализа. Техника parsing берет свое начало в формальных синтаксических теориях естественного языка (ЕЯ), моделирующих механизмы распознавания человеком языковых структур. Несмотря на это, именно применение техники parsing в задачах АОТ далеко не всегда бывает эффективным и дает положительный результат. Так, например, контекстно-свободные грамматики (context-free grammars) и аппарат конечных автоматов (finite-state automata) широко используются в системах морфологического анализа, снятия омонимии и выделения именных групп внутри предложения, но теряют свое прикладное значение в задачах сегментационного, полного синтаксического и семантического анализа, особенно для языков с относительно свободным порядком слов, каким является русский. Формальные математические модели и их программные динамические реализации не способны охватить всю сложность и многообразие языковой системы. Применение формализма для структурирования предложения ЕЯ зачастую приводит к потере правильного синтаксического представления или комбинаторному взрыву, когда программа оказывается не в состоянии просчитать все возможные варианты структур. Лингвистически мотивированные причины такого "провала" - явление омонимии, длина связи между словами, сочинительные

конструкции, нарушающие древовидность графа, to РвДОНОД^Н^КЩ^ЮЗР1

БИБЛИОТЕКА {¡.Петербург 08 МО А

нут

структуры предложения. Сфера действия методов распознавания и классификации объектов в лингвистических процессорах тоже сильно ограничена: скрытые модели Маркова удается применить только в узких контекстно-ограниченных задачах снятия морфологической омонимии, нейронные сети используются в системах автоматического распознавания речи, - такие модели, построенные на обучении и являющие собой альтернативный технике parsing подход, не имеют достаточной силы для отражения способности предложения ЕЯ к неограниченному усложнению. Все эти обстоятельства позволили прикладной (компьютерной) лингвистике выделиться в отдельную область исследования и стать самостоятельно развивающейся ветвью искусственного интеллекта.

Далее в работе мы будем использовать понятие синтаксического анализа только применительно к предложению естественного языка.

Работы по созданию синтаксического модуля велись еще в конце 60-ых годов, но вычислительная мощность компьютеров не позволяла реализовать сложные алгоритмы анализа в полном объеме. Упрощение алгоритмов и отказ от перебора омонимичных вариантов - компромисс, который приводил к низкой точности синтаксического анализа предложения.

Линейной репрезентацией предложения ЕЯ называется цепочка элементов, где каждый элемент является минимальной синтаксической единицей: словоформой или оператором, где оператор - знак препинания или сочинительный союз, с определенным набором характеристик. Обязательной составляющей такого набора у словоформы является ее морфологическая репрезентация, обычно состоящая из значения части речи и граммем, а у знака препинания или сочинительного союза -тип оператора (значение выполняемой им грамматической функции). Таким образом, можно представить линейную репрезентацию предложения в виде цепочки морфологических репрезентаций словоформ и типов операторов.

Процессом структурирования линейной репрезентации предложения называется построение ориентированных графа синтагм и графа сегментов.

Синтагма определяет бинарное синтаксическое отношение вида R(A, В), где А и В - словоформы, a R - тип синтаксического отношения, который соответствует имени синтагмы; А является хозяином, В - слугой, т. е. А управляет В. Таким образом, узлами графа синтагм является терминальные единицы.

Интуитивно сегмент можно определить как часть предложения (в частном случае - целое простое предложение), выделенную на письме знаками пунктуации и описывающую отдельную ситуацию; каждый сегмент имеет в качестве вершины

предикат, выраженный финитной формой глагола, деепричастием, причастием или именем с семантической характеристикой действия; каждый такой предикат и задает ситуацию. Любое придаточное предложение (или причастный и деепричастный обороты) является сегментом, равно как и простое предложение в составе сложного образует отдельный сегмент. В западной лингвистической традиции понятие сегмент эквивалентно термину клауза и является фразовой категорией (подобно NP, VP, etc). Таким образом, узлами графа сегментов являются нетерминальные единицы.

Морфология - термин, в последние годы ставший общеупотребительным. Любой грамотный пользователь глобальной сети сможет объяснить преимущества поиска информации с использованием морфологии. На сегодняшний день только для русского языка существует несколько десятков промышленно реализованных систем морфологического анализа, число же программ английской морфологии в несколько раз больше. Следующим этапом в развитии направления искусственного интеллекта, занимающегося АОТ, является создание промышленной системы синтаксического анализа ЕЯ.

Задача сегментации предложения является первой и, возможно, самой сложной компонентой полного синтаксического анализа. Целью сегментации является выделение и классификация сегментов в составе сложного предложения. Вторая компонента - построение внутрисегментных связей (графа синтагм) -исследована намного глубже и имеет успешные решения (HPSG, LinkParser), экспериментально подтвержденные на анализе простых предложений.

Отсутствие в моделях отдельного сегментационного компонента можно считать одной из основных причин того, что до сих пор не создано эффективных систем синтаксического анализа для русского языка. Сегментация предложения, наряду с морфологическим анализом, должна стать базисной составляющей любой полной системы АОТ. Таким образом, создание компонента сегментации русского предложения является чрезвычайно актуальной задачей.

Синтаксический анализ - задача приближения. Любая синтаксическая теория должна обладать описательной и объяснительной силой. Описательная сила модели формулируется как максимально возможное покрытие грамматических явлений рассматриваемого языка. В данной работе объяснение понимается в контексте ИИ: любая интеллектуальная система должна уметь обосновать каждый шаг принятых ею в ходе анализа решений. Такой критерий подразумевает, что количество эвристик и вероятностно-статистических распределений в системе синтаксического

анализа должно быть сведено к минимуму. Существует и третий, не менее важный критерий прикладной модели - эмулирующий принцип построения алгоритмов, -который заключается в способности лингвистического процессора к воспроизведению интуиции и схемы рассуждений человека в процессе изучения и восприятия языка.

Идеальная модель лингвистического процессора состоит из четырех основных анализаторов: графематического, морфологического, синтаксического и семантического. В данном случае мы ограничимся рассмотрением трехсоставного процессора без семантического анализатора.

Целью настоящей работы было создать экспериментальную систему автоматической сегментации русского предложения, демонстрирующую возможность эффективного - с точки зрения качества и скорости анализа - решения этой задачи как ключевого этапа полного автоматического синтаксического анализа русского текста. Основной решаемой проблемой была при этом разработка методов автоматической сегментации предложения и способов программирования, позволяющих минимальными силами решить поставленную задачу применительно к текстам произвольной (или почти произвольной) синтаксической сложности, а также построение прикладной модели лингвистического процессора, удовлетворяющего описательному, объяснительному и эмулирующему принципам.

Предметом исследования является структура сложного предложения русского языка и законы ее построения.

Работа построена на описании и сравнении решений и результатов двух систем синтаксического анализа, использующих компонент сегментации русского предложения.

Синтаксический процессор группы ДИАЛИНГ был создан в рамках проекта русско-английского машинного перевода (1999-2001). Фундаментом для исследований группы ДИАЛИНГ являлась система анализа политических текстов (ПОЛИТЕКСТ), разработанная в Центре информационных исследований совместно с ВЦ ИСК РАН в 1991-97 гг. под руководством H.H. Леонтьевой. В разное время в разработке синтаксического процессора группы ДИАЛИНГ принимали участие следующие специалисты: А. Сокирко, Д. Панкратов, Л. Гершензон, Т. Кобзарева и И. Ножов.

Синтаксический анализатор научный группы Отделения интеллектуальных систем (ОИС) Института Лингвистики РГГУ (Д.Г. Лахути, Т.Ю. Кобзарева, ИМ. Ножов) был создан в 1999-2003 гг. при финансовой поддержке РФФИ и ФЦП

«Интеграция высшего образования и фундаментальной науки». Базисом для проводимых исследований послужила модель автоматического анализа русского предложения, разработка которой была начата еще в 1971 г. в Информэлектро в секторе (затем отделе) Д.Г.Лахути группой лингвистов под руководством Г.А.Лесскиса. Последняя версия этой модели, положенная в основу описываемой реализации, разработана Т.Ю. Кобзаревой. Создание сегментационного анализатора группы ОИС стало возможным в первую очередь благодаря лингво-алгоритмическому аппарату, разработанному Т.Ю. Кобзаревой, и руководителю проекта д.т.н., профессору Д.Г. Лахути.

Также в работе предложены альтернативные подходы к проектированию некоторых составляющих лингвистического процессора, разработанные автором диссертации в НТЦ "Система" (1997-1998 гг.) и в исследовательском отделе компании Inxight, Software Inc. (2002-2003 гг.). Автор выражает благодарность исследователям Inxight (Masayo Iida, David van den Akker и Carolina Rubio de Hita) за оказанную техническую поддержку и научные консультации. Методы исследования:

• Создание и пополнение лексиконов, содержащих необходимую для анализа морфологическую и грамматическую информацию;

• Разработка лингвистических стратегий и правил, отвечающих синтаксическим законам языка; изучение множества грамматических явлений, характерных для русского языка; поиск (с использованием конкорданса) случаев применения описываемых грамматических конструкций в корпусе текстов;

• Проектирование общей схемы лингвистического процессора и прикладной модели синтаксического анализа;

• Разработка алгоритмов порождения и перебора структурных вариантов предложения, связанных с явлением морфологической и синтаксической омонимии естественного языка;

• Создание динамических структур данных для представления и хранения синтаксической информации и программное моделирование процесса анализа на ЭВМ;

• Создание отладочного массива предложений, охватывающего все множество отраженных в модели грамматических явлений, и тестирование системы на пространстве реальных текстов.

• Оценка эффективности применения предложенных методов в системах АОТ или МП.

В процессе работы над диссертацией автором были получены следующие научные результаты:

1. Разработаны два метода автоматического синтаксического анализа предложения: метод активизации омонимов и рекурсивный метод монтажа сегментов.

2. На основе лингвистических алгоритмов Т.Ю. Кобзаревой построена прикладная модель синтаксического анализатора, удовлетворяющего описательному, объяснительному и эмулирующему принципам, и позволяющая вести анализ параллельно: "снизу вверх" и "сверху вниз".

3. Оглажены грамматические стратегии сегментации и доказана их работоспособность.

4. Программно реализованы, совместно с другими разработчиками, две системы: промышленный синтаксический процессор группы "Диалинг" и экспериментальный сегментационный анализатор научной группы ОИС.

5. В процессе проводимых исследований и изучения существующих подходов к проектированию лингвистических процессоров автором были разработаны и внедрены следующие прикладные модули: бессловарный морфологический анализ (НТЦ "Система") и Russian LinguistX Platform 3.5 (Inxight, Software Inc.), включающая в себя tokenizer, stemmer, tagger и np-grouper русского языка.

Достоверность исследования определяется использованием общих структурных законов языковой системы, сформулированных в синтаксических исследованиях в области теоретической лингвистики, применением современных методов и средств объектно-ориентированного программирования, тестированием программной реализации системы на представительном массиве текстов (500 предложений, включающих разнообразные синтаксические конструкции, как специально построенных, так и взятых из реальных, синтаксически достаточно сложных текстов) и промышленным внедрением отдельных ее компонентов в АИПС. В процессе проведенных исследований был использован практический опыт научных коллективов НТЦ «Система», группы Диалинг, компании Inxight Software и Отделения интеллектуальных систем Института Лингвистики РГГУ.

Научная новизна работы состоит в том, что предложенные алгоритмы порождения структурных вариантов предложения позволили создать успешную модель лингвистического процессора и отказаться от декартова произведения омонимов, проверить работоспособность оригинальных грамматических стратегий анализа, разработанных Т.Ю.Кобзаревой, и реализовать методы автоматической сегментации без искусственного ограничения на перебор структурных вариантов,

обусловленных морфологической и синтаксической омонимией, и без ограничения на глубину рекурсии сегментов и длину предложения.

Научное и практическое значение работы определяется программными реализациями анализаторов, созданных на базе разработанных методов и стратегий и получивших практическое применение в различных системах автоматической обработки информации. В диссертации приведены примеры внедрения программ.

Апробация работы. Основные выводы и научные результаты диссертационной работы докладывались на международных конференциях Диалог в 2000 и 2001 гг., на национальных конференциях по искусственному интеллекту КИИ в 2000 и 2002 гг. и на научно-технической конференции ВИНИТИ в 2000 г. По теме диссертации автором опубликовано 6 работ. Сдана в печать одна статья.

Структура и объем работы: Диссертация состоит из введения, четырех глав, заключения, списка литературы из S3 наименований и двух приложений. Общий объем'работы -147 страниц, основной текст - 131 страница.

Содержание работы

Во введении обоснована актуальность темы, сформулированы цель и задачи исследования, раскрывается практическая значимость и научная новизна результатов работы.

В первой главе приводятся аналогии с химическим строением сложного вещества, шахматной игрой и монтажом фильма, существенные для понимания изложенного в работе подхода к построению модели синтаксической сегментации; рассматриваются современные представления об искусственном интеллекте и его взаимосвязях с естественным языком в аналитической философии; вводятся определения лингвистических понятий релевантных для прикладных моделей; содержится изложение фундаментальных концепций синтаксической теории Head-driven Phrase Structure Grammar (HPSG) и описание ее приложений; рассматриваются синтаксические процессоры английского (LinkParser) и немецкого (STP) языков.

С 90-х гг. учеными (I. Sag и T. Wasow) из Стэндфордского Университета создается унифицирующая грамматика HPSG, основанная на лексикализме и критике контекстно-свободных грамматик (CFG). Унификацией называется наиболее общий метод, позволяющий двум совместимым дескрипциям структуры свойств, построенным лексиконом для каждой лексической единицы, соединять информацию, которую они содержат, в одну (обычно большую) дескрипцию.

Успешными унификациями синтаксических единиц называется цепочка унификаций, которая позволяет свернуть предложение до уровня одной вершинной дескрипции с единой структурой свойств. В морфологически развитом языке, каковым является русский, с высоким коэффициентом глубины вложения составляющих, число ложных унификаций в процессе анализа сильно увеличится. Прикладным недостатком HPSG является тот факт, что успешность работы такой грамматики целиком зависят от полноты лексикона.

Процессор LinkParser, являющий собой противоположный HPSG подход, был реализован группой исследователей (Daniel Sleator, Davy Tempetley и др.) в начале 90-ых гг. Используемой техникой анализа является CFG. Единица словаря грамматики описывается логической формулой, состоящей из соединителей (коннекторов). Коннектор состоит из имени типа синтаксической связи (О - объект, CL - сегмент и т.д.) и суффикса, определяющего вектор направления соединения (*+' право- и лево-направленный коннектор). Два слова Wi и W2, имеющие словарные входы Wi: А" и W2: А+, образуют соединение А в линейной последовательности W2Wi, но не связаны в цепочке W1W2. Чтобы получить для каждого слова множество его однозначных грамматических интерпретаций, формула приводится к ее дизъюнктивной форме. Построение грамматики LinkParser для русского затруднительно: (а) основная идея грамматики - использование лево-и право-ветвящихся коннекторов - теряет свою силу для языка с относительно свободным порядком слов (особенно для глагольных групп); (б) если предположить, что каждое возможное направление связи можно маркировать отдельным типом коннектора, то в этом случае резко возрастет как число базовых коннекторов, так и число дизъюнктов словоформ, что негативно скажется на скорости работы процессора. Тем не менее, LinkParser по праву считается одним из самых элегантных и детально проработанных решений задачи синтаксического анализа английского языка.

В исследовательском центре ИИ в Саарбрюкене в 2000-2001 гг. был создан синтаксический процессор немецкого языка Shallow Text Processor (STP). Как и лингвистические процессоры русского языка, STP характеризуется разделением на функционально независимые компоненты, каждый из которых соответствует одному из уровней лингвистического анализа. Принципиально новое в STP -выделение сегментации в отдельный независимый модуль анализа, позволяющее отказаться от традиционного анализа «снизу вверх». Если обязательным условием для построения и оценки правильности синтаксической структуры предложения в

ЬшкРагеег служит связность графа, то результатом синтаксического разбора в БТР является частично связанное дерево зависимостей. В процессе анализа модуль сегментации немецкого предложения БТР использует свойство рекурсивное™ сегментов, похожим образом устроена и процедура сегментации русского предложения в системе ОИС; публикации БТР в Германии и системы ОИС в России вышли параллельно и независимо. В описание процессора не включена информация

0 сочинении предикатов и возможности построения структурных вариантов сегментации предложения.

Вторая глава посвящена проектированию морфологического анализа, некоторым методам снятия грамматической омонимии и построения именных групп.

Алгоритмы морфологического анализа без словаря (НТЦ "Система") построены на самообучении программы на открытых массивах реальных текстов и совмещают два подхода: лингвистический - формализованная грамматика для построения морфологических гипотез - и математический - метод корреляции1, позволяющий унифицировать морфологическую гипотезу. Морфологический анализ без словаря является центральной компонентой системы автоматической индексации БД, реализованной в СУБД Огас1е81. Выходным результатом системы является автоматически построенный грамматический словарь основ и связанный с ним индекс документов, предназначенный для полнотекстового поиска по БД Настоящий анализатор отличает способность выбирать гипотезу в условиях отсутствия полноты данных. Процесс автоматической индексации состоит из графематического и морфологического блоков. Цель графематического блока получить выборку полных словоформ из массива текстов БД для последующего морфологического анализа Используя эвристики, графематика обрабатывает внешнее представление текста, разбивая полученные данные на три потока: цифро-символьные комплексы, аббревиатуры и полные словоформы. Последний поток поступает на вход морфологического анализа, цель которого разбить все множество словоформ на подмножества по признаку принадлежности к той или иной лексеме, привести все элементы каждого такого подмножества к уникальной основе, однозначно определить грамматические характеристики лексемы. Морфологический анализ состоит из трех модулей и соблюдает определенную

1 Данный метод корреляции был разработан специально для задачи морфологического анализа и не имеет ничего общего с его вероятностно-статистическим аналогом, предназначенным для решения других задач [прим автора].

последовательность действий. Первый модуль содержит статический массив флексий и правила формализованной грамматики русской морфологии, построенной на основе грамматического словаря A.A. Зализняка. Данный модуль может быть заменен формализованной морфологией любого другого флективного языка. Второй модуль, используя правила формализованной грамматики, позволяет строить морфологическое дерево словоформы, в узлах которого хранятся все возможные гипотезы об основах и значениях грамматических категорий словоформы. Третий модуль содержит метод подбора словоформ на одну лексему, т.е. выбор коррелятов для дерева исходной словоформы. После того, как набраны корреляты, для каждой словоформы также строится морфологическое дерево всех возможных гипотез, в результате чего образуется лес деревьев. Метод корреляции осуществляет сравнение морфологических деревьев внутри леса и унификацию гипотез.

Корреляция проводится по гипотезам основ и значениям классифицирующих грамматических категорий, таких как часть речи, парадигматический класс, спряжение глаголов и род существительных. Значения словоизменительных категорий в корреляции не участвуют. Для унификации гипотезы метод корреляции использует матрицы корреляций. Лесом называется множество деревьев словоформ F = {Ti,..,Tj,..,Tn}. Множество всех построенных гипотез об основе в F обозначим U = {si,..,v-,Sm}- Параметром корреляции t называется значение грамматической категории. Матрицей корреляции A(t) = jaj леса Fem гипотезами об основах и п деревьями словоформ называется (m х п )-матрица, в которой at = 1, если заданный параметр корреляции t определен для s, в Tj, и ав = 0 в противном случае. В процессе корреляции отдается приоритет гипотезам исходной словоформы, на основе которых подбираются корреляты, что позволяет избежать ситуации, когда лес вырождается в пустое множество. Число матриц корреляции внутри одного типа корреляции определяется по числу возможных значений грамматической категории.

п

Для каждой матрицы корреляции находится к = шах , после чего из

множества значений к внутри одного типа корреляции также выбирается максимальное значение, которое и соответствует унифицированной гипотезе. Узлы не получившие максимального значения удаляются из деревьев словоформ. Условие ап Ф 0 задает приоритет гипотезам дерева исходной словоформы Ть

Традиционно в синтаксических и семантических теориях используется представление языковой структуры с помощью деревьев. В описываемой системе, пожалуй, впервые данный формализм оправдано был применен к морфологии. Бессловарная морфология сохраняет свою актуальность в задачах автоматического пополнения лексиконов и индексации документов. Метод корреляции не зависит от анализируемого ЕЯ и демонстрирует эффективную работу при сравнительно небольшой выборке.

Существует два базовых подхода к проектированию морфологических машинных лексиконов. Первый копирует лингвистическую модель описания, где выделяются основные парадигматические классы и правила регулярных альтернаций (фонетических чередований). Количество таких парадигм сравнительно невелико (8 классов именного склонения и 16 глагольного спряжения в модели Зализняка). Второй подход рассматривает любого вида регулярное и нерегулярное чередование как часть расширенной псевдо-флексии. В подобной модели описания число парадигматических классов для русского языка возрастает до 3000, но рост числа классов при проектировании компенсируется однородностью лексикона и отсутствием дополнительных вычислений, связанных с правилами альтернаций.

Русскоязычная часть промышленного процессора LinguistX Platform имеют четыре уровня текстового анализа: tokenizer - графематический анализ; stemmer -лемматизация входных словоформ; tagger - снятие морфологической омонимии; пр-grouper - синтаксическое выделение именных составляющих NP из текстов.

Лексикон stemmer применяет первый подход к проектированию морфологических данных. Технология анализа построена на разновидности конечных автоматов finite-state transducer (FST). FST называется автомат, в котором каждый переход между состояниями в сети имеет выходную помету в дополнение к входной. Исходный морфологический лексикон компилируется в lexicon transducer, а компонент правил альтернаций - в rule transducer. Результирующий лексический конечный автомат (lexical transducer), т.е. полное морфологическое представление языка, получается композицией lexicon transducer и rule transducer.

Tagger разрешает грамматическую омонимию словоформы по синтаксическому контексту в предложении. Tagger представляет собой скрытую марковскую модель, способную запоминать последовательности длиной от 4 до 6 синтаксических единиц. Коэффициенты вероятностей выбора морфологических значений вырабатываются в цепи путем обучения марковской модели на

размеченном корпусе текста. Каждой словоформе в размеченном тексте присваивается морфологическая помета (tag). Метод снятия омонимии, основанный на скрытой марковской цепи, - редкий случай, когда вероятностно-статистическая модель эффективно работает в задачах АОТ.

В модуле np-grouper для создания образцов NP - последовательностей грамматических элементов внутри группы - используется язык регулярных выражений, где каждое выражение представляет собой грамматический образ некоторой именной группы или ее подгруппы. Множество таких выражений составляет грамматику именных групп. Достоинством грамматики именных групп, сформулированной на языке регулярных выражений, является ее краткость и прозрачность.

Лексиконы морфологических компонентов проекта Диалинг и экспериментальной системы ОИС относятся к моделям второго типа. Процедура предсказания не найденных в лексиконе словоформ в этих компонентах устроена одинаково. Если входная словоформа не была найдена в лексиконе, то осуществляется поиск в лексиконе словоформы, максимально совпадающей с конца со входной словоформой. Парадигма найденной словоформы используется как образец для создания парадигмы неизвестной словоформы.

Все приведенные в работе морфологические и предсинтаксические компоненты анализа потенциально являются неотъемлемой частью идеальной модели полного синтаксического процессора, а также позволяют демонстрировать общность формализма и методов решения задач на разных уровнях лингвистического анализа. Результаты работы морфологических модулей поступают на вход синтаксических анализаторов, описанию которых посвящена третья глава диссертации.

Так же как и STP, синтаксический процессор Диалинг относится к алгоритмическим системам модульного типа. Принципиальным отличием в архитектуре анализатора можно считать двунаправленное взаимодействие модуля сегментации и синтаксиса (построение синтаксических групп слов в предложении). Общую схему действий в анализаторе можно представить в виде последовательности шагов:

1. Членение предложения по знакам пунктуации и сочинительным союзам на исходные отрезки (начальные сегменты). Объединение исходных отрезков с простыми случаями однородных рядов прилагательных, наречий, существительных, etc. Определение вершин и типов начальных сегментов.

2. Построение аналитических форм глагола внутри исходных отрезков.

3. Выделение групп терминов внутри исходных отрезков с помощью тезаурусов: общего, компьютерного и финансового.

4. Интерпретация вершин начальных сегментов, содержащих тире, и попытка восстановления элиминированной глагольной связки (Copul).

5. Декартово произведение омонимов внутри начальных сегментов - построение множества однозначных морфологических интерпретаций (МИ) одного сегмента. Построение простых синтаксических групп для каждой МИ сегмента подмножеством синтаксических правил: КОЛИЧ ("двадцать восемь"), ПРИЛ-СУЩ ("большой дом"), ПГ ("на столе"), ОДНОР_ПРИЛ ("умный и обаятельный"), etc.

6. Правила для объединения сочиненных начальных сегментов.

7. Построение сочиненных синтаксических групп для каждой МИ подмножеством синтаксических правил: ОДНОР ИГ ("сын своего отца и дочь своей матери"), Р_С_ОДНОР_СУЩ ("как новые книги, так и пыльные папки"), Р_С_ОДНОР_ИНФ ("если не писать, так читать"), etc.

8. Правила для вложения контактно расположенных сегментов (причастных и придаточных определительных) - установление иерархии на сегментах.

9. Построение груш подмножеством синтаксических правил для каждой МИ, где вершина - синтаксическая группа подчиняющего сегмента, а зависимое -вершина вложенного сегмента.

10. Правила для объединения разрывных сегментов. Завершение полной сегментации предложения.

11. Построение групп множеством всех синтаксических правил для каждой МИ. Всего в модели процессора используется 40 типов групп.

12. Оценка синтаксического покрытия каждой МИ (лучший вариант получает максимальный вес) и установление порядка на множестве морфологических интерпретаций каждого сегмента.

Таким образом, расширение границ сегментов происходит последовательно с постепенным накоплением синтаксической информации внутри каждого начального сегмента (сегментация «• синтаксис). В свою очередь, каждая новая итерация синтаксических правил пытается расширять границы синтаксических групп, вкладывая уже построенные ранее группы в новые составляющие.

МИ сегмента являются результатом декартова произведения омонимов словоформ, входящих в данный отрезок. Сегментация позволяет избежать полного

декартова произведения предложения, что значительно сокращает число рассматриваемых вариантов. В словосочетании "рабочие стали" (рабочие: рабочий.И и рабочий.Аф; стали: сталь.И и стать.V) строится четыре МИ, для каждой из которых будет построена своя структура групп. Лучший вес получают МИ с максимальным количеством синтаксических групп. Множества синтаксических групп двух МИ, как правило, имеют непустое пересечение. Покрытием МИ называется число словоформ, вошедших в синтаксические группы данной МИ.

Внутрисегментный анализ в процессоре Диалинг - это синтаксис неразрывных групп. Исключение в процессоре делается для группы подлежащее-сказуемое, которая в большинстве случаев является разрывной составляющей. Для синтаксической группы определены: (а) координаты (номер первого и последнего слова); (б) тип группы (ПРИЛ-СУЩ, ПГ, ОДНОР_ИГ, ПРЯМ_ДОП, etc.); (в) координаты главной подгруппы группы. Например, группа "высокий дом" имеет соответствующие параметры: (а) {1, 2); (б) ПРИЛ-СУЩ; (в) {2, 2}. Каждый тип группы строится отдельным правилом, которое имеет направление поиска зависимого и определяет вершину группы. Используя параметры группы, легко вычислить синтаксически главное слово, что позволяет переводить структуру вложенных групп в размеченное дерево зависимостей. Порядок применения синтаксических правил жестко задан как на отдельных подмножествах правил (шаги 5, 7, 9 в схеме), так и на множестве всех правил (шаг 11 в схеме), что позволяет сохранять правильную иерархию вложений групп. Так, правило ПРИЛ-СУЩ (согласованные прилагательное + существительное) должно отрабатывать раньше правила ГЕНИТ_ИГ (существительное + существительное в родительном): "высокий дом отца" ГЕНИТ_ИГ(ПРИЛ-СУЩ(1, 2), 3) vs. *ПРИЛ-СУЩ(1, ГЕНИТ_ИГ(2,3)). Синтаксические правила не используют модели управления слов.

Для каждого сегмента определены: (а) координаты (номера слов в предложении, соответствующих левой и правой границе сегмента); (б) вершина сегмента: номер слова и тип вершины h е Н = { ГЛ_ЛИЧН (глагол в личной форме), КР_ПРЧ (краткое причастие), КРПРИЛ (краткое прилагательное), ПРЕДК (предикативное слово), ПРИЧ (причастие), ДПР (деепричастие), ИНФ (инфинитив), ВВОДИ (вводное слово), 0 }, где 0 означает пустую вершину, а все типы в Н иерархически упорядочены; (в) союз или союзное слово. Тип вершины сегмента задается по значению селективного признака слова, репрезентирующего вершину, и может быть представлен в виде множества значений, соответствующих допустимым

значениям морфологических омонимов этого слова. В сегменте "когда ему весело" (весело: веселый (кр. прил.), весело (предикатив), весело (наречие)) определены соответствующие параметры: (а) {1, 3}; (б) [3] и { КР_ПРШ1, ПРЕДК, 0}; (в) 'когда'.

Порядок выполнения сегментационных правил (отраженный в шагах 1, б, 8 и 10 схемы) определен последовательностью работы их подмножеств, внутри этих блоков правил порядок выполнения - свободный. В процессоре определено три операции на сегментах: объединение, вложение и деление. Каждое правило, фактически, является проверкой ряда условий на возможность применения той или иной операции над сегментами.

Помимо условий, накладываемых на вершины двух претендующих на объединение сегментов, основным критерием объединения служит возможность построения группы на границе двух сегментов. Получившийся в результате объединения сегмент наследует вершину того начального сегмента, чей тип вершины находится выше в иерархии Н. Морфологические интерпретации нового сегмента получаются путем перемножения МИ объединившихся начальных сегментов.

Вложение одного сегмента в другой может быть как согласованным, так и произвольным. Правила, отвечающие за согласованное вложение сегмента, ищут вершину придаточного определительного или причастного оборота в лево-стоящем сегменте. Для выполнения операции вложения вводится специальное понятие -юнит (шШ). Юнитом в сегменте может быть либо слово, представленное множеством своих омонимов, либо вложенный сегмент, представленный множеством омонимов своей вершины. Тогда МИ сегмента есть линейная последовательность омонимов его юнитов. Понятие юнит позволяет строить синтаксические группы, где составляющей группы является вложенный сегмент. Произвольное вложение сегментов происходит в случае объединения двух дистантно расположенных исходных отрезков, тогда все сегменты, находящиеся между ними, вкладываются в новый сегмент, полученный в результате объединения. При вложении одного сегмента в другой МИ подчиняющего сегмента умножаются на омонимы вершины подчиняемого сегмента с сохранением в МИ ранее построенных синтаксических групп.

Операция деления сегмента выполняется только для одного правила: выделения необособленного согласованного определения (НСО) Не имея границ,

выраженных знаками препинания, НСО вычленяется алгоритмически в отдельный подсегмент.

Недостатком системы является отсутствие синтаксической омонимии как на уровне иерархии и границ сегментов, так и на уровне групп; также в анализаторе не обрабатываются случаи сочинения предикатов, что служит иногда препятствием для '

объединения исходных отрезков и приводит к ошибочному построению сегментационной структуры. Неоспоримым достоинством процессора Диалинг •

является его завершенность: программная реализация доведена до уровня промышленного использования, - система характеризуется устойчивостью на открытом пространстве реальных текстов.

Сохраняя принцип модульности проектируемой системы, процессор ОИС не использует в своей модели правила, а применяет грамматические стратегии для анализа предложения, каждая из которых является независимым модулем, вызываемым в качестве подпрограммы. Стратегии позволяют эффективно работать с морфологической и синтаксической омонимиями в системе ОИС. Анализ в процессоре однонаправлен; первая фаза работы анализатора выполняет построение предложных РКЫ и именных ИЯА групп (РК№-ЖА модуль), во второй фазе осуществляется сегментация сложного предложения с вызовом (только в алгоритмически зафиксированных случаях) модуля сочинения, - РК>МЛ1А модуль=>сегментация.

Выделяются два алгоритмически обоснованных класса сегментов: а- и Р-сегменты. р-сегментами называется множество простых предложений в составе сложного, ос-сегментами - все остальные, а-сегменты делятся на следующие подклассы: (1) придаточные предложения (вчЬв); (2) деепричастные обороты (1>8); (3) причастные обороты и обособленные определительные (АЭ); (4) предложные обороты (Рв); (5) вводные обороты (Рг$). В начале работы системы отрабатывает блок алгоритмов (РКЫ-№1А модуль), отвечающий за построение основных синтагм. >®А и Р1Ш позволяют элиминировать часть потенциальных границ сегментов -операторы, которые служат разделителями в однородных цепочках, вложенных в проективные синтагмы. Следующий этап анализа разбивает предложение на первоначальные отрезки, границами которых являются знаки пунктуации, и ,

приписывает каждому отрезку значение класса или подкласса. Завершающий и основной этап анализа (непосредственно сегментация) объединяет отрезки, тем самым укрупняя узлы и формируя простые сегменты. В обусловленных алгоритмически случаях, в процессе сегментации фиксируются цепочки

сочиненных составляющих, связь подлежащее-сказуемое или связь глагола с прямым дополнением. Поиск и фиксация всех таких синтагм в предложении, в отличие от РКЫ и ЫИА, не являются обязательным условием анализа.

Любое предложение естественного языка в системе описывается двумя графами: граф синтагм и граф сегментов. Узлами графа синтагм являются терминальные единицы (словоформы), дуга в графе образует синтагму и задает тип связи. Узлами графа сегментов являются нетерминальные единицы - сегменты, -дуга в графе задает межсегментную связь. Грамматическое сочинение терминальных единиц в графе синтагм и сочинение однородных сегментов в графе сегментов нарушает древесность графов, так как каждый элемент множества узлов, образующих сочинительную связь, попарно связан со всеми остальными элементами множества и одновременно является как слугой, так и хозяином всех узлов, принадлежащих множеству сочинения. Таким образом, граф синтагм и граф сегментов - ориентированные графы, содержащие контуры и замкнутые пути. Связность графа не является обязательным условием анализа

Сегментационный анализатор работает с двумя типами омонимии: морфологической и синтаксической. Морфологическая омонимия в сегментационном анализаторе определена только на графе синтагм.

Синтаксическая омонимия представляет собой гораздо более абстрактный случай и задается стратегиями анализа в алгоритмах. Так, синтаксическая омонимия выражается наличием или отсутствием той или иной связи в графе синтагм. Синтаксическая омонимия в графе сегментов возникает при объединении первоначальных отрезков в более крупные узлы. Омонимичный граф сегментов, порожденный таким типом омонимии, будет отличаться от своего родителя границами сегментов и, возможно, числом узлов Синтаксическая омонимия определена как на графе синтагм, так и на графе сегментов.

Линейная структура предложения в естественного языка состоит из множества словоформ Б = (ЧУ), ..., \У„}, где каждая словоформа представлена множеством морфологических омонимов Ш, = {Ьь Ь^, ....Ьщ}, где Ь, является кортежем значений {часть речи, граммемы, примитивная модель управления}. Таким образом, предложение можно представить как упорядоченную цепочку элементов Б = {ем, е^,... ,е1Ш, ••■, епр}, где первый индекс элемента соответствует номеру словоформы в предложении, а второй - номеру морфологического омонима словоформы. Первоначальный этап синтаксической сегментации, отвечающий за построение графа синтагм, начинает работать с линейным представлением Б. При

построении синтагм и поиске предикатов происходит активизация омонимов, в результате чего возникают смешанные цепочки типа S = {Wi, e2j, W3, ..., е^}. Таким образом, графом синтагм предложения S называется граф G=(S , Е), где S -множество узлов, состоящих из элементов смешанной цепочки S , а Е - множество упорядоченных пар на S , то есть множество синтагм; в частном случае, при отсутствии морфологических омонимов, G=(S, Е). Существует динамически пополняемый список омонимичных графов синтагм L = {Gi=(S 1, Ej), G2= (S 2, E2),..., Gk= (S ь Ek)}, активизация нового омонима является событием, которое вызывает пополнение списка. Каждый G, содержит минимальное число синтагм, необходимых для дальнейшей сегментации.

Синтаксическая сегментация проводится для каждого графа синтагм из списка L, собирая разорванные вложениями а- и р- сегменты. Предложение S представляется в виде графа, в узлах которого находятся сегменты, а дуги являются связями между сегментами, такой граф сегментов GS=(ST, SE) можно предстаешь как множество узлов ST = {Segmi, Segm2, ..., Segm„}, где Segm, с: S , и множество SE межсегментных связей на ST. Каждому графу синтагм G из списка L соответствует множество графов L = {GS,=(STb SEO, GS2KST2, SE2), ..., GSmKSTm, SEm)}, множественность интерпретаций графа синтагм G обусловлена возникновением синтаксической омонимии. После того, как проанализированы все элементы списка L, мы получаем множество всех возможных графов сегментов данного предложения М = {GSi, GS2, ..., GSq}, из которых в дальнейшем должны выбираться лучшие структуры. Множественность синтаксических интерпретаций зачастую определяется естественной смысловой омонимией в предложении. После завершения сегментации возможно проведение полного синтаксического анализа внутри а- и р-сегментов.

Базовым ограничением, на котором строится анализ в процессоре, является проективность сегментной структуры предложения. Рассмотрим предложение с разрывными сегментами и глубиной вложений равной трем: "Мать, когда мальчик, выйдя во двор, где стояла машина, к которой было необходимо подойти, споткнулся, не заметив приступка, и упал в сугроб, наметенный за ночь, выбежала ему помочь". Разделим его на исходные отрезки: р][мать] otifSubS: когда мальчик] a2[DvS: выйдя во двор] ot3[SubS: где стояла машина] at[SubS: к которой было необходимо подойти] Рг[споткнулся] OsfDvS: не заметив приступка] Рз[и упал в сугроб] a<s[AS: наметенный за ночь] р4[выбежала ему помочь]

Схема объединения исходных отрезков в полные сегменты представлена на рис.1:

[ д. | 1 СИ | 1 ад | | а, | | Р, | | а, | | Р, | | а« | [рГ

Рис 1

В результате процедуры объединения образовано семь сегментов: [1р]'матъ выбежала ему помочь', [2а]'когда мальчик споткнулся и упал в сугроб', [За]'выйдя во двор', [4а]'где стояла машина', [5а]'к которой бьшо необходимо подойти', [6о]'не заметив приступка', [7а]'наметенный за ночь'. Структура межсегментных связей показана на рис.2:

Получившиеся схема объединения (рис.1) и структура межсегментных связей (рис.2) проективны, т.е. не содержат пересечения стрелок. Такое свойство схемы объединения и свойство структуры полных сегментов будем называть сегментной проективностью2. Такого рода проективность, связанная с сегментной структурой предложения, - абсолютно жесткая, в отличие от традиционной синтаксической (на уровне синтагм).

Методом монтажа будем называть а- и р-анализ, опирающийся на свойство рекурсивности сегментов, а-анализ, являясь центральной и алгоритмически наиболее сложной стратегией сегментации, предшествует р-анализу и позволяет ликвидировать обусловленные вложением а-сегменгов разрывы простых р-сегментов в составе сложного предложения в. Алгоритм а-анализа идет справа налево по в, осуществляя поиск а-отрезков, и заново вызывается рекурсивно для текущего а-отрезка после каждого нового присоединения право-стоящего Р-отрезка. Поиск справа налево каждого следующего а-отрезка в в дает возможность начинать сборку а-сегментов с вложений максимальной глубины.

Определяются грамматические условия для присоединения Р-отрезка: (а) синтаксическая неполнота а-отрезка (а-тсотр^епевз); (б) синтаксическая неполнота р-отрезка (Р-тсотр1е1епе5з); (в) в а-отрезке существует слово \Уь способное управлять словом W2 в р-отрезке (а-тападе); (г) слово или группа слов в

2 Термин впервые был введен в работах Т.Ю. Кобзаревой

a-отрезке образует сочинительную связь со словом или группой слов в (3-отрезке (coordination). В ситуации контактного расположения (3- относительно а-отрезка допустимо использование только условия сочинения (coordination) для присоединения (3-отрезка, при этом накладываются дополнительные грамматические ограничения (constraints) на поиск сочинения.

Представим множество исходных а- и р- отрезков на предложении S в виде вектора V = {Sgi, Sg2,.., Sgn}. Тогда запишем алгоритм a-анализа псевдокодом: a-Analyse

1 for i length [V] downto 1

2 do if V[i) = a

3 then V[i] <- Montage(V, V[i], i, i+1)

Montage(V, a, i, j)

1 if j < length[V]

2 then if V[j] * p

3 then a Montage(V, a, i, j+1 )

4 else if ( j = i + 1 and coordination^, V[j], constraints) )

or(

j>i+l and(

a-incompleteness(a) or(

P-incompleteness(V|j]) and(

a-manage(a, V[j]) or coordination(a, V[j])

)

)

)

5 ) then ufa© V[j]

6 delete(V[j])

7 a Montage(V, a, i, j)

8 return a

На вход Р-анализу поступает вектор, содержащий последовательность Р-отрезков, оставшихся непроанализированными или неприсоединенными к а-сегментам. В упрощенном виде алгоритм р-анализа можно представить в виде последовательности итераций: (а) процедура поиска предикатов (в том числе неморфологических) в Р-отрезках; (б) установление границ между зонами синтаксического влияния предикатов; (в) объединение Р-отрезков внутри подгрупп контактно расположенных p-отрезков при сочинении предикатов.

Активизация морфологического омонима, которая возникает в тех случаях, когда хотя бы один из омонимов словоформы h е W не отвечает проверяемому условию/ограничению или не способен образовать строящуюся синтагму,

порождает отдельный граф синтагм G, состоящий из узлов новой смешанной цепочки типа S . В точке выбора порожденный граф наследует текущее состояние своего родителя, копируя ранее построенные синтагмы. Новый граф выделяется в отдельный поток, где процедура анализа продолжается из точки выбора.

Активизация синтаксического омонима возникает на этапе построения а- и Р- сегментов. В точке выбора порождается граф сегментов GS, что создает множественность интерпретаций для графа синтагм G на уровне сегментов. Как и в случае морфологической омонимии, порожденный граф наследует текущее состояние своего родителя, копируя ранее построенные сегменты.

Метод активизации омонимов состоит из следующих понятий, определенных в процессоре:

• Условие/ограничение: в ходе работы стратегий в пределах одного графа синтагм или сегментов проверяются условия/ограничения для некоторых элементов е^ и е,т цепочки S". Условия/ограничения могут определять как морфологическую, так и синтаксическую омонимии. Подтвержденные в ходе анализа условия/ограничения, способные задавать синтаксическую омонимию, называются многозначными.

• Синтагма: построение синтаксического отношения R(e&, ejm). Синтагма, при определенных условиях/ограничениях, задает синтаксическую омонимию на графе синтагм.

• Событие: событие возникает в системе в результате подтверждения условия/ограничения или построения синтагмы.

• Точка выбора: событие в системе происходит в некоторой точке процедуры анализа, которая может быть определена в любом из модулей процессора; в случае порождения омонимичного графа такая точка выбора служит координатами места в процедуре анализа, с которого будет начат анализ нового графа.

• Состояние: текущим состоянием графа называется множество его узлов и связей, состояние графа фиксируется в точке выбора.

• Класс эквивалентности: класс эквивалентности [h]p, где р - отношение эквивалентности на множестве омонимов словоформы W е S, h - омоним словоформы W, состоящий из пары значений pos - часть речи и GR - множество граммем, тогда р = {(h„ hj): h„ hj e W; h,={posb GR,}; hj={poSj, GRJ; h,- (pos, s X) & (Y n GR, v Y = 0) и h, = hj, если и только если для h, справедливо (poSj б X) &

(У Г\ йЯ, V У = 0)}; X и У - множества, заданные инициировавшим событие условием/ограничением. Пример: допустим, что в цепочке в" найден предикат е,т (е;т := ^ е У/]), тогда условием/ограничением, осуществлявшим поиск предиката (Предикат={финитная ф. гл., кр. прил., кр. прич., предикатив}), формируется множество X = Предикат и У = 0 для отношения эквивалентности р; предположим, словоформа состоит из четырех омонимов \У, = {Ь]={ кр. прил., 01^}, Ь2= {наречие, вЯг}, Ь3={предикатив, БЯз}, И4= {частица, ®14}}; пусть для ЬшШ = 3, тогда £р(Ьт) = [Ьш]р = {Ьь Ь3}.

• Функция разбиения: аргументом функции является класс эквивалентности |Ъ]р и множество если В = V/ \ [Ь]р и В * 0, то вызвать функцию клонирования, иначе завершить обработку события; [Ь]р будем также называть множеством Ш', а В - множеством W".

• Функция клонирования: аргументом функции служат точка выбора, в которой возникло событие, и состояние графа в данной точке; функция клонирования изменяет множество узлов или связей исходного графа и порождает омонимичный вариант исходного графа, который добавляется в конец списка Ь или Ь' для графа синтагм или сегментов соответственно. В точке выбора отличие между исходным и клонированным вариантами графа - незначительное, но по окончании процедуры анализа для каждого из вариантов различие в узлах и связях, как правило, становится существенным. Так, морфологическая омонимия на графе синтагм может повлиять на узлы зависящего от него графа сегментов, т.е. на границы построенных сегментов.

Таким образом, принцип ленивых вычислений, алгоритмически мотивированный условиями/ограничениями, реализуется в системе через событие и обработку каждого такого события. В процессоре зафиксировано три сценария обработки события:

(1) Событие[(3=(8 , Е), условие/ограничение] => Функция разбиения([Ь]р, Щ => Функция клонирования(точка выбора, состояние Сг=(8 , Е)) = (3={8х , Е) и й'^Эу , Еу), где \У' с Бх", с Эу'и Е = Еу.

(2) Событие[Сг=(8 , Е), синтагма вуп] => Функция клонирования(точка выбора, состояние Оф", Е)) = (Нв", Е*) и 0'=^", Еу), где вуп е Е*, вув е Еу и Б" = Бу".

(3) Событие[08=(8Т, вЕ), многозначное условие/ограничение] => Функция клонирования(точка выбора, состояние 08=(8Т, вЕ)) = ОБ^вТ» БЕ) и 03'=(8ТУ,

SEy), где STX * STy и SE = SEy. Синтаксическая омонимия на графе сегментов возникает при неоднозначности присоединения р-отрезка.

Основная идея изложенного метода активизации омонимов состоит в том, чтобы избежать (в тех случаях, когда это возможно) полного декартова произведения морфологических омонимов (Wi х ... х Wn) и повторного построения общих для омонимичных графов синтагм и сегментов.

В четвертой главе диссертации обсуждаются примеры использования и внедрения синтаксических процессоров ЕЯ и их составляющих: бессловарный морфологический анализ в системах автоматического построения словарей и поиска в правовой базе данных НТЦ "Система", технологии Inxight LinguistX Platform в системах АОТ (Мигах, Categorizer и Smart Discovery), синтаксический процессор в системе МП ДИАЛИНГ, экспериментальные возможности сегментационного анализатора группы ОИС.

Приведем показатели оценки качества и скорости для синтаксического процессора Диалинг и экспериментальной системы сегментации ОИС:

Характеристика Диалинг ОИС

Отношение количества правильно сегментированных сложных предложений к общему количеству сложных предложений в тексте, [%] 78 85

Отношение количества правильно построенных синтаксических групп к общему количеству построенных групп в предложениях текста, [%1 97 —

Отношение количества правильно выбранных с использованием системы весов МИ сегмента к общему количеству выбранных МИ сегментов в предложениях текста, [%1 95

Покрытие отношение количества слов, вошедших в состав синтаксических групп, к общему количеству слов в тексте, Г%] 79 —

Отношение количества правильно построенных синтагм к общему количеству построенных синтагм в предложениях текста, |%1 — 98

Скорость синтаксического анализа, [слов/сек.] 350 450

Имеющаяся программная реализация синтаксической сегментации может быть значительно оптимизирована для дальнейшего промышленного использования. Оптимизация программы способна существенно увеличить скорость анализа.

Синтаксический процессор Диалинг является компонентой системы МП Диалинг. Результаты синтаксического анализа поступают на вход семантического модуля системы, использующий в процессе работы русский общесемантический словарь (РОСС). Центральной функцией синтаксического анализатора в составе системы МП Диалинг является сегментация сложного предложения и выбор МИ внутри сегментов. В Исследовательском центре искусственного интеллекта ИПС РАН в Переславле-Залесском синтаксический анализ Диалинг интегрирован как компонент лингвистического процессора в систему автоматического извлечения информации из текстов на русском языке.

Процессор синтаксической сегментации группы ОИС используется в учебном процессе РГТУ для проведения лабораторных и семинарских занятий.

Создание эффективной системы сегментации сложного предложения позволит осуществлять поиск заданного образца в пределах одного сегмента, что существенно повысит качество работы АИПС. Сегментационный анализатор, способный выделить сегмент простого предложения в составе сложного, может стать центральным звеном в программах автоматического реферирования текстов. Сегментация предложения - компонента полного синтаксического анализа, без которой представляется невозможным полноценное решение задач извлечения информации из текстов, автоматической кластеризации информационного потока и машинного перевода.

В заключении суммируются основные результаты диссертационного исследования:

- автоматическая синтаксическая система ОИС представляет собой не законченный промышленный продукт, а экспериментальную систему для отработки лингвистических решений;

- ограничения на тексты, обрабатываемые системой, связаны с морфологическим или даже графематическим этапом анализа (отсутствие нелинейных элементов, предложений, состоящих из нескольких абзацев, и т.п.);

- в основу работы положены лингвистические алгоритмы, разработанные Т.Ю.Кобзаревой; задача состояла в их эффективной программной реализации;

- хотя разработанная система решает не все задачи сегментации, однако ситуации, не поддающиеся ей, могут быть описаны, и видно, что их можно решить в рамках разработанного подхода;

- метод монтажа и метод активизации омонимов лингвистически адекватны и универсальны (независимы от анализируемого ЕЯ). Адекватность понимается как соответствие модели процессора трем сформулированным принципам: описательному, объяснительному и эмулирующему;

- реализация системы ОИС позволила создать автоматическую синтаксическую сегментацию русского предложения без искусственных ограничений на анализ.

Основные положения диссертации опубликованы в следующих работах: 1. Ножов И.М. Проектирование сегментационного анализатора русского предложения. // КИИ-2002. Труды конференции - М.: Физматлит, 2002. Т.1. С. 212-222.

2. Кобзарева Т.Ю., Лахути Д.Г., Ножов И.М. Сегментация русского предложения. //КИИ-2000. Труды конференции-М.: Физматлит, 2000. Т.1. С. 339-344.

3. Кобзарева Т.Ю., Лахути Д.Г., Ножов И.М. Модель сегментации русского предложения. //Диалог'2001. Труды конференции - Аксакове, 2001. Т.2. С. 185194.

4. Кобзарева Т.Ю., Лахути Д.Г., Ножов ИМ. Сегментация русского предложения (поверхностно-синтаксический анализ как самостоятельный модуль анализа текста) //Материалы международной конференции НТИ-2000, ВИНИТИ, 2000. Т.2. С. 29-31.

5. Ножов ИМ Процессор автоматизированного морфологического анализа без словаря. Деревья и корреляция. //Диалог'2000. Труды конференции - Протвино, 2000. Т.2. С. 284-290.

6. Ножов И.М. Прикладной морфологический анализ без словаря. // КИИ-2000. Труды конференции - М.: Физматлит, 2000. Т. 1. С. 424-429.

Принято к исполнению 14/10/2003 Исполнено 15/10/2003

Заказ № 384 Тираж: 80 экз.

ООО «НАКРА ПРИНТ» ИНН 7727185283 Москва, Балаклавский пр-т, 20-2-93 (095) 318-40-68 \vww.autoreferat ш

У-ooJ-fi

»1614 t

I

i

ВВЕДЕНИЕ.

ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ ПОЛОЖЕНИЯ И ПРИКЛАДНЫЕ

СИСТЕМЫ.

I. Синтаксические аналогии.

II. Искусственный интеллект и естественный язык в аналитической философии.

III. Фундамент синтаксического анализа.

IV. Гипотеза глубины.

V. Head-driven Phrase Structure Grammar (HPSG).

VI. Link Grammar Parser (LinkParser).

VII. Сегментационный анализатор немецкого предложения (STP).

ГЛАВА 2. МОРФОЛОГИЧЕСКИЙ И ПРЕДСИНТАКСИЧЕСКИЙ

АНАЛИЗ.

I. Прикладной морфологический анализ без словаря.

II. Проектирование словарной морфологии.

III. Метод снятия морфологической омонимии (tagger).

IV. Методика выделения именных групп (np-grouper).

ГЛАВА 3. СЕГМЕНТАЦИОННЫЙ АНАЛИЗ РУССКОГО

ПРЕДЛОЖЕНИЯ.

I. Поверхностный синтаксический процессор группы Диалинг.

Общая схема действий анализа.93

Морфологические интерпретации.95

Внутрисегментный анализ.96

Синтаксические группы.97

Структура сегмента.98

Операция объединения сегментов.99

Операция вложения сегментов.99

Операция деления сегментов.100

Преобразование групп в бинарные отношения.101

Заключение.101

II. Сегментационный процессор группы ОИС.102

Введение.102

Стратегии.102

Морфологическая и синтаксическая омонимии.105

Граф синтагм.106

Граф сегментов.107

Сегментная проективность.108

Метод монтажа.110

Метод активизации омонимов.114

Общая схема реализации анализатора.117

Заключение.121

ГЛАВА 4. ПРИКЛАДНЫЕ ВОЗМОЖНОСТИ СИНТАКСИЧЕСКИХ ПРОЦЕССОРОВ В СИСТЕМАХ МАШИННОГО ПЕРЕВОДА И АВТОМАТИЧЕСКОЙ ОБРАБОТКИ ТЕКСТОВ.123

ЗАКЛЮЧЕНИЕ.127

ЛИТЕРАТУРА.128

ПРИЛОЖЕНИЕ 1. ПРИМЕРЫ РАБОТЫ МОРФОЛОГИЧЕСКИХ И ПРЕДСИНТАКСИЧЕСКИХ АНАЛИЗАТОРОВ.132

ПРИЛОЖЕНИЕ 2. ПРИМЕРЫ АНАЛИЗА СИНТАКСИЧЕСКИХ ПРОЦЕССОРОВ140

ВВЕДЕНИЕ

Синтаксический анализ является одним из наиболее исследованных направлений в теории computer science. Синтаксические анализаторы широко применяются в таких областях как создание компиляторов, проектирование интерфейсов баз данных, искусственный интеллект (ИИ), автоматическая обработка текстов (АОТ), в том числе для автоматизированных информационно-поисковых систем (АИПС, или «поисковых машин»), машинный перевод (МП), анализ химических формул и распознавание хромосом. Синтаксическим анализом (parsing) называется процесс структурирования линейной репрезентации в соответствии с заданной грамматикой [D.Grune, C.Jacobs, 1990]. Такое определение, являясь наиболее общим и абстрактным, позволяет охватить весь спектр приложений синтаксических методов. Техникой parsing называется вся совокупность существующих алгоритмов для решения задач синтаксического анализа. Техника parsing берет свое начало в формальных синтаксических теориях естественного языка (ЕЯ), моделирующих механизм распознавания человеком языковых структур. Несмотря на это, именно применение техники parsing в задачах автоматической обработки текста далеко не всегда бывает эффективным и дает положительный результат. Так, например, контекстно-свободные грамматики (context-free grammars) и аппарат конечных автоматов (finite-state automata) широко используются в системах морфологического анализа, снятия омонимии и выделения именных групп внутри предложения, но теряют свое прикладное значение в задачах сегментационного, полного синтаксического и семантического анализа, особенно для языков с относительно свободным порядком слов, каким является русский. Формальные математические модели и их программные динамические реализации не способны охватить всю сложность и многообразие языковой системы. Применение формализма для структурирования предложения естественного языка зачастую приводит к потере правильного синтаксического представления или комбинаторному взрыву, когда программа оказывается не в состоянии просчитать все возможные варианты структур. Лингвистически мотивированные причины такого "провала" - явление омонимии, длина связи между словами, сочинительные конструкции, нарушающие древесность графа, и сложность сегментной структуры предложения. Сфера действия методов распознавания и классификации объектов в лингвистических процессорах тоже сильно ограничена: скрытые модели Маркова удается применить только в узких контекстно-ограниченных задачах снятия морфологической омонимии [Xerox, 1999], нейронные сети используются в системах автоматического распознавания речи [С. Гладунов, О. Федяев, 2002], - такие модели, построенные на обучении и являющие собой альтернативный технике parsing подход, не имеют достаточной силы для отражения способности предложения естественного языка к неограниченному усложнению. Все эти обстоятельства позволили прикладной (компьютерной) лингвистике выделиться в отдельную область исследования и стать самостоятельно развивающейся ветвью искусственного интеллекта.

Далее в работе мы будем использовать понятие синтаксического анализа только применительно к предложению естественного языка.

Взаимодействие между лингвистикой и computer science началось еще полвека назад с возникновением теории Н. Хомского, развитием генеративизма и появлением электронно-вычислительных машин. Многие лингвистические идеи и концепции на протяжении последних десятилетий были заимствованы и воплощены в программировании, теоретической информатике и информационных системах. Наиболее яркими примерами такого заимствования могут служить базисный компонент порождающей грамматики Н. Хомского, который стал прототипом первых компиляторов искусственных языков, или выдвинутая М. Мински, исследователем в области ИИ, теория фреймов для представления реальных объектов в системах распознавания образов и естественных языков [Г. Буч, 2000], которая сыграла свою роль как в становлении объектно-ориентированного подхода в программировании, так и в семантических исследованиях языка, а наследование и полиморфизм -фундаментальные принципы объектно-ориентированного программирования -стали применяться в проектировании лексиконов [I. Sag, Т. Wasow, 1999].

Существует и удивительная связь между естественными и искусственными языками, которая заключается в закономерности эволюции языков. Первый опыт программирования в машинных кодах или на языках низкого уровня, к которым относится ассемблер, характеризуется скорее командным (императивным) стилем, где только упорядоченная последовательность операторов (команд) образует осмысленное действие, подобно тому как в языках с развитым словообразованием последовательная конкатенация грамматических аффиксов порождает слово, обладающее новым значением. С развитием таких языков как ALGOL-60 или COBOL усложняются синтаксические конструкции языка, появляется блочная структура программ. В следующем поколении языков, Pascal и С, текст программы становится похож на многопролетные лестницы, возможность описывать логику действий развернутыми синтаксическими конструкциями задает "ступенчатую" форму текста. Последнее поколение объектно-ориентированных языков (CLOS, Object Pascal, С++ и Java) стремятся к описанию ключевых абстракций предметной области; абстракции объединяются в библиотеки классов, а программы оперируют объектами этих классов, вызывая методы классов и используя свойства классов, тем самым упрощая синтаксические конструкции, но усложняя структуру объектов и семантические зависимости между ними; текст современный программы напоминает набор коротких четверостиший или деклараций, где каждая строка - обращение к объекту со своим значением и сложной семантикой. Нечто подобное наблюдается и в процессе эволюции естественных языков, когда постепенное вырождение словоизменительной парадигмы в морфологии приводит к ужесточению порядка слов в предложении и фиксации жестких синтаксических конструкций, а последующее усложнение семантики, за счет насыщения языка идиомами и фраземами, за счет появления более абстрактных понятий или новых значений старых слов или за счет пополнения общеупотребительной лексики из научных метаязыков, приводит к упрощению синтаксиса. Конечно, такой сценарий развития не является обязательным и предопределенным для многих языковых групп и семей, но такой путь эволюции до некоторой степени справедлив для италийской группы индоевропейских языков - от латыни к современному итальянскому и французскому - и для группы германских языков.

Разумеется, что такое сравнение программных и естественных языков является во многом условным, но одно можно утверждать с полной уверенностью: "изменчивость - глубинное и универсальное свойство" [С. Бурлак, С. Старостин, 2001] как естественных, так и искусственных языков. Очевидно то, что направления векторов развития систем естественного и искусственного языков совпадают, как и то, что история человеческого языка насчитывает тысячелетия, а искусственных пять десятилетий. Возможно, именно глобальность задачи и разнообразие явлений синтаксиса предложения помноженное на число существующих на земле языков с развитой письменностью оправдывает разработку новых моделей и алгоритмов, отличных от общепризнанных техник parsing или математических моделей, успешно используемых в других областях человеческого знания.

Теоретическая лингвистика и типологический опыт исследования языков создали необходимый описательный аппарат для компьютерного моделирования автоматического анализа текстов. Множество теоретических подходов можно разделить на два основных направления: формализм и функционализм. Формализм утверждает, что язык есть врожденная компонента человеческого мышления, которая может быть представлена в виде абстрактной модели на метаязыке формальной грамматики и не зависит от способов использования языка, а функционализм напротив полагает, что строение языка определяется его использованием [Я. Тестелец, 2001]. Исследования в формальной лингвистике можно тоже условно разделить на два подхода: построение универсальной грамматики, верной для всех существующих языков мира, и построение формальной модели, наиболее полно охватывающей все множество грамматических явлений конкретного языка. Н. Хомский стал родоначальником первого подхода и основателем школы генеративистов, самым ярким представителем второго подхода является И. Мельчук, автор модели "Смысл О Текст".

В задачах автоматической обработки текста (АОТ), как правило, используются концепции, разработанные в рамках формализма. Совмещая два подхода формальной лингвистики, программные модели являются лишь частичной реализацией теоретических исследований.

Работы по созданию синтаксического модуля велись еще в конце 60-ых годов, но вычислительная мощность компьютеров не позволяла реализовать сложные алгоритмы анализа в полном объеме. Упрощение алгоритмов и отказ от перебора омонимичных вариантов - компромисс, который приводил к низкой точности синтаксического анализа предложения. Сегодня, по-прежнему, задача автоматизированного анализа синтаксиса ЕЯ сводится к двум параметрам: качеству, определяемому парой «точность (уровень ошибок в построенных синтаксических структурах предложений), полнота (степень покрытия текста синтаксическими связями, или связность графа предложения)», и скорости, пока что недостаточной для ряда прикладных задач.

Ниже будут введены несколько определений понятий, связанных с синтаксическим анализом естественного языка, которые позже получат более точные формулировки. Линейной репрезентацией предложения естественного языка называется цепочка элементов, где каждый элемент является минимальной синтаксической единицей. Минимальная синтаксическая единица может быть словоформой или оператором с определенным набором характеристик. Оператором называется знак препинания или сочинительный союз. Обязательной составляющей такого набора у словоформы является ее морфологическая репрезентация, обычно состоящая из значения части речи и граммем, а у знака препинания или сочинительного союза - тип оператора (значение, выполняемой им грамматической функции). Таким образом, можно представить линейную репрезентацию предложения в виде цепочки морфологических репрезентаций словоформ и типов операторов.

Процессом структурирования линейной репрезентации предложения называется построение ориентированного графа синтагм и ориентированного графа сегментов.

Синтагма определяет бинарное синтаксическое отношение вида R(A, В), где А и В - словоформы, a R - тип синтаксического отношения, который соответствует имени синтагмы; А является хозяином, В - слугой, т. е. А управляет В. Таким образом, узлами графа синтагм является терминальные единицы. Связанность не является обязательным условием такого графа, так как синтагмы опираются только на морфологические репрезентации словоформы, линейный порядок предложения и, в некоторых случаях, на примитивную модель управления. На этом уровне анализа связи, для построения которых необходимо использовать сложную модель управления (предикатно-аргументную структуру) или семантическую информацию, могут не фиксироваться в графе синтагм.

Интуитивно сегмент можно определить как часть предложения (в частном случае целиком простое предложение), выделенную на письме знаками пунктуации и описывающую отдельную ситуацию; каждый такой сегмент имеет в качестве вершины явный предикат, выраженный в большинстве случаев финитной формой глагола, или «скрытый» предикат, который может быть выражен либо деепричастием, либо причастием, либо именем с семантической характеристикой действия; каждый такой предикат и задает ситуацию. Близкие по значению понятия в теоретической лингвистике - "предикация" и "элементарное предложение". В западной лингвистической традиции понятие сегмент эквивалентно термину клауза: "клаузой называется любая группа , в том числе и не предикативная, вершиной которой является глагол, а при отсутствии полнозначного глагола - связка или грамматический элемент, играющий роль связки" [Тестелец, 2001]. Например, любое придаточное предложение (или причастный и деепричастный обороты) в составе сложного является сегментом, равно как и простое предложение в составе сложного образует отдельный сегмент. Сегмент, в терминах системы составляющих, является фразовой категорией (подобно NP, VP, РР, etc. [I. Sag, Т. Wasow, 1999]) или нетерминальной единицей. Таким образом, узлами графа сегментов являются нетерминальные единицы.

Морфология, лексема, основа, окончание - понятия и термины, в последние годы ставшие общеупотребительными. Любой грамотный пользователь глобальной сети сможет "на пальцах" объяснить значение этих слов и преимущества поиска информации с использованием морфологии. На сегодняшний день только для русского языка существует несколько десятков известных систем морфологического анализа, число же программ английской морфологии в несколько раз больше. Следующим этапом в развитии направления искусственного интеллекта, занимающегося автоматической обработкой текста, является создание промышленной системы синтаксического анализа естественного языка.

Задача сегментации предложения является первой и, возможно, самой сложной компонентой полного синтаксического анализа. Целью сегментации является выделение и классификация сегментов в составе сложного предложения. Вторая компонента - построение внутрисегментных связей (графа синтагм) - исследована намного глубже и имеет успешные решения, экспериментально подтвержденные на анализе простых (односегментных) предложений. Основной упор в представляемой работе делается на разработку стратегий и методов автоматической системы сегментационного анализа предложения, хотя и предлагается ряд решений, связанных с внутрисегментным анализом терминальных единиц, а также методы моделирования морфологического анализа и снятия омонимии.

В последние десятилетия в странах Западной Европы, США и России проводятся чрезвычайно интересные и перспективные исследования по созданию систем автоматического синтаксического анализа для многих индоевропейских языков. Все попытки моделирования таких систем, как правило, происходят без предварительной сегментации предложения, что приводит к порождению в ходе анализа большого числа ложных синтаксических связей внутри сложного предложения и значительному снижению скорости анализа. Отсутствие в моделях отдельного сегментационного компонента можно считать одной из основных причин того, что до сих пор не создано эффективных систем синтаксического анализа для русского языка (РЯ) [Т. Кобзарева и др., 2000]. Сегментационный компонент может быть использован и в качестве самостоятельной системы при решении многих прикладных задач автоматической обработки текстов (ИПС, автоматическое реферирование, машинный перевод, etc.). Сегментация предложения, наряду с морфологическим анализом, должна стать базисной составляющей любой полной системы АОТ. Таким образом, создание компонента сегментации русского предложения является чрезвычайно актуальной задачей.

Синтаксический анализ - задача приближения. Любая синтаксическая теория должна обладать описательной и объяснительной силой. Это утверждение с некоторыми оговорками и дополнениями остается справедливым и для прикладных моделей. Описательная сила модели формулируется как максимально возможное покрытие грамматических явлений рассматриваемого языка. Объяснение в теоретической лингвистике заключается в рассмотрении вопроса о существовании в языке именно данных наблюдаемых фактов, а не других [Я. Тестелец, 2001]. В данной работе объяснение понимается в контексте ИИ: любая интеллектуальная система должна уметь обосновать каждый шаг принятых ею в ходе анализа решений [М. Boden, 1990]. Такой критерий подразумевает, что количество эвристик и вероятностно-статистических распределений в системе синтаксического анализа должно быть сведено к минимуму. Существует и третий, не менее важный критерий прикладной модели - эмулирующий принцип построения алгоритмов, - который заключается в способности лингвистического процессора к воспроизведению интуиции и схемы рассуждений человека в процессе изучения и восприятия языка.

Идеальная модель лингвистического процессора состоит из четырех основных анализаторов: графематического (внешнее представление текста), морфологического, синтаксического и семантического. В данном случае мы ограничимся рассмотрением трехсоставного процессора без семантического анализатора.

Целью настоящей работы было создать экспериментальную систему автоматической сегментации русского предложения, демонстрирующую возможность эффективного - с точки зрения качества и скорости анализа -решения этой задачи как ключевого этапа полного автоматического синтаксического анализа русского текста. Основной решаемой проблемой была при этом разработка методов автоматической сегментации предложения и способов программирования, позволяющих минимальными силами решить поставленную задачу применительно к текстам произвольной (или почти произвольной) синтаксической сложности, а также построение прикладной модели лингвистического процессора, удовлетворяющего описательному, объяснительному и эмулирующему принципам.

Предметом исследования является структура сложного предложения русского языка и законы ее построения.

Работа построена на описании и сравнении решений и результатов двух систем синтаксического анализа, использующих компонент сегментации русского предложения.

Синтаксический процессор группы ДИАЛИНГ был создан в рамках проекта русско-английского машинного перевода (1999-2001). Фундаментом для исследований группы ДИАЛИНГ послужила система французско-русского автоматического перевода (ФРАП), разработанная в ВЦП совместно с МГПИИЯ им. М. Тореза в 1976-86 гг., и система анализа политических текстов (ПОЛИТЕКСТ), разработанная в Центре информационных исследований совместно с ВЦ ИСК РАН в 1991-97 гг [Н. Леонтьева, 1995].

Синтаксический анализатор научный группы Отделения интеллектуальных систем (ОИС) Института Лингвистики РГГУ (Д.Г. Лахути, Т.Ю. Кобзарева, И.М. Ножов) был создан в 1999-2003 гг. Предлагаемый проект продолжает развиваться и содержит наиболее полную реализацию идей сегментации русского предложения. Базисом для проводимых исследований послужила модель автоматического поверхностно-синтаксического анализа русского предложения, разработка которой была начата еще в 1971 г. в

Информэлектро в секторе (затем отделе) Д.Г.Лахути группой лингвистов под руководством Г. А.Лесскиса.

Также в работе предложены альтернативные подходы к проектированию некоторых составляющих лингвистического процессора, разработанные автором диссертации в НТЦ "Система" (1997-1998 гг.) и в исследовательском отделе компании Inxight, Software Inc. (2002-2003 гг.).

Методы исследования:

• Создание и пополнение лексиконов, содержащих необходимую для анализа морфологическую и грамматическую информацию;

• Разработка лингвистических стратегий и правил, отвечающих синтаксическим законам языка; изучение множества грамматических явлений, характерных для русского языка; поиск (с использованием конкорданса) случаев применения описываемых грамматических конструкций в корпусе текстов;

• Проектирование общей схемы лингвистического процессора и прикладной модели синтаксического анализа;

• Разработка алгоритмов порождения и перебора структурных вариантов предложения, связанных с явлением морфологической и синтаксической омонимии естественного языка;

• Создание динамических структур данных для представления и хранения синтаксической информации и программное моделирование процесса анализа на ЭВМ;

• Создание отладочного массива предложений, охватывающего все множество отраженных в модели грамматических явлений, и тестирование системы на пространстве реальных текстов.

• Оценка эффективности применения предложенных методов в системах АОТ или МТ.

Научная новизна работы состоит в том, что предложенные алгоритмы порождения структурных вариантов предложения позволили создать успешную модель лингвистического процессора и отказаться от декартова произведения омонимов, проверить работоспособность оригинальных грамматических стратегий анализа и реализовать методы автоматической сегментации без искусственного ограничения на перебор структурных вариантов, обусловленных морфологической и синтаксической омонимией, и без ограничения на глубину рекурсии сегментов и длину предложения.

Практическая значимость работы определяется программными реализациями анализаторов, созданных на базе разработанных методов и стратегий и получивших практическое применение в различных системах автоматической обработки информации. В диссертации приведены примеры внедрения программ.

В процессе работы над диссертацией автором были получены следующие научные результаты:

1. Разработаны два метода автоматического синтаксического анализа предложения: метод активизации омонимов и рекурсивный метод монтажа разрывных сегментов.

2. Построена прикладная модель синтаксического анализатора, удовлетворяющего описательному, объяснительному и эмулирующему принципам, и позволяющая вести анализ параллельно: "снизу вверх" и "сверху вниз".

3. Отлажены грамматические стратегии сегментации и доказана их работоспособность.

4. Программно реализованы, совместно с другими разработчиками, две системы: промышленный синтаксический процессор группы "Диалинг" и экспериментальная сегментационный анализатор группы ОИС под руководством Д.Г. Лахути.

5. В процессе проводимых исследований и изучения существующих подходов к проектированию лингвистических процессоров автором, совместно с другими исполнителями, были разработаны и внедрены следующие прикладные модули: бессловарный морфологический анализ (НТЦ "Система") и Russian LinguistX Platform 3.5 (Inxight, Software Inc.), включающая в себя tokenizer, stemmer, tagger и np-grouper русского языка.

Апробация работы. Основные выводы и научные результаты диссертационной работы докладывались на международных конференциях Диалог в 2000 и 2001 гг., на национальных конференциях по искусственному интеллекту КИИ в 2000 и 2002 гг. и на научно-технической конференции ВИНИТИ в 2000 г. По теме диссертации автором опубликовано 6 работ. Сдана в печать одна статья.

Структура и объем работы: Диссертация состоит из введения, четырех глав, заключения, списка литературы из 53 наименований и двух приложений. Общий объем работы -148 страниц, основной текст - 131 страница.

ЗАКЛЮЧЕНИЕ

Сформулируем основные результаты исследования:

- автоматическая синтаксическая система ОИС представляет собой не законченный промышленный продукт, а экспериментальную систему для отработки лингвистических решений;

- ограничения на тексты, обрабатываемые системой, связаны с морфологическим или даже графематическим этапом анализа (отсутствие нелинейных элементов, предложений, состоящих из нескольких абзацев, и т.п.);

- в основу работы положены лингвистические алгоритмы, разработанные Т.Ю.Кобзаревой [Т.Ю.Кобзарева, 2002]; задача состояла в их эффективной программной реализации;

- хотя разработанная система решает не все задачи сегментации, однако ситуации, не поддающиеся ей, могут быть описаны, и видно, что их можно решить в рамках разработанного подхода;

- метод монтажа и метод активизации омонимов лингвистически адекватны и универсальны (независимы от анализируемого ЕЯ). Адекватность понимается как соответствие модели процессора трем сформулированным принципам: описательному, объяснительному и эмулирующему;

- реализация системы ОИС позволила создать автоматическую синтаксическую сегментацию русского предложения без искусственных ограничений на анализ;

- в процессе проведенных исследований доведены до промышленного использования программные реализации трех прикладных систем, морфологический анализатор без словаря (НТЦ "Система"), русскоязычная версия LinguistX Platform 3.5 (Inxight, Software Inc.) и синтаксический процессор Диалинг.

1. Г. Буч, 2000. Г. Буч. Объектно-ориентированный анализ и проектирование. М.: «Издательство Бином», 2000.

2. Sag, Т. Wasow, 1999. Ivan A. Sag, Thomas Wasow. Syntactic Theory: A Formal Introduction. Stanford University, 1999

3. С. Бурлак, С. Старостин, 2001. С. А. Бурлак, С. А. Старостин. Введение в лингвистическую компаративистику. Эдиториал УРСС, М., 2001. М. Boden, 1990] М. Boden. Artificial intelligence and images of man. // Perspectives From Artificial Intelligence, 1990.

4. Xerox, 1999. Examples of Networks and Regular Expressions. // www. xrce. xerox. com/research

5. И. Мельчук, 1999. И. А. Мельчук. Опыт теории лингвистических моделей «Смысл о Текст».-М., 1999.

6. Ф. де Соссюр, 1999. Ф. де Соссюр. Курс общей лингвистики. М., 1999.

7. S. Оереп, К. Netter, 1997. S. Оереп, К. Netter. Test Suites for Natural Language

8. Processing. // Linguistic Databases, CSLI Lecture Notes #77.

9. D. Sleator, D. Temperley, 1991. D. Sleator, D. Temperley. Parsing English with a Link Grammar. CMU-CS-91-196, School of Computer Science, Carnegie Mellon University, Pittsburg, 1991.

10. D. Grinberg, J. Lafferty, 1995. D. Grinberg, J. Lafferty. A robust parsing algorithm for Link Grammars. CMU-CS-95-125, School of Computer Science, Carnegie Mellon University, Pittsburg, 1995.

11. XRCE MLTT, 1995. Application of Finite-State Networks. // www. xrce. xerox, com/research

12. H. Леонтьева, 1995. H. H. Леонтьева. «Политекст»: информационный анализ политических текстов. // НТИ, Сер.2, 1995, №4.

13. Я. Тестелец, 2001. Я. Г. Тестелец. Введение в общий синтаксис. М., РГГУ, 2001. С. Эйзенштейн, 2000] С. М. Эйзенштейн. Монтаж. - М., 2000.

14. X. Дрейфус, С. Дрейфус, 1998. Дрейфус X., Дрейфус С. Создание сознания vs моделирование мозга. //Аналитическая философия: Становление и развитие. М., 1998.

15. Д. Серл, 1998. Серл Д. Мозг, сознание и программы. //Аналитическая философия: Становление и развитие. М., 1998.

16. X. Патнэм, 1999. Патнэм X. Философия сознания. //М., 1999.

17. ВИНИТИ, 1990. Итоги науки и техники: физические и математические модели нейронных сетей, том 1, М., изд. ВИНИТИ, 1990.

18. А. Кибрик, 2001. Кибрик А.Е. Очерки по общим и прикладным вопросам языкознания. УРСС, М., 2001.

19. Э. Сепир, 1993. Э. Сепир. Избранные труды по языкознанию и культорологии. //М., 1993.

20. В. Ингве, 1965. В. Ингве. Гипотеза глубины. //Новое в лингвистике. Вып. 4, М., 1965 -с. 126.

21. Б. Страуструп, 1999. Б. Страуструп. Язык программирования С++. М., 1999. Н.А.Еськова, И.Г.Бидер и др.] Н.А.Еськова, И.Г.Бидер и др. Формальная модель русской морфологии.

22. С.О.Шереметьева, С.Ниренбург, 1996. Эмпирическое моделирование ввычислительной морфологии. //НТИ, №7, 1996.

23. Г.Г.Белоногова, 1984. Г.Г.Белоногова. Итоги науки и техники. Серия "Информатика", т.№8,1984г.

24. J. Goldsmith, 1999. J. Goldsmith. Unsupervised Learning of the Morphology of a Natural Language. //University of Chicago, 1998.

25. А.Зализняк, 1980. Зализняк A.A. Грамматический словарь русского языка М.: Русский язык, 1980 г.

26. Finite-State Network, 1995. Finite-State Network. // Xerox Research Center, Grenoble, www.xrce.xerox.com/research

27. Ж.Г.Аношкина, 1995. Ж.Г.Аношкина. Морфологический процессор русского языка. //Альманах «Говор», Сыктывкар, 1995, с.17-23.

28. Ч. Хоккетт, 1961. Ч. Хоккетт. Грамматика для слушающего. // Новое в лингвистике. Вып. 4,М., 1965-с. 139.

29. S. Oepen, J. Caroll, 2000. S. Oepen, J. Caroll. Parser engineering and performance profiling. // Journal of Natural Language Engineering # 6 (1), 2000.

30. Т. Кормен и др., 2001. Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы, построение и анализ. М., МЦНМО, 2001.

31. G. Neumann, J. Piskorski, 2001. G. Neumann, J. Piskorski. A Shallow Text Processing Core Engine. DFKI, Saarbruecken, 2001.

32. Дж. Фридл, 2001. Дж. Фридл. Регулярные выражения. СПб., 2001. А. Сокирко, 2001] А. В. Сокирко. Семантические словари в автоматической обработке текста (по материалам системы Диалинг). - Автореф. дисс. к.т.н. - М., 2001.

33. Д. Панкратов и др., 2000. Д. В. Панкратов, Л. М. Гершензон, И. М. Ножов. Описание фрагментации и синтаксического анализа в системе Диалинг. // Техническая документация, www.aot.ru, 2000.

34. А. Белоусов, С. Ткачев, 2001. А. И. Белоусов, С. Б. Ткачев. Дискретная математика, -т. 19, М.,2001.

35. Т. Кобзарева и др., 2000. Т.Ю. Кобзарева, Д.Г. Лахути, И.М. Ножов. Сегментация русского предложения. // КИИ-2000. Труды конференции М.: Физматлит, 2000. Т.1. С. 339-344.

36. Т. Кобзарева и др., 2001. Т.Ю. Кобзарева, Д.Г. Лахути, И.М. Ножов. Модель сегментации русского предложения. // Диалог'2001. Труды конференции -Аксакове, 2001. Т.2. С. 185-194.

37. Н. Вирт, 2001. Н. Вирт. Алгоритмы и структуры данных. СПб., 2001. И. Ножов, 2002] Ножов И.М. Синтаксический анализ. //Компьютерра, № 21 (446), 2002.