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

Дроздов Вячеслав Вадимович

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

Специальность 05.13.12 Системы автоматизации проектирования (информатика) (технические науки)

Автореферат

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

о з 023 ¿¡Л

Москва - 2010

4853696

Работа выполнена на кафедре «Информационные технологии и автоматизированные системы» Московского государственного института электроники и математики (технический университет)

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

кандидат технических наук, доцент Клышинский Эдуард Станиславович

Официальные оппоненты:

доктор технических наук, доцент Никольский Сергей Николаевич

доктор физико-математических наук, доцент Большакова Елена Игоревна

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

Учреждение Российской Академии Наук Институт прикладной математики им. М.В. Келдыша РАН

Защита состоится «15» февраля 2011 г. в «12» часов на заседании диссертационного совета Д 212.133.03 при Московском государственном институте электроники и математики (техническом университете) по адресу: 109028, г. Москва, Б. Трехсвятительский пер., д.З.

С диссертацией можно ознакомиться в библиотеке Московского государственного института электроники и математики (технический университет)

Ученый секретарь

д.т.н., доцент

диссертационного совета

Леохин Ю.Л

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В ходе своего существования крупные предприятия формируют большой архив, содержащий в себе различного рода документацию, связанную с их функционированием. К подобным документам относятся не только результаты официального документооборота (приказы, распоряжения и пр.), но и техническая документация по выполняемым и выполненным проектам: технические отчеты, проектная документация, планы и так далее. В последнее время довольно широкое распространение получили системы ILM (Information Lifecycle Management) и PDM (Product Data Management). ILM охватывает все процессы управления размещением, хранением, распределением, миграцией, архивированием и удалением данных в инфраструктуре предприятия. Задачей ILM является хранение документов, и обеспечение оптимального времени доступа к ним со стороны пользователя и его систем.

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

чертеж. Конструкторская

спецификация изделий

Модель продукта

Конструкция Технология

Техпроцесс, нормы расхода материалов, нормы времени

Справочник конструкторской номенклатуры

Конструкторский состав изделия

Конструкторская Технологическ. документация документация

Планирование, управление произв.

Номенклатура Спецификация Маршрут Список отступлений от норм РЦ

справочник материалов

нормы расхода материалов

Техпроцессы, маршруты

Рис. 1. Общая схема интеграции CAD/CAM, PDM и ERP систем

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

проектирования и производства, спецификации, нормативные документы, программы для станков с числовым программным управлением, результаты анализа, эксплуатационные данные и многое другое. Поскольку при их создании все чаще используются компьютерные средства, то поиск ответа на вопросы: «Существуют ли необходимые данные?», «Где они находятся?», «Являются ли они актуальными?» - не всегда представляется тривиальным.

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

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

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

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

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

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

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

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

Для достижения поставленной цели необходимо решить следующие

задачи.

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

• Разработать формат деревьев синтаксического подчинения, пригодный для программной реализации метода автоматизированной генерации правил, на основе деревьев синтаксического подчинения А.В.Гладкого.

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

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

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

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

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

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

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

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

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

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

Автором самостоятельно спроектирована и реализована подсистема генерации новых правил для системы машинного перевода «Кросслейтор», разрабатываемой в ИПМ им. М.В. Келдыша. Проведенные испытания показали эффективность применения предложенных решений.

Достоверность научных положений и выводов подтверждается:

• корректностью использования математического аппарата и методов испытаний;

• апробацией и публикациями основных результатов исследований;

• результатами внедрения разработанного метода и рекомендаций в практику.

Реализация и внедрение результатов. Алгоритмы и методы, описанные в данной работе, реализованы автором в компьютерной программе. Программа создавалась как с целью апробации и совершенствования разрабатываемых методов и алгоритмов, так и с целью практического использования в машинном переводчике «Кросслейтор», разрабатываемом в ИПМ им. М.В. Келдыша РАН, и при выполнении гос. контракта П-261 в рамках ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013 гг., заключенного между Министерством образования и науки и МИЭМ.

Апробация работы и публикации. Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах:

• «Ежегодная научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ», МИЭМ, 19 февраля - 29 февраля 2008.

• «Ежегодная научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ», МИЭМ, 24 февраля - 05 марта 2009.

• «Горизонты прикладной лингвистики и лингвистических технологий», Мегалинг 2009, Украина, Киев, 20- 27 сентября 2009.

• «Ежегодная научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ», МИЭМ, 17 февраля - 01 марта 2010.

• «Новые информационные технологии в автоматизированных системах», МИЭМ, 25 марта 2010 года.

Основное содержание диссертационной работы и ее результатов отражено в следующих научных и научно-технических работах автора: Всего автором опубликовано 8 научных работ из них 1 в журнале из перечня ВАК.

На защиту выносятся следующие основные положения:

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

• Алгоритм поиска неразобранной части предложения. То есть такой минимальной части (или частей) предложения, убрав которую, можно будет разобрать предложение, имеющимися в базе правилами.

• Алгоритм поиска максимального фрагмента неразобранного предложения, которое удается разобрать имеющимися в базе правилами.

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

Структура работы. Работа состоит из введения, четырех глав с выводами, заключения, списка использованной литературы и приложения. Основная часть работы изложена на 117 страницах машинописного текста, содержит 1 таблицу и 61 рисунок. Список литературы включает 100 наименований.

СОДЕРЖАНИЕ РАБОТЫ Во введении дается обоснование актуальности темы диссертационной работы, определяется направленность исследования, формулируются цели и задачи исследования, определяются научная новизна и практическая значимость результатов.

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

