WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

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

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

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

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

Специальность 05.13.12

Системы автоматизации проектирования (информатика)

(технические наук

и)

Автореферат

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

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

Москва - 2010

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

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

Официальные оппоненты: доктор технических наук, доцент Никольский Сергей Николаевич кандидат физико-математических наук, доцент Большакова Елена Игоревна

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

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

109028, г. Москва, Б. Трехсвятительский пер., д.3.

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

Ученый секретарь диссертационного совета д.т.н., доцент Леохин Ю.Л

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

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

предприятия формируют большой архив, содержащий в себе различного рода документацию, связанную с их функционированием. К подобным документам относятся не только результаты официального документооборота (приказы, распоряжения и пр.), но и техническая документация по выполняемым и выполненным проектам: технические отчеты, проектная документация, планы и так далее. В последнее время довольно широкое распространение получили системы 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 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

свойствами:

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

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

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

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

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

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

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

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

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

Дерево подчинения для предложения «В декабре выпал первый снег»

будет иметь следующий вид:

Рис. 2. Пример дерева подчинения для предложения «В декабре выпал первый Итак, моделью предложения будет являться дерево синтаксического подчинения (оно же дерево зависимостей). Дуга в дереве подчинения – это синтаксическая зависимость.

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

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

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

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

имя правила::= случай | случай”|”имя правила случай::= символ|символслучай name_rule ”;” params”” params::= param | paramparams param::= name_param id vl vl::= “+” | “#” value | “-“ value | value Здесь part – название части речи, inf – нормальная форма слова, name_rule – имя правила, node_name – роль слова в предложении для образуемой вершины, id – идентификатор вершины, id_parent – идентификатор вершины-родителя (при отсутствии принимает пустое значение), name_param – название параметра, value – значение параметра.

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

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

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

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

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

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

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

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

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

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

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

Например, рассмотрим, как будет выглядеть дерево подчинения для предложения: «инженер подошел к старому, а не к новому устройству»

Рис. 4. Древесное представление предложения с необходимыми для Узел D нашего дерева подчинения - это пятерка вида w,p,r,n,m, где w слово в предложении (содержит лексические параметры, часть речи), p – номер слова в предложении, r - роль слова в предложении, n - порядковый номер слова, от которого зависит текущее (если зависит от вышестоящего по дереву подчинения, то параметр пуст), m - порядковый номер предлога, который относится к текущему слову (используется при согласовании).

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

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

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

Например, «Разбор по правилу SENTOBJ с позиции 0. Продукций 2».

Обозначим эту вершину как вершину первого типа H. Вершина первого типа - это четверка r,p,n,s, где r - правило, по которому проходил разбор, p - позиция, с которой проходил разбор, n - количество продукций, s - успешность разбора по этому правилу.

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

Например, «Начат разбор по продукции с позиции 0. Символов 1».

Обозначим эту вершину как вершину второго типа P. Вершина второго типа - это тройка вида n1,p,s, где n1-номер продукции в правиле, по которому идет разбор, p - позиция, с которой проходил разбор, s успешность разбора по этой продукции • Лист, содержащий номер терминала, с которым проходило сравнение.

Например, «Терминал успешно сравнился с символом в позиции 0».

Обозначим лист дерева разбора как L. Лист дерева разбора L - это пара вида t,s, где t - номер терминала в П, с которым проходило сравнение, а s - результат этого сравнения.

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

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

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

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

Для этого воспользуемся рекурсивным проходом по дереву подчинения.

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

Рис. 6. Дерево подчинения D’ предложения П’ и дерево подчинения D Шаг 2. Выбор неразобранного поддерева для построения нового правила.

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

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

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

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

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

L=(t,s)-лист F', такой что t равен порядковому номеру R' в X' и в s установлен флаг успешности разбора.

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

M={{L1,P1,H1},….,{Li,Pi,Hi},…., {Ln,Pn,Hn}}, где n=1, Li - лист дерева разбора F' Pi - вершина второго типа дерева разбора F' такая, что она является родительской для листа Li.

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

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

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

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

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

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

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

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

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

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

Вершина R’’ неразобранного поддерева D’’ – потомок вершина R’ имя правила 1:=имя правила 2|имя правила |имя правила 4 имя правила имя правила 4:=имя правила имя правила 5:=описание терминала вершины R’’ Здесь следует прояснить, почему не очень хорошим является следующий вариант создания правил:

имя правила 1:=имя правила 2|имя правила |имя правила 2 имя правила имя правила 5:=описание терминала вершины R’’ Имя правила 2 - это обычно продукция, содержащая описание терминального символа, по которому разобралась удачная вершина R’.

