Содержание к диссертации
ВВЕДЕНИЕ 4
1. ОБЗОР И АНАЛИЗ МЕТОДОВ РЕШЕНИЯ ЗАДАЧИ 10
Структура лингвистического анализатора 10
Анализ методов и подходов морфологического анализа 11
*-J КЗ. Аналитический обзор методов синтаксического анализа 14
Аналитический обзор семантических моделей—., . 22
Выводы и постановка задачи 27
2. МОДЕЛЬ ЛИНГВИСТИЧЕСКОГО ТРАНСЛЯТОРА 29
Математическая модель транслятора 29
Аппарат описания формальных моделей 30
Введение б системы продукции 30
Описание формального аппарата 34
2.3. Модель морфологического анализа 39
2.3.1. Содержательное описание модели морфологического анализа 39
і ks 2,3.1.1. Словари и таблицы совместимости 39
2.3.1.2. Алгоритм морфологического анализа 42
23.2. База правил морфологического анализа 43
Сорта морфологического анализа..., 43
Типовые предикаты условий применимости продукций морфологического анализа 45
Система продукций морфологического анализа 46
2.4. Модель синтаксического анализа 54
2.4.1. Содержательное описание модели синтаксического анализа 54
2.4.1.1. Алгоритм синтаксического анализа , 55
%
У I) 2.4.1.2. База знаний синтаксического анализа 56
2.4.2. Базаправил синтаксического анализа 63
2.5. Выводы по второй главе 66
3- МОДЕЛЬ ТРАНСЛЯЦИИ 67
3.1. Интерпретационная модель лингвистического транслятора 67
3JJ. Метаописание базы данных 67
3.1.2. Описание знаний проблемной среды 73
чР*
3.2. Базовые механизмы проблемного анализа 77
3.2. 1. Метод построения преобразования 4 77
3.2Л Л. Построение транзитивных замыканий 78
Описание системы продукций 81
Преобразование графа зависимостей терминов логической модели в граф зависимостей терминов физической модели - преобразование Щ 88
3.3, Формирование SQL-запроса или построение преобразования Т4 90
Продукции по формированию SQL-запроса 92
Алгоритм доказательства гипотез 94
Формирование оператора SQL 96
ЗА Выводы по третьей главе 97
ЗАКЛЮЧЕНИЕ 99
ЛИТЕРАТУРА 100
ПРИЛОЖЕНИЕ А. Лингвистические знания морфологического анализа ПО
ПРИЛОЖЕНИЕ Е- Правила синтаксического анализа 118
ПРИЛОЖЕНИЕ В, Предикаты метаописания базы данных 140
ПРИЛОЖЕНИЕ Г\ Предикаты описания знаний проблемной среды 150
ПРИЛОЖЕНИЕ Д. Система продукций формирования SQL-запроса , 157
ПРИЛОЖЕНИЕ Е. Описание программного обеспечения и вычислительных
экспериментов 162
Введение к работе
Актуальность темы диссертационного исследовании. Задача, интеллектуальной обработки текстов на естественном языке впервые появилась на рубеже 60-х-70-х гг.ХХ в.. Работы последних лет связаны с решением проблемы анализа смысла языка в приложении к созданию систем диалога с программным обеспечением. Подходов к решению задачи понимания естественно-языковых запросов- несколько. Наиболее распространенными являются подходы, основанные на синтаксическом, семантическом анализах и шаблонах. Первый подход основан на .использовании синтаксических конструкций» Синтаксическое представление запроса строится на основе подлежащего, сказуемого, прямого дополнения и т.п., которые определяются с помощью морфологических характеристик (часть речи, род, падеж, лицо и т.д.)' Это представление ничего не говорит о смысле запроса»
Второй подход, основанный на семантике, гораздо ближе к смыслу запроса. В нем. используется синтаксическая информация из предыдущего подхода, а также информация из семантических словарей. Каждое слово в словаре имеет характеристики, позволяющие определять смысловые отношения между ним и другими словами, точнее, их значениями: Полное-описание связей между смыслами слов (а одно слово часто имеет несколько смыслов) образует тезаурус, представляющий собой большую сеть со словами и их смыслами в качестве, узлов, С помощью таких тезаурусов выполняется построение семантического представления запроса. Основная задача при этом:— отсечь ненужные. смыслы, постараться выделить, с помощью синтаксических, связей достоверные семантические конструкции. В больших предложениях, особенно с многозначными словами, это часто приводит к комбинаторному взрыву — перебору множества смыслов и связей между ними, а. также многозначности синтаксических конструкции (одному и тому же предложению может быть сопоставлено несколько синтаксических представлений), обработка которых занимает неприемлемо большое время. Это лишь одна проблема, стоящая на пути понимания естественно-языковых запросов в традиционной синтаксически-ориентированной парадигме. Вторая сложность — типичные естественно-языковые запросы, которые,как правило, не имеют правильных синтаксических конструкций- На это влияют вольное словоизменение и словообразование в виде неологизмов сетевой общественности, большой процент имен собственных и сокращений, игнорирование правил пунктуации, что приводит к тому, что от естественного языка во всем его многообразии иногда остается лишь лексика, причудливым образом исковерканная- И, наконец, необходимые в этом подходе-семантические словари — очень трудоемкая составляющая, для многих предметных областей они просто отсутствуют, а их разработка требует высокой квалификации.
Третий подход к анализу естественно-языковых запросов основан на шаблонах. Он появился самым первым и с точки зрения программной реализации наиболее прост. Суть его в том, что возможные запросы покрываются набором шаблонов-конструкций, позволяющих отождествляться с запросом и выдавать в результате предопределенные конструкции. Основной недостаток такого подхода заключается в необходимости предусмотреть все возможные способы выражений на естественном, языке, т.е. исчислить грамматику. К сожалению,. современный пользовательский язык совсем не похож на литературный, и поисковые запросы синтаксическими шаблонами.в чистом виде покрыть довольно трудно. Если же основываться на семантической грамматике, придется для каждой новой предметной области писать шаблоны заново,
К настоящему времени существующие естественно-языковые системы используют в основномдва последних подхода. Второй подход реализован в достаточно распространенной системе ЗАПСИБ, разработанной в середине 80-х годов'[78]; Система позволяет вести общение на ограниченном подмножестве естественного языка. Развитием проекта является система InterBase, вышедшая в 1990 году [128]. Система основана на семантически-ориентированном анализе и продолжает ряд естественно-языковых технологий лаборатории искусствешюго интеллекта. ВЦ АН Новосибирска, затем фирмы «Иіггеллектуальпьіе -технологии», а теперь РосНИИ искусственного интеллекта. В 2001 году эта система была переработана и получила название InBASE в виде коммерческого продукта. В настоящее время система представляет собой библиотеку СОМ-компонентов и- среду настройки естественно-языковых интерфейсов. Существенным отличием от старой версии является появление промежуточного уровня запросов — Q-языка, являющегося подмножеством языка объектных запросов OQL, и уровня описания предметной области в виде диаграммы классов UML, В полном соответствии с особенностями семантически-ориентированной парадигмы InBASE позволяет строить естественно-языковые интерфейсы ко многим языкам — для русского и для английского используется один и тот же Л-процессор. Интересной особенностью InBASE является возможность моделирования предметной области на естественном языке:"С помощью класса словарных статей «Толкование» смысл слова можно описать простой фразой. Это позволяет настраивать естественно-языковые интерфейсы^ людям, не обладающим навыками инженеров знаний. Основным недостатком данной системы является то, что кортежи базы данных продублированы в словарях — отдельных файлах. В базах данных больших объемов этот недостаток может стать проблемой [34, 97, 115,123,126-127].
Ярким представителем третьего подхода является система English Query. Система English Query от Microsoft основана на синтаксически-ориентированных шаблонах,
связываемых с моделью предметной области, и через нее - со схемой базы данных [ 107]. При настройке необходимо задать модель базы данных и предметной области, а затем для каждого отношения в базе данных (а отношением считается и связь между классом и его атрибутом, например, между товаром, и его ценой) задать синтаксический шаблон английской грамматики, выбираемый из списка. Этот продукт позволяет строить естественно-языковые интерфейсы только для английского языка и работает только с Microsoft'SQL Server,' в этом смысле это лишь утилита, поставляемая с SQL-сервером, именно так она и позиционируется. В целом же этот продукт очень интересен. Например, в нем есть встроенная.обучаемая базазнаний, с которой можно пообщаться на. английском* языке, — она запоминает факты, правила и отвечает на вопросы по этой базе, К сожалению,. эта замечательная способность не совмещена с пониманием запросов к базе данных.
Исследования, проводимые в данной- работе, посвящены разработке методов и алгоритмов, реализующих второй-подход. Основное.отличие:от описанных выше.работ заключается; в формальном описании моделей транслятора. На. наш взгляд, запросы к структурированным источникам-данных вполне.могут быть изложены.в виде одного или нескольких простых предложении естественного языка, в которых отсутствуют неологизмы и для которых несложно осуществлять синтаксический анализ. При синтаксическом анализе естественно-языкового предложения строится граф. зависимостей, который после ряда последовательных преобразованию содержит информацию, необходимую для'построения SQL-запроса.
База знаний, необходимая для выполнения анализа запроса, содержит мстаописание базы данных и знания проблемной среды. Модуль метаописания БД состоит из описания концептуальной схемы базы данных на.естественном язьжс: сущностей, атрибутов и связей между сущностями; Модуль словарей содержит знания для проведенияморфологического, синтаксического анализов и трансляции естественно-языковых запросов к базе данных. Модуль знаний проблемной-среды содержит описания понятий и терминов предметной области;
Создаваемую естественно-языковую систему обработки запросов к базе данных предполагается использовать при разработке больших информационных систем. База знаний; должна заполняться в процессе разработки проекта информационной системы. Поскольку у многих информационных систем основным ядром является SQL-ориентир овалі іьіе распределенные базы данных, то задача построения естественно-языкового пользовательского интерфейса тесно связана с разработкой методов и алгоритмов трансляции естественно-языковых запросов. в запросы. SQL языка. Все это определило актуальность работы, выбор целей, задач, структуры и содержания исследования,
Таким образом, целью исследования является разработка методов и алгоритмов, позволяющих осуществлять преобразование естественно-языковых запросов к базе данных, представленных в виде простых предложений русского языка, в SQL-запросы,
Для достижения указанной цели в работе поставлены и решены следующие задачи:
анализ существующих лингвистических моделей для.обработки предложений естественного языка;
разработка лингвистической модели транслятора;
разработка интерпретационной модели задачи;
разработка подхода к семантическому и проблемному анализам естественноязыкового запроса;
разработка методов трансляции естественно-языковых запросов к базе данных, представленных в виде простых предложений русского языка, в SQL-запросы,
Объектом исследования является естественно-языковой запрос к базе данных в виде простого предложения.
Предмет исследования - преобразование запроса на естественном языке в SQL-запрос.
Методологической и теоретической основой исследования послужил математический аппарат теории искусственного интеллекта, множеств, графов, математической логики и лингвистики- Достоверность научных выводов и практических-рекомендаций основывается на теоретических, и методологических положениях, сформулированпых в исследованиях зарубежных и российских ученых: Д.А. Поспелова, Э.В. Попова, Г.Г\ Белопогова, Е.С. Кузина, Р.Г. Пиотровского, А.С. Нариньяни, Т. Винограда, М. В. Никитина, О. Н. Селиверстовой, А. И. Смирницкого, Ю.А. Загорулько, JLA. Голубсвой, В.Е. Дмитриева, Ф.Г. Динетіберга, Е.Ю, Капдрашиной, И.С Кононенко, Д.Я. Левина, B.C. Маркина, Т.В. Нестеренко, G.H. Очаковской, В.В. Телермана, СП. Трапезникова, В.Ф. Хорошевского, И.Е. Швецова, Т.М. Яхно, Р. Ковальского, Д. Лавленда, Д. Кюнсра и других [21-29,49, 59, 55, 64, 68, 80, 85-86, 114, 107].
Наиболее существенные результаты и научная новизна диссертационной работы заключается в разработке модели лингвистического транслятора естественно-языкового запроса в SQL-запрос базы данных, особенностью которого является то, что для построения модели впервые использован подход, основанный на решении задачи в виде преобразований в пространстве ситуаций.
Проведенные исследования привели к следующим результатам, содержащим, по мнению автора, элементы научной новизны:
грамматическая модель и модель трансляции, отличительной особенностью которых является их представление в виде систем продукций морфологического, синтаксического, семантического и проблемного анализов;
интерпретационная модель, сосотоящая из модели метаописания базы данных и модели1 проблемной среды, представленные в виде множества фактов и описанные предикатами.
Теоретическая, значимость исследования состоит в создании подхода, позволяющего представлять условие применимости продукции в виде множества дизъюнктов и применять метод резолюции для активации продукционных правил.
Практическая значимость исследования состоит в том, что полученные результаты могут быть применены при разработке реальных естественно-языковых систем общения с базами данными.
Апробация результатов исследовании. Основные положения диссертационной работы докладывались и обсуждались на международной научно-технической конференции-"Информатизация-процессов формирования открытых, систем на основе СУБД, САПР, АСНИ и СИИ" (Вологда, 2001 г.), III Международной выставки-конференции "Информационные технологии и телекоммуникации в образовании" (Москва, 2001 г.), VI.и VII Всероссийской конференции по проблемам информатизации региона ПИР (Красноярск, 2000 и 200 Г гг.), первой, третьей, четвертой и пятой конференциях «Теоретические и прикладные вопросы современных информационных технологий» (Улан-Удэ, 2000-2004 гг.), внуривузовской научной конференции преподавателей, научных работников и аспирантов ВСГТУ (Улан-Удэ, 2000-2004 гг.), межкафедральном семинаре «Концепции и методологии создания.современных информационных систем» (СибГТУ, Красноярск, 22 сентября 2004 г.). Ряд положений диссертации был использован при подготовке учебного- курса «Естественно-языковые системы» по специальности 220400 «Программное обеспечение вычислительной техники и автоматизированных систем» и нашел применение в учебном процессе ВСГТУ. По теме диссертации опубликовано 8 печатных работ общим объемом, более 24 пл.
Структура и объем диссертации. Работа состоит из введения, трех глав, заключения, литературы и 6 приложений.
В первой главе дан обзор существующих моделей лингвистического анализатора, рассмотрена структура лингвистического анализатора, проанализированы. методы и алгоритмы морфологического, синтаксического и проблемного анализов, сделаны основные выводы и сформулирована постановка задачи.
Во второй главе рассматривается математическая модель лингвистического транслятора, которая включает в себя лингвистическую модель, базовые механизмы обработки предложений и ассоциированные процедуры. Предложен аппарат для построения формального описания лингвистических моделей, который основан на описании модели знаний предметной области в виде множества подразумеваемых ситуаций. Поэтому решение задач представляется в виде преобразований в пространстве ситуаций. Формальное отображение ситуации описывается продукционными правилами, что позволяет представлять модели в виде системы продукций, а решение задач строить как доказательство теорем, используя метод линейной резолюции. На основе предложенного подхода построены формальные модели морфологического и синтаксического анализов лингвистического транслятора в виде систем продукций.
Третья глава посвящена методам трансляции. В пей предложены формальные модели метаописания базы данных и проблемной среды, которые описываются семейством множеств закономерностей проблемной среды и концептуальной схемы базы данных, представленных в виде формул предикатов второго порядка, описаны методы построения графа, гомеоморфного графу зависимостей естественно-языкового запроса и методы трансляции естественно-языковых запросов в SQL-запросы к базе данных.
В заключении приведены основные результаты работы и перспективы развития.
В прилолсениях приведены структура лингвистических словарей морфологического анализа, система продукций синтаксического анализа и система продукций по формированию SQL-запроса, формальные модели метаописания базы данных и проблемной среды, описание программного обеспечения и вычислительных экспериментов.