Правильность синтаксического анализа очень важна для задач обработки текстов на естественных языках. Можно выделить два основных направления развития технологии синтаксического анализа: традиционная технология, основанная на применении правил (генеративистские лингвистические теории основывающиеся (пусть даже частично) на контекстно-свободных грамматиках), и технология синтаксического анализа, основанная на взаимоотношениях слов. В каждом из этих направлений есть свои подклассы теорий синтаксического анализа, зачастую довольно сильно отличающиеся в пределах одного и того же направления. Наличие большого числа теорий объясняется очень высокой сложностью естественного языка. На данном этапе нет теоретических построений для описания ЕЯ, обладающих требуемой степенью полноты и формализации. Иными словами, не существует ни идеальной теории для компьютерной лингвистики, ни идеальных средств ее реализации. По этой причине невозможно создать идеальную инструментальную систему для обработки ЕЯ, что приводит к изобилию существующих систем. Представленный в первой главе обзор не претендует на полноту описания всех существующих методов синтаксического анализа, так как есть более полусотни разных вариаций. Основная цель приведенного обзора - показать, с какими проблемами для своего дальнейшего развития сталкиваются одни из наиболее известных моделей. Все рассмотренные методы синтаксического анализа имеют свои достоинства и недостатки. Общим среди них является то, что они в той или иной форме при проведении синтаксического анализа используют некоторые знания о естественном языке. Это может быть статистика сочетаемости и встречаемости слова и частей речи, как в методе п-грамм, Толково-комбинаторный словарь, как в модели «Смысл<-»Текст» или правила, как в А ТЫ. Важность этих знаний трудно переоценить. Какой бы совершенной ни была теория, без представления о конкретном языке синтаксический анализ невозможен. Зачастую именно простота получения подобных знаний имеет решающее значение для выработки на основе теории конкретных практических реализаций. Например, в методе п-грамм такие знания получить неизмеримо более легко, нежели чем создать полный Толково-комбинаторный словарь для модели «Смысл<->Текст». В результате модель п-грамм активно практически используется на сегодняшний день, а модель «Смысл<-»Текст» - нет. Можно даже сказать, что столь активное использование

9

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

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

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

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

10

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

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

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

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

Существует два типа выделения критериев:

• Интуитивный.

• Формальный.

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

сформулированными так четко, чтобы в них можно было усмотреть только один смысл.

На основании интуиции можно сделать несколько важных выводов:

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

• Синтаксические отношения часто возникают между семантически связанными словами.

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

Синтаксические отношения обладают следующими важными

свойствами:

• Антисимметричность.

® Антитранзитивность.

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

• Условие связности.

• Условие, которое можно назвать принципом единственности корневого узла.

• Условие - принцип единственности одной родительской вершины.

• Условие - принцип запрета на контур.

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

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

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

Дерево подчинения для предложения «В декабре выпал первый снег» будет иметь следующий вид:

Рис. 2. Пример дерева подчинения для предложения «В декабре выпал первый

снег»

Итак, моделью предложения будет являться дерево синтаксического подчинения (оно же дерево зависимостей). Дуга в дереве подчинения - это синтаксическая зависимость.

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

Правила разбора хранятся в отдельной базе. Для базы определяется набор правил, являющихся входными (те правила, с которых начинается рекурсивный спуск). Правила записываются в виде модифицированной Бэкусовской нормальной формы.

Формат правил следующий.

<имя правила>::= <случай> | <случай>"|"<имя правила>

<случай>: := <символ>|<символ><случай>