Если генерировать правила по схеме правило 2правило 5, то в дальнейшем, когда будет расширяться группа, зависимая от терминала, который разбирается по правилу 2, придется это правило делить и выносить вниз. Это необходимо, чтобы правило 5 относилось не только к терминалу правила 2, но и к группе слов, зависимых от него.

Вершина R’’ неразобранного поддерева D’’ – брат вершина R’ имя правила 1:=имя правила 2|имя правила 3 |имя правила имя правила 4:=имя правила имя правила 5:=описание терминала вершины R’’ имя правила 6:=имя правила 4 знак союз имя правила Следует отметить важный вариант создания нового правила, когда добавляемое слово относится не только к какому-то одному слову, а к группе слов. И при добавлении такого правила, нужно добавить его не тривиально к последней разобранной вершине, а подняться по всем правилам, описывающим слова группы, от которой оно зависит. Найти их последнее общее правило (если смотреть на журнал разбора от корня) и к нему добавить правило, описывающее новый случай.

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

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

Причастный оборот «, стоящий на столе» зависит от существительного «компьютер». Эта зависимость задается через параметр n узла D дерева подчинения. Но по базе правил причастный оборот должен зависеть не просто от существительного, а от группы «существительное + его зависимые слова».

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

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

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

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

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

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

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

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

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

Для некоторых предложения не удается построить «естественные»

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

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

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

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

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

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

синтаксического анализа текста за счет обучения с учителем // Журнал «Качество Инновации Образование», №10, 2010. C. 45- • 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– • Дроздов В.В. Обзор и сравнение статистических и грамматических методов синтаксического анализа // Материалы тринадцатого научнопрактического семинара «Новые информационные технологии в автоматизированных системах».– М. МИЭМ, 2010. C. 75- использующей грамматический подход к синтаксическому анализу // Журнал «Научно-техническая информация», № 5, сер. 2, 2010. C. 19- • Дроздов В.В. Обзор методов синтаксического анализа // Материалы международной научной конференции Мегалинг, Киев, 2009. C. • Дроздов В.В., Клышинский Э.С. Метод автоматической генерации правил синтаксического анализа для грамматик в БНФ // Материалы двенадцатого научно-практического семинара «Новые информационные технологии в автоматизированных системах».– М. МИЭМ, 2009. С. 149Дроздов В.В. Автоматическая генерация правил для грамматик естественных языков // Материалы ежегодной научно-технической конференции студентов, аспирантов и молодых специалистов МИЭМ. – М. МИЭМ, 2009. С. 63- • Дроздов В.В. Автоматизированная система генерации правил // Материалы ежегодной научно-технической конференции студентов, аспирантов и молодых специалистов МИЭМ.– М. МИЭМ, 2008. C. 136-

 
Похожие работы:

«ГАВРИЛОВСКАЯ НАДЕЖДА ВЛАДИМИРОВНА МЕТОДЫ, АЛГОРИТМЫ И ТЕХНОЛОГИЯ ПРОГНОЗИРОВАНИЯ АГРОМЕТЕОРОЛОГИЧЕСКИХ ФАКТОРОВ В МОДЕЛЯХ ПРОДУКТИВНОСТИ ЗЕРНОВЫХ КУЛЬТУР 05.13.18 – Математическое моделирование, численные методы и комплексы программ Автореферат диссертации на соискание ученой степени кандидата технических наук Барнаул – 2011 Работа выполнена на кафедре теоретической кибернетики и прикладной математики ФГБОУ ВПО Алтайский государственный университет. Научный руководитель :...»

«Динь Вьет Шанг Алгоритмы подбора параметров комбинирования ациклических графов соседства в задачах обработки текстурных изображений Специальность 05.13.17 – Теоретические основы информатики АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Тула 2013 2 Работа выполнена в Федеральном государственном бюджетном образовательном учреждении Высшего профессионального образования Тульский государственный университет (ТулГУ) на кафедре автоматики и...»

«Малышев Андрей Сергеевич РАЗРАБОТКА АЛГОРИТМОВ УПРАВЛЕНИЯ И ОБРАБОТКИ ИНФОРМАЦИИ ПРИ НЕШТАТНЫХ СИТУАЦИЯХ Специальность 05.13.01 – Системный анализ, управление и обработка информации АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Москва 2010 2 Работа выполнена в Открытом акционерном обществе Головной центр сервисного обслуживания и ремонта Концерна ПВО Алмаз-Антей Гранит (ОАО ГЦСО ПВО Гранит). Научный руководитель : доктор технических наук...»