<символ>::= "["<id>":" <id_parent>";" <part>";" <params>"]" +"<node_name>"+" | "{"<id>":" <id_parent>";" " ' " <infi> " " <part>";"<params>"} +"<node_narae>"+" | "<" <id>":" <id_parent> ";" <name_rule> ";" <params>">"

<params>::= <param> | <paramxparams> <param>::= <name_param> <id> <vl> <vl>::= "+" | "#" <value> | "-" <value> | <value>

Здесь part - название части речи, inf - нормальная форма слова, name rule - имя правила, node_name - роль слова в предложении для образуемой вершины, id - идентификатор вершины, id_parent - идентификатор вершины-родителя (при отсутствии принимает пустое значение), name jjaram -название параметра, value - значение параметра.

• Если параметр включает символ "+", то его значение должно совпадать с уже имеющимся запомненным параметром, имеющим то же название и идентификатор.

• Если параметр включает символ "-", то его значение не должно совпадать с уже имеющимся запомненным параметром, имеющим то же название и идентификатор.

• Если параметр включает символ "#", то данный параметр должен быть создан заново, при этом его значение должно совпадать с уже имеющимся запомненным параметром, имеющим то же название и идентификатор (если такой присутствует).

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

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

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

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

и

| человек |

| подошел |

I подошел |

| человек | | к |

а___,_

ну | | и | | двери |

окну | | и | | двери

| открытому |

| открытому |

Рис. 3. Деревья сиитаксического подчинения с однородным членами при выборе корнем дерева: слева - подлежащего, справа - сказуемого

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

• Если к слову относится частица, то она в дереве подчинения должна быть родителем этого слова.

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

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

Рис. 4. Древесное представление предложения с необходимыми для генерации правил данными Узел О нашего дерева подчинения - это пятерка вида <\у,р,г,п,т>, где V/ -слово в предложении (содержит лексические параметры, часть речи), р - номер слова в предложении , г - роль слова в предложении, п - порядковый номер слова, от которого зависит текущее (если зависит от вышестоящего по дереву подчинения, то параметр пуст), т - порядковый номер предлога, который относится к текущему слову (используется при согласовании).

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

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

• Вершина, содержащая название правила, по которому шел разбор.

Например, «Разбор по правилу ЗЕМТОВ.! с позиции 0. Продукций 2».

Обозначим эту вершину как вершину первого типа Н. Вершина первого типа - это четверка <г,р,п,&>, где г - правило, по которому проходил разбор, р - позиция, с которой проходил разбор, п - количество продукций, б - успешность разбора по этому правилу.

• Вершина, содержащая описание продукции, по которой шел разбор (ее порядковый номер соответствует ее порядковому номеру в правиле). Например, «Начат разбор по продукции с позиции 0. Символов 1». Обозначим эту вершину как вершину второго типа Р. Вершина второго типа - это тройка вида <п1,р,5>, где п1-номер продукции в правиле, по которому идет разбор, р - позиция, с которой проходил разбор, в -успешность разбора по этой продукции

• Лист, содержащий номер терминала, с которым проходило сравнение. Например, «Терминал успешно сравнился с символом в позиции 0». Обозначим лист дерева разбора как Ь. Лист дерева разбора Ь - это пара вида <1,з>, где I - номер терминала в П, с которым проходило сравнение, а б - результат этого сравнения.

Формат дерева Типы узлов

Рис. 5. Формат дерева журнала разбора

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

Метод автоматизированной генерации нового правила состоит в следующем.

Шаг 1. Поиск предложения П', которое можно разобрать имеющимися в базе правилами и все точки которого принадлежат П.

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

Р' - Журнал разбора П'

I ноеому |

Рис. 6. Дерево подчинения £>' предложения П' и дерево подчинения О предложения П 18

Шаг 2. Выбор неразобранного поддерева для построения нового правила.

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

Пусть И" с О (О-дерево синтаксического подчинения для П) -найденное неразобранное поддерево. В дереве подчинения О есть Л" - вершина поддерева О" и Я' - успешно разобранная вершина, потомком или братом которой является Я". Для случая однородных членов может понадобиться создание фиктивной вершины.

Рис. 7. Неразобранное поддерево £>"

В этом случае для узлов «,» , «а», «не» необходимо создать фиктивную вершину, которая и будет Я". В случае на рисунке Я" будет являться братом для Я'. Но для некоторых случаев не удается, выполнив подобные элементарные преобразования, интуитивно построить деревья подчинения. Например, для предложения: «Мальчики и девочки пели и плясали». Для таких конструкций с сочинительными союзами на текущий момент создавать новые правила невозможно.

Шаг 3. Поиск в журнале разбора предложения П' листьев, по которым был успешно разобран узел Я'.

Следующим шагом для создания правила будет поиск в лесе деревьев разбора предложения ГГ листьев, по которым был успешно разобран узел Я', т.е.

Ь=(1,з)-лист е Б', такой что I равен порядковому номеру Я' в X' и в в установлен флаг успешности разбора.

Найдя эти вершины, получим непустое конечное множество. М={{Ь1)Р1,Н|},....,{Ь,,Р|,Н|},...., {Ц,Р„,Н„}}, где п>=1,

- лист дерева разбора е Р' Р, - вершина второго типа дерева разбора б И' такая, что она является родительской для листа

Н; - вершина первого типа дерева разбора е Р' такая, что она является родительской для вершины Р,.

Рис. 8. Фрагмент леса разбора

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

Шаг 4. Формирование нового правила с использованием информации, содержащейся в полученном множестве.

Правило, по которому был разбор вершины Я', хранится в параметре г вершины первого типа Н. Номер продукции в правиле находится в параметре п1 вершины второго типа Р, С помощью этих данных однозначно можем найти во множестве правил разбора нашей базы то правило, по которому прошел успешный разбор вершины Я'. Создаваемое нами новое правило будет иметь своим родительским правилом именно его. Имея номер продукции в правиле, возьмем саму продукцию. Она послужит частью нового создаваемого правила, так как вершина, разобранная с помощью этой продукции, является родителем или братом для неразобранной вершины.

Если неразобранная вершина Я" является потомком для вершины Я', то будут сгенерированы два новых правила. Первое правило будет содержать продукцию, по которой был проведен успешный разбор вершины. Второе правило будет содержать новую сгенерированную продукцию.

Также при создании нового правила следует учесть наличие между главным и зависимым словом предлогов, частиц, знаков препинания, которые не имеют согласования. А, значит, их надо вносить в создаваемое правило, но согласовывать слова по дереву подчинения придется не просто, беря первого потомка, а выбирать потомка для согласования, учитывая его роль в предложении и часть речи. После создания двух новых правил, надо создать и новую продукцию в правиле, по которому была разобрана вершина Я'.

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

При создании новых правил для случая, когда неразобранная вершина Я" является братом вершины Я1, уже имеем правило, описывающее один из однородных. Это связано с тем, что проход при составлении предложения П' осуществляется сначала в глубину. Как и в случае создания правила для потомка, необходимо создать правило для неразобранного однородного. Также необходимо создать правило, описывающее саму структуру однородных членов, включив в него знаки препинания и союзы, если они есть в структуре

предложения. Именно название этого правила будет использоваться в сформированной продукции для правила, по которому прошел разбор вершины Я'.

Упрощенно эти два случая создания новых правил можно представить следующим образом:

Два случая создания новых правил (курсивом выделены новые созданные правила и продукции):

• Вершина Я" неразобранного поддерева О" - потомок вершина Я' <имя правила 1>:=<имя правила 2>|<имя правила 3>

\<имя правила 4> <имя правила 5>

<имя правила 4>:=<имя правила 2>

<имя правила 5>:=<описание терминала вершины /?">

Здесь следует прояснить, почему не очень хорошим является следующий вариант создания правил:

<имя правила 1>:=<имя правила 2>|<имя правила 3>

| <имя правила 2> <имя правила 5>

<имя правила 5>:=<описание терминала вершины Я">

<Имя правила 2> - это обычно продукция, содержащая описание терминального символа, по которому разобралась удачная вершина Я'. Если генерировать правила по схеме <правило 2хправило 5>, то в дальнейшем, когда будет расширяться группа, зависимая от терминала, который разбирается по <правилу 2>, придется это правило делить и выносить вниз. Это необходимо, чтобы <правило 5> относилось не только к терминалу <правила 2>, но и к группе слов, зависимых от него.

• Вершина Я" неразобранного поддерева Э" - брат вершина Я'

<имя правила 1>:=<имя правила 2>|<имя правила 3> |<имя правила 6>

<имя правила 4>:=<имя правила 2>

<имя правила 5>:=<описапие терминала вершины Я">

<имя правила 6>:=<имя правила 4> <зпак> <союз> <имя правила 5>

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

Например, предложение «Инженер увидел компьютер старый, стоящий на столе». Дерево синтаксического подчинения для него, с учетом требований разрабатываемого метода, будет иметь вид: | инженер

увидел

компьютер

старый

стоящии

столе

Рис. 9. Дерево подчинения для предложения «Инженер подошел к компьютеру старому, стоящему на столе»

Причастный оборот «, стоящий на столе» зависит от существительного «компьютер». Эта зависимость задается через параметр п узла О дерева подчинения. Но по базе правил причастный оборот должен зависеть не просто от существительного, а от группы «существительное + его зависимые слова». Для этого при генерации новых правил находим правило, описывающее эту группу, и считаем именно это правило, более верхнего уровня, тем правилом Я', к которому идет добавление нового неразобранного случая.

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

Шаг 5. Проверка есть ли в базе правил правило, описывающее оставшуюся неразобранной часть поддерева.

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

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

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

В заключении перечислены основные научные результаты, полученные при решении поставленных задач.

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

24

• Для некоторых предложения не удается построить «естественные» деревья синтаксического подчинения, соответственно, на данный момент для таких предложений не удается и создавать правила.

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

Перспективы развития метода:

• Устранить взаимодействие программы с лингвистом на этапе согласования параметров, за счет использования статистики по многим деревьям.

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

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

Публикации по теме диссертации:

• Дроздов В.В., Клышинский Э.С. О повышении качества синтаксического анализа текста за счет обучения с учителем // Журнал «Качество Инновации Образование», №10, 2010. С. 45-52

• Drozdov V.V. Automatic Generation of Rules for a System that Uses a Grammatical Approach to Syntactic Analysis // Automatic Documentation and Mathematical Linguistics, No. 3, Vol. 44, 2010, pp. 121-126

• Дроздов B.B. Обзор и сравнение статистических и грамматических методов синтаксического анализа // Материалы тринадцатого научно-

практического семинара «Новые информационные технологии в автоматизированных системах»,- М. МИЭМ, 2010. С. 75-83 Дроздов В.В. Автоматическая генерация правил для системы, использующей грамматический подход к синтаксическому анализу // Журнал «Научно-техническая информация», № 5, сер. 2, 2010. С. 19-23 Дроздов В.В. Обзор методов синтаксического анализа // Материалы международной научной конференции Мегалинг, Киев, 2009. С. 59 Дроздов В.В., Клышинский Э.С. Метод автоматической генерации правил синтаксического анализа для грамматик в БНФ И Материалы двенадцатого научно-практического семинара «Новые информационные технологии в автоматизированных системах»,- М. МИЭМ, 2009. С. 149153

Дроздов В.В. Автоматическая генерация правил для грамматик естественных языков // Материалы ежегодной научно-технической конференции студентов, аспирантов и молодых специалистов МИЭМ. -М. МИЭМ, 2009. С. 63-64

Дроздов В.В. Автоматизированная система генерации правил // Материалы ежегодной научно-технической конференции студентов, аспирантов и молодых специалистов МИЭМ- М. МИЭМ, 2008. С. 136137

Формат 60x90/16. Заказ 984. Тираж 100 экз.

Печать офсетная. Бумага для множительных аппаратов.

Отпечатано в ООО "ФЭД+", Москва, ул. Кедрова, д. 15, тел. 774-26-96

Введение.

Глава 1. Обзор методов синтаксического анализа.

1.1. Деревья синтаксического подчинения.

1.2. Основные направления развития синтаксического анализа.

1.3. Методы синтаксического анализа, основанные на связях слов.

1.3.1. Модель п-грамм.

1.3.2. Модель грамматики связей.

1.4. Методы синтаксического анализа, основанные на грамматиках.

1.4.1. Расширенные сети переходов.

1.4.2. Модель «Смысл «-»Текст».

1.4.3. Семантическая грамматика.

1.4.4. Системно-функциональная грамматика.

1.4.5. Лексико-функциональная грамматика.

1.4.6. HPSG.

1.5. Методы обучения.

1.6. Выводы.

Глава 2. Формальная основа метода автоматизированной генерации правил.

2.1. Метод и журнал синтаксического разбора.

2.2. Модифицированные деревья синтаксического подчинения.

2.3. Выводы.

Глава 3. Алгоритмы и метод автоматизированной генерации правил.

3.1. Основные алгоритмы.

3.2. Метод автоматизированной генерации правил.

3.3. Ограничения метода.

3.4. Выводы.

Глава 4. Практическая реализация разработанного метода.

4.1. Подсистема генерации новых правил.

4.2. Примеры генерации новых правил.

4.3. Оценка эффективности метода.

4.4. Выводы.