«УПК 621.396.664 Ж уат Муратхан РАЗРАБОТКА И ИССЛЕДОВАНИЕ МОДЕЛЕЙ ТЕЛЕКОММУНИКАЦИОННОЙ СЕТИ ИНФРАСТРУКТУРЫ ЭЛЕКТРОННОГО ПРАВИТЕЛЬСТВА 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей Автореферат диссертации на соискание ученой степени кандидата технических наук Астана, 2009 Работа выполнена в Евразийском национальном университете имени Л.Н. Гумилева Министерства образования и науки Республики Казахстан Научный...»

«НЕКРАСОВ АЛЕКСАНДР ВИТАЛЬЕВИЧ НЕЙРОСЕТЕВОЙ АЛГОРИТМ КАЛИБРОВКИ ВОЛНОВОГО ТВЕРДОТЕЛЬНОГО ГИРОСКОПА Специальность – 05.13.01 Системный анализ, управление и обработка информации АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Москва – 2010 Работа выполнена на кафедре Авиационные приборы и измерительновычислительные комплексы Московского авиационного института (государственного технического университета). Научный руководитель : д.т.н., Бабиченко...»

«Экз. № ДАВЫДОВ ГЕОРГИЙ ГЕОРГИЕВИЧ ПРОГНОЗИРОВАНИЕ ДОЗОВЫХ ЭФФЕКТОВ В ЦИФРОВЫХ КМОП МИКРОСХЕМАХ НА СТРУКТУРАХ КРЕМНИЙ-НА-САПФИРЕ ПРИ ИМПУЛЬСНОМ ИОНИЗИРУЮЩЕМ ВОЗДЕЙСТВИИ 05.13.05 - Элементы и устройства вычислительной техники и систем управления Автореферат диссертации на соискание ученой степени кандидата технических наук Автор: Москва – 2009 г. Работа выполнена в Московском инженерно-физическом институте (государственном университете). Научный руководитель Доктор технических...»

«РАТУШНЯК Олег Александрович Методы сжатия данных без потерь с помощью сортировки параллельных блоков 05.13.11 – математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей. АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Красноярск — 2002 Работа выполнена в Институте систем информатики им.А.П.Ершова Сибирского отделения Российской академии наук Научный руководитель : доктор физико-математических наук,...»

«ТИМОНИН Денис Викторович ПАРАМЕТРИЧЕСКАЯ ИДЕНТИФИКАЦИЯ НЕЛИНЕЙНЫХ СИСТЕМ КЛАССА ГАММЕРШТЕЙНА ПРИ НАЛИЧИИ АВТОКОРРЕЛИРОВАННЫХ ПОМЕХ В ВЫХОДНЫХ СИГНАЛАХ Специальность 05.13.01 – Системный анализ, управление и обработка информации (в технике и технологиях) Автореферат диссертации на соискание ученой степени кандидата технических наук ПЕНЗА 2013 Работа выполнена в ФГБОУ ВПО Самарский государственный университет путей сообщения. Научный руководитель – доктор технических наук,...»

«КНЯЗЬКОВ Дмитрий Юрьевич МОДЕЛИРОВАНИЕ И ОПТИМИЗАЦИЯ ПРОЦЕССА ФОРМИРОВАНИЯ ГОЛОГРАФИЧЕСКИХ ИЗОБРАЖЕНИЙ НА ОСНОВЕ ЭФФЕКТИВНЫХ МЕТОДОВ РАСЧЕТА ЭЛЕКТРОМАГНИТНЫХ ПОЛЕЙ специальность 05.13.18 — Математическое моделирование, численные методы и комплексы программ Автореферат диссертации на соискание учёной степени кандидата физико-математических наук Москва — 2013 Работа выполнена в лаборатории механики управляемых систем Федерального государственного бюджетного учреждении науки...»

«МОГОРАС АНДРЕЙ АЛЕКСАНДРОВИЧ УПРАВЛЕНИЕ ТРАНСПОРТНЫМИ ПОТОКАМИ МЕГАПОЛИСА НА ОСНОВЕ ПРОГНОЗИРОВАНИЯ И ПОВЕДЕНИЯ ИНТЕЛЛЕКТУАЛЬНЫХ АГЕНТОВ Специальность 05.13.01 - Системный анализ, управление и обработка информации АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Москва 2010 Работа выполнена на кафедре: Математическое обеспечение систем обработки информации и управления (МОСОИиУ) Московского государственного института электроники и математики...»