В ходе своего существования крупные предприятия формируют большой архив, содержащий в себе различного рода документацию, связанную с их функционированием. К подобным документам относятся не только результаты официального документооборота (приказы, распоряжения и пр.), но и техническая документация по выполняемым и выполненным проектам: технические отчеты, проектная документация, планы и так далее. В последнее время довольно широкое распространение получили системы ILM (Information Lifecycle Management) и PDM (Product Data Management). ILM охватывает все процессы управления размещением, хранением, распределением, миграцией, архивированием и удалением данных в инфраструктуре предприятия [10,23]. Задачей ILM является хранение документов, и обеспечение оптимального времени доступа к ним со стороны пользователя и его систем [14].

PDM - это технология управления данными об изделии, которая позволяет решить две проблемы, возникающие при разработке и поддержке жизненного цикла наукоемкой промышленной продукции: управление данными об изделии и управление информационными процессами жизненного цикла изделия, создающими и использующими эти данные [16].

Построение эффективной единой информационной системы предприятия требует интеграции PDM-системы с системами Computer Aided Design / Manufacturing (CAD/CAM) и системами Enterprise Resource Planning System (ERP). CAD/CAM системы обеспечивают такие функции, как проектирование изделий, разработку технологий, расчет материальных и трудовых нормативов. ERP системы призваны выполнять такие функции, как планирование, управление продажами, снабжением, производством и запасами, управление персоналом, ведение управленческого, бухгалтерского и налогового учета. Общая схема взаимодействия этих систем представлена на рис.1. чертеж. коксгрушзраад < спецификация изделия

Инструкция Технология

Техпроцесс, нормы расхода материалов, нормы времени

Справочник материалов

Спрэзочнвд! конструкторской номенклатуры

Конструкторская Технологическ. документация документация

Нор'.'ы расхода материалов ,

Конструкторский состав изделия

Техпроцессы, маршруты

Номенклатура Спецификация Маршрут Список отступления от норм РЦ

Рис. 1. Общая схема интеграции CAD/CAM, PDM и ERP систем

В условиях жесткой конкуренции применение PDM-технологий дает предприятиям возможность получить целый ряд преимуществ, основными из которых являются: сокращение сроков разработки изделий и вывода их на рынок (сокращение так называемого цикла time-to-market); снижение себестоимости продукции при сохранении ее высокого качества; полное информационное сопровождение продукции на протяжении всего ее жизненного цикла [9].

Данные об изделии представляют собой всю информацию, созданную в течение жизненного цикла. Они включают в себя состав и структуру изделия, технические задания, геометрические параметры, чертежи, планы проектирования и производства, спецификации, нормативные документы, программы для станков с числовым программным управлением, результаты анализа, эксплуатационные данные и многое другое. Поскольку при их создании все чаще используются компьютерные средства, то поиск ответа на вопросы: «Существуют ли необходимые данные?», «Где они находятся?», «Являются ли они актуальными?» - не всегда представляется тривиальным [16].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Разработать формат записи деревьев синтаксического подчинения, пригодный для программной реализации метода автоматизированной генерации правил, на основе деревьев синтаксического подчинения: А.В .Гладкого.

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

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

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

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

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

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

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

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

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

Автором самостоятельно спроектирована и реализована подсистема генерации новых правил для системы машинного перевода «Кросслейтор», разрабатываемой в ИПМ им. М.В. Келдыша. Проведенные испытания показали эффективность применения предложенных решений.

Реализация и внедрение результатов. Алгоритмы и метод, описанные в данной работе, реализованы автором в компьютерной программе. Программа создавалась как с целью апробации и совершенствования разрабатываемых алгоритмов и метода, так и с целью практического использования в машинном переводчике «Кросслейтор», разрабатываемом в ИПМ им. М.В. Келдыша РАН и при выполнении гос. контракта П-261 в рамках ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013 гг., заключенного между Министерством образования и науки и МИЭМ.

Апробация работы и публикации. Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах:

1. «Ежегодная научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ», МИЭМ, 19 февраля - 29 февраля 2008 г.

2. «Ежегодная научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ», МИЭМ, 24 февраля - 05 марта 2009 г.

3. «Горизонты прикладной лингвистики и лингвистических технологий», Мегалинг 2009, Украина, Киев, 20-27 сентября 2009 г.

4. «Ежегодная научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ», МИЭМ, 17 февраля - 01 марта 2010 г.

5. «Новые информационные технологии в автоматизированных системах», МИЭМ, 25 марта 2010 г.

Основное содержание диссертационной работы и ее результатов отражено в следующих научных и научно-технических работах автора (из них 1 в журнале из перечня ВАК):

1. Дроздов В.В., Клышинский Э.С. О повышении качества синтаксического анализа текста за счет обучения с учителем // Журнал «Качество Инновации Образование», №10, 2010. С. 45-52.

2. Drozdov V.V. Automatic Generation of Rules for a System that Uses a Grammatical Approach to Syntactic Analysis // Automatic Documentation and Mathematical Linguistics, No. 3, Vol. 44, 2010, pp. 121-126.

3. Дроздов B.B. Обзор и сравнение статистических и грамматических методов синтаксического анализа // Материалы тринадцатого научно-практического семинара «Новые информационные технологии в автоматизированных системах».-М. МИЭМ, 2010. С. 75-83.

4. Дроздов В.В. Автоматическая генерация правил для системы, использующей грамматический подход к синтаксическому анализу // Журнал «Научно-техническая информация», № 5, сер. 2, 2010. С. 19-23.

5. Дроздов В.В. Обзор методов синтаксического анализа // Материалы международной научной конференции Мегалинг, Киев, 2009. С. 59.

6. Дроздов В.В., Клышинский Э.С. Метод автоматической генерации правил синтаксического анализа для грамматик в БНФ // Материалы двенадцатого научно-практического семинара «Новые информационные технологии в автоматизированных системах».— М. МИЭМ, 2009. С. 149153.

7. Дроздов В.В. Автоматическая генерация правил для грамматик естественных языков // Материалы ежегодной научно-технической конференции студентов, аспирантов и молодых специалистов МИЭМ. -М. МИЭМ, 2009. С. 63-64.

8. Дроздов В.В. Автоматизированная система генерации правил // Материалы ежегодной научно-технической конференции студентов, аспирантов и молодых специалистов МИЭМ- М. МИЭМ, 2008. С. 136137.

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

На защиту выносятся следующие основные положения:

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

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

• Алгоритм поиска максимального фрагмента неразобранного предложения, которое удается разобрать имеющимися в базе правилами.

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

4.4. Выводы

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

105 с помощью исходной базы правил не разбирались.

Заключение

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

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

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

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

106 использованы журнал синтаксического разбора и модифицированные деревья синтаксического подчинения. Журнал синтаксического разбора формируется системой машинного перевода «Кросслейтор» при проведении синтаксического анализа предложения. Правила синтаксического разбора в этой системе хранятся в Бэкусовских нормальных формах. Таким образом, сгенерированные правила также будут в виде Бэкусовских нормальных форм. Модифицированные Бэкусовские нормальные формы сочетают в себе удобство и ясность записи контекстно-свободных грамматик с описательной мощностью контекстно-зависимых грамматик, что позволяет использовать их для проведения синтаксического анализа текстов на естественном языке. Существует также возможность конвертации правил в этой форме в формат правил ATN.

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

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

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

Основные требования, предъявляемые к структуре используемого в методе дерева синтаксического подчинения:

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

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

разделяющие их.

Если к слову относится частица («не», «ни»), то она в дереве подчинения должна быть родителем этого слова.

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

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

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

1. Ализар А. Незаметная смерть распознавания речи // Компьютерные вести, №18, 2010.

2. Андреев A.M., Березкин Д.В., Брик A.B., Кантонистов Ю.А. Вероятностный синтаксический анализатор для информационно-поисковой системы // Компьютерная хроника, №1, 1999.

3. Апресян Ю.Д., Богуславский И.М., Иомдин Л.Л., Лазурский A.B., Митюшин Л.Г., Санников В.З., Цинман Л.Л. Лингвистический процессор для сложных информационных систем. М: Наука, 1992.

4. Апресян Ю.Д., Богуславский И.М., Иомдин Л.Л., Лазурский A.B., Перцов Н.В., Санников В.З., Цинман Л.Л. Лингвистическое обеспечение системы ЭТАП 2. М: Наука, 1989.

5. Большаков И.А., Гельбух А.Ф. Модель «Смысл<->Текст»: Тридцать лет спустя // J. International Forum on Information and Documentation, №1, 2000.

6. Бузикашвили H.E., Крылова Г.А., Самойлов Д.В. N-граммы в лингвистике. // Методы работы с документами. М., 2000.

7. Виноград Т. Программа, понимающая естественный язык; М., 1976.

8. Гладкий A.B. Синтаксические структуры естественного языка, Изд. 2 -М.: ЛКИ, 2007. С. 12-15.9.,Глинских А. Мировой рынок PDM-систем // Компьютер-Информ, №7, 2001.

9. Ю.Головченко А. ILM концепция и инструментарий // PC Week Review, №1,2008.

10. П.Дроздов B.B. Автоматизированный метод генерации правил синтаксического анализа проектной документации // Журнал «Научно-техническая информация», № 2, сер. 2, 2011.

11. Дроздов В.В., Клышинский Э.С. О повышении качества синтаксического анализа текста за счет обучения с учителем //Журнал «Качество.

12. Инновации. Образование», №10, 2010. С. 45-52.

13. Иомдин JI.JI. Автоматическая обработка текста на естественном языке: модель согласования. М.: Наука, 1990.

14. Клышинский Э.С. Перспективные методы обработки проектной документации // Сб. трудов конференции "Электронные библиотеки: перспективные методы и технологии, электронные коллекции". Казань, 2010. С. 129-134.

15. Люгер Д.Ф. Искусственный интеллект: стратегии и методы решения сложных проблем. М. : Вильяме, 2003. 863 с.

16. Мельчук И.А. Об одной лингвистической модели типа «Смысл <->Текст» // Серия литературы и языка, №5, 1974. Т.ЗЗ.

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

18. Мельчук И.А. Русский язык в модели «Смысл<-»Текст». М.: «Языки русской культуры»; Wien: Wiener Slawistischer Almanach. Sonderband 39 ,1995.

19. Ножов И.М. Реализация автоматической синтаксической сегментации русского предложения // Диссертация на соискание ученой степени кандидата технических наук, М.: РГГУ, 2003.

20. Ножов И.М. Синтаксический анализ // Компьютерра, №21, 2002.

21. Орлов С. Жизненный цикл ILM // LAN №7, 2007.

22. Протасов C.B. Преимущества грамматики связей для русского языка // Труды международного семинара Диалог'2005, М., 2005.

23. Протасов C.B. Вывод и оценка параметров дальнодействующей триграммной модели языка (Презентация) // Труды международного семинара Диалог'2008, М., 2008.

24. Протасов C.B. Вывод и оценка параметров дальнодействующей триграммной модели языка. // Труды международного семинара Диалог'2008, М., 2008.

25. Сегалович И., Маслов М. Яндекс на РОМИП-2004. Некоторые аспекты полнотекстового поиска и ранжирования в Яндексе // Труды РОМИП 2004 / под ред. Некрестьянова И.С. СПб., 2004.