«БУДИЛОВСКИЙ ДМИТРИЙ МИХАЙЛОВИЧ ОПТИМИЗАЦИЯ РЕШЕНИЯ ЗАДАЧ ТЕОРИИ РАСПИСАНИЙ НА ОСНОВЕ ЭВОЛЮЦИОННО-ГЕНЕТИЧЕСКОЙ МОДЕЛИ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ Специальность 05.13.01 – Системный анализ, управление и обработка информации АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата технических наук Ростов-на-Дону 2007 г. 2 Работа выполнена на кафедре Программное обеспечение вычислительной техники и автоматизированных систем. ФГОУ ВПО Донского государственного технического...»

«Поляков Сергей Владимирович Математическое моделирование с помощью многопроцессорных вычислительных систем процессов электронного транспорта в вакуумных и твердотельных микро- и наноструктурах Специальность 05.13.18 Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук Москва 2010 Работа выполнена в Институте математического моделирования РАН Официальные оппоненты : доктор...»

«Лапшин Виктор Александрович Математические модели динамики срочной структуры процентных ставок, учитывающие качественные свойства рынка 05.13.18 – Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Москва – 2010 Работа выполнена в Московском государственном...»

«Крылов Андрей Серджевич МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ И КОМПЬЮТЕРНЫЙ АНАЛИЗ ЖИДКИХ МЕТАЛЛИЧЕСКИХ СИСТЕМ Специальность 05.13.18 математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук Москва 2009 Диссертационная работа выполнена на кафедре математической физики факультета...»

«Махнычев Владимир Сергеевич Распараллеливание алгоритмов ретроанализа для решения переборных задач в вычислительных системах без общей памяти Специальность 05.13.11 – математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Москва – 2012 Работа выполнена на кафедре автоматизации систем вычислительных комплексов факультета вычислительной математики и...»

«Лаконцев Дмитрий Владимирович Анализ и оптимизация адаптивного централизованного управления в беспроводных широкополосных сетях передачи информации. Специальность 05.13.13 – Телекоммуникационные системы и компьютерные сети. АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Москва – 2007 Работа выполнена в Институте проблем передачи информации им. А.А. Харкевича РАН. Научный руководитель : доктор технических наук, профессор Вишневский Владимир...»

«Соколов Дмитрий Витальевич МЕТОДИЧЕСКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ДЛЯ ОПТИМИЗАЦИИ ПАРАМЕТРОВ ТЕПЛОСНАБЖАЮЩИХ СИСТЕМ Специальность 05.13.18 Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Иркутск 2013 2 Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте систем энергетики им. Л. А. Мелентьева Сибирского отделения Российской академии наук (ИСЭМ СО...»

«Портнов Игорь Сергеевич РАЗРАБОТКА ИНФОРМАЦИОННОЙ СИСТЕМЫ УПРАВЛЕНИЯ ПОТРЕБЛЕНИЕМ ТОПЛИВНОЭНЕРГЕТИЧЕСКИХ РЕСУРСОВ Специальность: 05.13.01– Системный анализ, управление и обработка информации (промышленность) АВТОРЕФЕРАТ Диссертация на соискание ученой степени кандидата технических наук Владикавказ 2009 Работа выполнена в ГОУ ВПО Северо-Кавказский горнометаллургический институт (государственный технологический университет) Научный руководитель : доктор технических наук, доцент...»

«Черноглазов Дмитрий Григорьевич ИССЛЕДОВАНИЕ РОБАСТНЫХ ХАРАКТЕРИСТИК ЛИНЕЙНЫХ СИСТЕМ УПРАВЛЕНИЯ Специальность 05.13.01 – системный анализ, управление и обработка информации (промышленность) Автореферат диссертации на соискание ученой степени кандидата технических наук Москва – 2011 Работа выполнена в Морской Государственной Академии имени адмирала Ф.Ф. Ушакова, на кафедре системного анализа, управления и обработки информации, г. Новороссийск Научный руководитель : доктор...»

«Малистов Алексей Сергеевич Разработка и анализ информационных алгоритмов повышения эффективности визуализации и достоверности автоматической регистрации динамических объектов компьютерными видеосистемами 05.13.01 – Системный анализ, управление и обработка информации (в области приборостроения) Автореферат диссертации на соискание ученой степени кандидата технических наук Москва 2011 Работа выполнена на Государственном унитарном предприятии Научнопроизводственный центр...»






 
© 2013 www.diss.seluk.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Методички, учебные программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.