26. Современная американская лингвистика: фундаментальные направления; под ред. A.A. Кибрика, И.М. Кобозевой, И.А. Секериной. М.:УРСС, 2002. 477 с.

27. Сокирко A.B. Семантические словари в автоматической обработке текста (по материалам системы ДИАЛИНГ) // Диссертация на соискание ученой степени кандидата технических наук, М. 2001.

28. ТестелецЯ.Г. Введение в общий синтаксис. М.: РГГУ, 2001 г. 798 с.

29. Технологии компании ПРОМТ // Сайт компании ПРОМТ. URL: http://www.promt.ru/company/technology/promt/ дата обращения: 23.08.2010).

30. Формальные модели анализа и распознавания языковых структур // Сайт Международной конференций по компьютерной лингвистике «Диалог». URL: http://www.dialog-21.iWtrends/?id=2026&fommid=17&f=l (дата обращения: 23.08.2010).

31. Холоденко А.Б. О построении статистических языковых моделей для систем распознавания русской речи // Интеллектуальные системы, 2002. Т.6. С. 384-385.

32. Хомский Н. Синтаксические структуры // Новое в лингвистике; Под ред. ЗвегинцеваВ.А. вып. II, М.: Прогресс, 1962, С. 412-527.ш

33. Шаров С.А. Средства компьютерного представления лингвистической информации // Информационные технологии и телерадиокоммуникации, 1996.

34. All Our N-gram are Belong to You // Official Google Research Blog. URL: http://googleresearch.blogspot.eom/2006/08/all-our-n-gram-are-belong-to-you.html (дата обращения: 23.08.2010).

35. Bahi L. R., Jelinek F., and Mercer R. L. A maximum likelihood approach to continuous speech recognition // IEEE Transactions on Pattern Analysis and Machine Intelligence, 1983. pp. 179-190.

36. Bateman J.A. Enabling technology for multilingual natural language generation: the KPML development environment // Natural Language Engineering, vol 3, 1997.

37. Bobrow D.G. Natural language input for a computer problem-solving system // Semantic information processing; Ed. by Minsky M. Cambridge (Mass.): The MIT Press, 1969. pp. 146 226.

38. Bresnan, J. (ed.) The mental representation of grammatical relations. Cambridge, Mass.: The MIT Press, 1982.

39. Brown P. F., Delia Pietra V. J., P. V. de Souza, Lai J. C., and Mercer R. L. Class-based n-gram models of natural language. // In Proceedings of the IBM Natural Language ITL, Paris, France, 1990.

40. Burton. R. R. Semantic Grammar: A Technique for Constructing Natural Language Interfaces to Instructional Systems. BBN Report No. 3587, Bolt Beranek and Newman, Inc., Cambridge, MA., 1977.

41. Burton. R. R. Semantic grammar: an engineering technique for constructing natural language understanding systems. BBN Report No. 3453, Bolt Beranekand Newman, Inc., Cambridge, MA., 1976.112

42. Carbonell, J. G. Requirements for Robust Natural Language Interfaces: The XCALIBUR and LanguageCraft Experiences // Proceedings of COLING-86, Munich, Germany, 1986.

43. Chomsky N. Aspects of the Theory of Syntax. Cambridge, MA: The MIT Press, 1965.

44. Chomsky N. Lectures on government and binding. The Pisa Lectures. Dordrecht: Foris, 1981.

45. Chomsky, N. Syntactic Structures. The Hague: Moution, 1957.

46. Chomsky N. The Minimalist Program. Cambridge (Mass.): The MIT Press, 1995.

47. Chomsky, N. Three models for the description of language // IRI Transactions on Information Theory, 1956. pp. 113-124.

48. DeMori R. and Kuhn R. A cache-based natural language model for speech recognition // IEEE Transactions on Pattern Analysis and Machine Intelligence, 1990. pp. 570—583.

49. Dorre J., Eisele A. A lexical-functional grammar system in Prolog // Proc. COLING-86, 1986. pp. 551 -553.

50. Fink G.A. Markov Models for Pattern Recognition. From Theory to Applications. Berlin: Springer-Verlag Berlin Heidelberg, 2008.

51. Gazdar G., Klein E., Pullum G., Sag I. Generalized Phrase Structure Grammar. Cambridge (Mass.): The MIT Press, 1985.

52. Goddeau D. and Zue V Integrating probabilistic lr parsing into speech understanding systems // Proceedings of the 1992 IEEE international conference on Acoustics, speech and signal processing, 1992. pp. 181-184.

53. Grinberg D., Lafferty J. and Sleator D. A robust parsing algorithm for link grammars // Proceedings of the Fourth International Workshop on Parsing Technologies. Carnegie Mellon University Computer Science technical report, 1995.

54. Halliday M.A.K. An Introduction to Functional Grammar, London: Edward Arnold, 1985.

55. Harris L.R. The ROBOT System: Natural Language Processing Applied to Data Base Query//Proceedings ACM Conf., 1976. pp. 165-172.

56. Hendrix, G.G., Sacerdoti, E.D., Sagalowicz, D., Slocum, J. Developing a natural language interface to complex data // ACM Transactions on database systems, 3(2), 1978. pp. 105-147.

57. Hopcroft J.E. and Ulman J.D. Introduction to Automata Theory, Languages and Computation. Rending. MA: Addison-Welsey, 1979.

58. Hudson R. Language Networks: The New Word Grammar. Oxford: Oxford University Press, 2007.

59. Hudson R. Word Grammar. Oxford: Oxford University Press, 1984.

60. Iyer R, Ostendorf M., and Rohlicek R. An improved language model using a mixture of Markov components // ARPA, 1994.

61. Jelinek F. Statistical Methods for Speech Recognition. Cambridge, Massachusetts: The MIT Press, 1997.

62. Jelinek F., Merialdo В., Roukos S., and Strauss M. A dynamic language model for speech recognition. IBM Research Division, Thomas J. Watson Research Center Yorktown Heights, NY, 1991. pp. 293-295.

63. Jurafsky D. and Martin J. H. Speech and Language Processing: An introduction to Natural Language Processing, Computational Linguistics, and Speech Processing. Prentice-Hall, 2000.

64. Kahn E. Frame, Semantics for motion verbs with application to metaphor // Proceedings of annual meeting of the Berkeley Linguistics Society. Berkeley, 1975. V.l.pp. 246- 256.

65. Kaplan R.M. and Bresnan J. Lexical-Functional Grammar: A Formal System for Grammatical Representation, Cambridge, Massachusetts: The MIT Press, 1982.

66. Karlsson, Fred. Constraint Grammar as a Framework for Parsing Unrestricted Text // Proceedings of the 13th International Conference of Computational Linguistics, vol. 3. Helsinki, 1990. pp. 168-173.

67. Karlsson, Fred, et al. Constraint Grammar: a Language-Independent System for Parsing Unrestricted Text. Berlin: Mouton de Gruyter, 1995.

68. Lafferty J. Sleator D. Temperley D. Grammatical Trigrams: A Probabilistic Model of Link Grammar //Proceedings of the AAAI Conference on Probabilistic Approaches to Natural Language, 1992.

69. Lau R., Rosenfeld R., and Roukos S. Trigger-based language models: A maximum entropy approach // Proceedings of the 1993 IEEE international conference on Acoustics, speech and signal processing, 1993. pp. 45-48.

70. Losee R.M. Learning Syntactic Rules and Tags with Genetic Algorithms for Information Retrieval and Filtering: An Empirical Basis for Grammatical Rules // Information Processing & Management, 1996. pp. 185-197.

71. MacGregor R. and Raymond B. The LOOM Knowledge Representation Language, Information Sciences Institute, 1987.

72. Marslen-Wilson W.D., Tyler L.K., The temporal structure of spoken language understanding. // Cognition, 1980. vol. 8. pp. 1-71.

73. Matthiessen C. & Bateman J. Text Generation and Systemic Functional Linguistics: Experiences from English and Japanese. London: Pinter Publishers, 1992

74. Mel'cuk, I.A. Dependency Syntax: theory and practice. N.Y.: State University of New York Press, 1988.

75. Mel'cuk, I.A. Studies in dependency syntax. Ann Arbor: Karoma, 1979.

76. Müller S. The babel-system: An HPSG Prolog implementation // In Proceedings of the 4th International Conference on the Practical Application of Prolog, London, 1996. pp. 263-277.115

77. Neidle C., Lexical-Functional Grammar // Encyclopedia of Language and Linguistics. New York: Pergamon Press, 1994.

78. Pietra S., Pietra D., Gillet J., Lafferty J., Prinz H., Ures L. Inference and Estimation of a Long-Range Trigram Model // Grammatical Inference and Applications, Second International Colloquium, ICGI-94, 1994.

79. Pollard C., Sag I.A. Information-based Syntax and Semantics // Volume 1: Fundamentals. Stanford: CSLI Publications, 1987.

80. Pollard C., Sag, I.A. Head-Driven Phrase Structure Grammar. Chicago: University of Chicago Press, 1994.

81. Radford A. Transformational Syntax. Cambridge: Cambridge University Press, 1981.

82. Sabah G. Knowledge Representation and Natural Language Understanding // AI Commnuications, 1993. Vol. 6. № 3-4. pp. 155-186.

83. Sag I.A., Wasow T., Bender E. Syntactic Theory: a formal introduction, Chicago: University of Chicago Press, 2003.

84. Saraswat V.A. Concurrent Constraint Programming. Cambridge, MA: The MIT Press, 1993.

85. Seljan S. Lexical-functional grammar of the Croatian language: theoretical and practical models. University of Zagreb, 2003.

86. Sleator D. Temperley D. Parsing English with a Link Grammar. Pittsburgh: Carnegie Mellon University, 1991.

87. Swartout W.R. A Comparision of PARSIVAL with Augmented Transition Networks. Cambridge: The MIT Press, 1978.

88. Thorne J.P. A computer model for the perception of syntactic structure // Proceedings of the Royal society. Edinburg: English Language Research Unit, Edinburg University, 1968. V. 171. pp. 377 386.

89. Waltz D.L. An English Language Question Answering System for a Large Relational Database // Comm. ACM, № 7,1978. pp. 526-539.

90. Weaver W. Translation. Technical Report, 1949. Reprinted in Machine Translation of languages. Cambridge, MA: The MIT Press 1955. pp. 15-23.116

91. Wilensky R., Arens Y. PHRAN: a knowledge-based natural language understander // Proceedings of the 18th annual meeting on Association for Computational Linguistics, 1980.

92. Winograd T. Language as Cognitive Process, Syntax. Addison-Wesley, Vol. 1, 1983.

93. Woods W.A. An Experimental Parsing System for Transition Network Grammars. New-York: Algorithmics Press, pp. 111-154.

94. Woods W.A. Semantics and quantification in natural language question answering // Advances in computers. N.Y. etc., 1978. V. 17. pp. 1-87.

95. Woods W.A. What's in a link: Foundations for semantic networks // Representations and understanding; Ed. by Bobrow D.G., Collins A. N.Y. etc., 1975. pp. 35 - 82.