Найханова Л.С. Методы и алгоритмы трансляции естественно-языковых запросов к базе данных в SQL запросы

Подождите немного. Документ загружается.

для реализации полной схемы анализа и синтеза модели «Смысл-текст» придется учесть

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

и индивидуальные свойства громадного числа пар единиц. Их полное формальное

описание представляет собой громадную и объемную теоретическую работу, поставленную

в лингвистике в последнее время и еще далекую от решения.

Модель контекстного фрагментирования разрабатывалась для анализа и синтеза

естественно-языкового предложения, но ее проработка касается в основном анализа. Задача

лингвистической трансляции естественно-языкового текста рассматривается отдельно от

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

Анализ и трансляция текста осуществляются при наличии достаточно мощных средств

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

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

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

модель содержит информацию о морфологии, синтаксисе и семантике подмножества

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

одновременным преобразованием распознаваемых синтаксических отношений в

семантические. Достоинством данного метода является то, что существует возможность

динамически изменять стратегию обработки естественно-языкового текста в зависимости

от необходимой глубины и последовательности этапов трансляции и расширять метод при

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

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

В заключение обзора различных подходов и направлений реализации моделей

лингвистического процессора можно сделать вывод о том, что к настоящему времени

модели способны:

- извлекать знания из заданного текста и строить правильные предложения

естественного языка по заданным значениям смысла;

- перефразировать эти предложения;

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

Главным средством решения всех этих задач является специальный семантический

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

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

Анализ показал, что разработанные модели имеют достоинства, но и не лишены

недостатков. Многие из них (модели «Семантик предпочтения», «Концептуальной

зависимости» и др.) в основном ориентированы на анализ, в них слабо продуман процесс

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

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

или слабо реализован блок морфологического или синтаксического анализов, что

оказывает существенное влияние на качество анализа.

1.5. Выводы по первой главе

Естественно-языковый интерфейс с базами данных не предполагает использование

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

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

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

синтаксического и семантического. Для каждого уровня требуется соответствующий

компонент модели со своим массивом правил и словарями и построением формального

образа запроса – морфологической, синтаксической и семантической структурами. Следует

отметить, что для решения поставленной задачи полный семантический анализ не

требуется, он необходим для классификации лексем с целью выполнения проблемного

анализа. Поэтому лингвистический анализатор целесообразнее называть лингвистическим

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

модель контекстного фрагментирования.

Как показала практика, для достижения приемлемого качества обработки

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

фразы. Достаточно выделить наиболее информативные единицы текста – ключевые слова,

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

анализатора для реализации таких систем является модель контекстного

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

морфологии, синтаксиса и отображения естественно-языкового текста на формальный язык

представления знаний базы данных.

Несмотря на то, что исследованиям в области обработки естественно-языковых

предложений посвящено много работ, окончательно теоретический аппарат ещё не

сформирован. В работе необходимо построить модели морфологического и

синтаксического анализов на основе использования известных методов морфологического

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

необходимо разработать соответствующие методы и алгоритмы.

В данной работе в качестве исходной оперативной информации будем рассматривать

запрос пользователя к SQL-ориентированной базе данных, на написание которого

накладываются следующие ограничения:

1. Запрос может состоять из одного или нескольких простых предложений на

русском языке.

2. Если запрос содержит несколько простых предложений, то каждое последующее

предложение должно содержать существительное, приведенное в одном из предыдущих

предложений.

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

данных.

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

должны использоваться указательные местоимения я, ты (вы), он (она, оно), они, этот, тот,

такой, таков, столько и т.п., частицы «ли», «либо», «то» и другие.

5. Рекомендуется начинать запрос со специальных слов: Выдать, Показать,

Перечислить, Как, Когда, Где, В какое время, Какой, Куда, Откуда.

При решении задачи будем считать заданными описание концептуальной схемы базы

данных, словари для морфологического, синтаксического анализов, словари синонимов,

словари антонимов.

2. Модель лингвистического транслятора

Анализ и трансляция текста осуществляются при наличии достаточно мощных

средств описания и фрагментации лингвистических знаний. Схема отображения ЕЯ-текста

адекватна трансляции ЕЯ-запросов на проблемную область в базе данных. Инвариантность

проблемной области достаточно точно отражается в словаре базы данных. Словарь БД

предполагает наличие в них всех концептов проблемной области и включает в себя, как

минимум, имя концепта и его определение.

2.1. Математическая модель транслятора

Основу модели контекстного фрагментирования составляет трехуровневая система:

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

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

преобразованием распознаваемых синтаксических отношений в семантические.

Структуру системы общения с базами данных можно представить в виде тройки:

Z = <M, В, K>,

(1.1)

где М – лингвистическая модель;

В – базовые механизмы обработки предложений;

К – ассоциированные процедуры.

Лингвистическая модель М содержит информацию о морфологии, синтаксисе и

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

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

Лингвистическая модель представляется в виде:

M = <M

, M

(1.2)

где M

– грамматическая модель;

– интерпретационная модель;

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

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

знаний и реализуемой схемой трансляции, а ее наполнение – используемым

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

Грамматическая модель, в свою очередь, состоит из кортежа:

′

111

, MMM

(1.3)

где M

′

- модель морфологического анализа;

′′

- модель синтаксического анализа.

Интерпретационная модель

задается в виде вектора:

′

222

, MMM ,

(1.4)

где

′

– модель метаописания базы данных;

′

- модель проблемной среды.

Базовые механизмы В реализуют четыре основных отображения: Ψ

: T → X

(морфологический разбор); Ψ

: Х→G (синтаксический разбор); Ψ

: G→G

(семантический и

проблемный анализы), Ψ

: G

→Q (трансляция), где Т – текст естественного языка в виде

множества лексем, X - множество лексем с векторами морфологической информации v, G -

граф зависимостей, в вершинах которого располагаются словоформы (лексемы), а дуги

отображают связь от вершины “предок” к вершине “потомок”, G

- граф, в вершинах

которого располагаются термины физической модели базы данных, Q – SQL-запрос в виде

команды SELECT.

Под ассоциированными процедурами К понимается разбиение предложения на

лексемы, а также все вычислительные процедуры, реализующие частичные функции,

необходимые для выполнения отображений.

2.2. Аппарат описания формальных моделей

Формирование ответа на запрос является результатом процессов распознавания и

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

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

логических отношений между языковыми объектами.

В настоящее время в качестве основных средств представления знаний в

информационно-поисковых системах используются Семантические сети, Системы

продукций, Фреймы и Логические модели, в последнее время стали развиваться

прикладные модели [128, 43, 69, 84, 90, 2, 131]. В качестве подхода к построению модели

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

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

на которой удобно описывать правила обработки знаний, именно это обстоятельство

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

2.2.1. Введение в системы продукций

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

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

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

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

продукционного подхода. Наиболее полное исследование данного представления в виде

формальных моделей дали А.С.Клещев [82], В.Е.Кузнецов [26], Т.М.Яхно [62,81],

M.Georgeff [130]. Особенности каждой модели определялись классами решаемых задач и

технологическим базисом.

Опишем концептуальные рамки понятия "системы продукций" (СП), используемого

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

складывалось и как эволюционировало. Формальная теория или исчисление [129]

определяется как "способ задания множеств путем указания исходных элементов (аксиом)

и правил вывода, каждое из которых описывает, как строить новые элементы из исходных

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

предыдущих элементов списка по одному из правил вывода, называют выводом в

исчислении. Наиболее полно изученными исчислениями в математической логике

являются исчисления высказываний и исчисления предикатов первого порядка [129]. С

каждой формулой в этих исчислениях связывается понятие «интерпретация»

(приписывание истинностных значений), через которое определяются такие понятия, как

противоречивость, непротиворечивость и общезначимость формул. Логическое следствие

определяется следующим образом. Формула G есть логическое следствие формул F

, F

,...,

, тогда и только тогда, когда для любой интерпретации I, если формула F

...

истинна в

I, то G также в ней истинна [129].

Логическое следствие получается в результате применения логических правил

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

либо для установления истинности некоторого утверждения, либо для порождения новых

заключений. В исчислении предикатов первого порядка зафиксировано несколько правил

вывода (например, modus ponens).

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

монотонны — мы никогда не отказываемся от полученных заключений, если становится

истинным некоторый дополнительный факт. В этом смысле они отличаются от

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

логических правил вывода обычно называют чистыми, или логическими, а вывод в них —

логическим выводом.

Формулировка задачи в исчислении предикатов рассматривается как теорема. Многие

проблемы могут быть сформулированы как проблемы доказательства теорем. Именно это и

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

Важный прогресс в этой области достигнут с момента разработки метода резолюций,

который оказался легкодоступным для реализации на ЭВМ. Именно поэтому исчисление

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

программ, обладающих интеллектуальными способностями [131].

Однако попытки автоматизации решения разнообразных классов задач в рамках

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

превращая простые задачи в практически не решаемые. В частности, именно с этим

обстоятельством связан некоторый скепсис в отношении применимости математической

логики. Это дало толчок развитию исчислений на основе использования проблемно-

ориентированных правил вывода. Примером таких исчислений являются системы

подстановок. К данному классу можно отнести исчисление, введенное Э.Постом, которое

он назвал системами продукций [131]. Система продукций Поста задается своим

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

вид a

W → Wb

, (i = 1... n), где a

, b

— слова в алфавите С. Пусть некоторое слово L

начинается словом а

. Выполнить над L продукцию — значит вычеркнуть из L начальный

отрезок а

, и к оставшемуся слову приписать справа слово b

. Например, применяя к слову

aba продукцию abW —> Wc, получим слово ас. Существуют теоремы, показывающие, что

любую систему подстановок можно "вложить" в систему продукций. Характерным для

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

К этому же классу исчислений можно отнести и порождающие грамматики,

введенные Н.Хомским [127]. Накладывание ограничений на левые и правые части правил

привело к классификации грамматик и соответственно к классификации языков,

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

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

некоторой заданной грамматикой. Основная сфера применения данного формализма — это

анализ формальных и естественных языков [127].

Общим для исчислений указанного вида, называемых иногда нелогическими,

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

математические аспекты и свойства. Так, разные варианты систем подстановок интенсивно

изучались в теории алгоритмов, а в программировании использовались в виде разного рода

грамматик, в основном для описания синтаксиса языков программирования.

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

в искусственном интеллекте к середине 70-х годов осознана необходимость разработать

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

общие методы поиска решений не привели к практическим успехам. В качестве одной из

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

> действие, в которых левая часть описывает некоторую ситуацию, а правая — те действия

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

Общая постановка задач при использовании множества правил формулируется

следующим образом. Задается исходное и целевое состояние задачи. Система сама на

основе заложенных в нее правил ищет возможные пути решения перевода исходного

состояния в целевое.

Знания о предметной области задают множество возможных преобразований в

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

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

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

продукций [131]. Такая форма представления информации была принята в некоторых

психологических моделях мышления человека. Исследования процессов принятия решений

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

А.Ньюэлл первым предложил использовать такое представление знаний для

моделирования на ЭВМ процесса принятия решений.

Таким образом, в искусственном интеллекте под термином "системы продукций"

понимают, с одной стороны, средство представления знаний. В этом смысле его можно

отнести к классу нелогических прикладных исчислений и исследовать его свойства. К

основным достоинствам систем продукций можно отнести: проблемную

ориентированность, естественную модульность организации знаний в системах продукций

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

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

не взаимодействуют друг с другом, эффект применения каждой из них определяется

изменениями, которые она производит в обрабатываемой структуре); присущая системам

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

а не только соответствующие процедуры обработки.

К проблемам реализации продукционных систем относится их формальное описание

и реализация процедуры поиска по образцу. Ниже описан подход, который позволит

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

имеет две основные части: условие применимости и действие.

Условие применимости представляет собой описание возможной ситуации

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

описывающих эту ситуацию. Множество условий применимости составляют множество

возможных ситуаций этой предметной области. На вход системы продукций подается

исходная ситуация, осуществляется поиск по образцу на множестве условий

применимости. Если условие применимости найдено, то выполняется действие,

соответствующее данному условию. Если представить условие применимости в виде

формулы логики предикатов второго порядка в скулемовской стандартной форме, то

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

для этого хорошо развитые резолютивные методы вывода.

В архитектуре программных систем продукций можно выделить четыре основных

компонента: базу данных — память для хранения информации о решаемой задаче, базу

знаний – множество правил (продукций), аппарат активации продукций - алгоритм,

осуществляющий поиск по образцу, и интерпретатор, выполняющий преобразование базы

данных по заданным правилам. Таким образом, аппарат активации продукций можно

реализовать на основе метода линейной резолюции.

В связи с тем, что сразу представление в предикативной форме утверждения на

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

работах Т.М. Яхно, А.С. Клещева, М.Ю. Черняховской, Т.Л. Гаврилова и других [131,

62,81-82], в котором для описания системы продукций применяется аппарат многосортной

алгебры.

2.2.2. Описание формального аппарата

Рассмотрим аппарат, который позволит построить формальное описание

лингвистических моделей. В работе [131] было предложено описание модели проблемной

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

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

записывается в виде простого правила «Условие → действие», что соответствует

оператору ЕСЛИ-ТО. Тогда модель проблемной среды может быть формализована как

система продукций. Описание продукций основано на работах [129 и 131].

Введем понятия из теории моделей в том объеме, в котором они понадобятся для

дальнейшего изложения и как они описаны в работах Т.М. Яхно [129, 131].

Введем определение терма:

• всякая константа

Aa ∈

, где А – словарь констант, есть терм;

• всякая переменная

Xx ∈

, где X - исходное множество-носитель, есть терм;

• если f - функциональный символ

∈

, а t

, ... , t

– термы

∈

, то f ( t

, ... , t

) –

терм.

Термы находятся как в функциональных, так и в предикатных отношениях. Фактом

принято называть предложение, являющееся истинным высказыванием. В предложении

элементы

2, …

, x

высказывания находятся в некотором отношении, которое обозначают

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

Р.

Определение 1. Назовем фактом предикат вида P

,...,t

), Tt

∈ , при этом

существуют некоторые t

=f(t

,...,t

), Ff

∈

- множеству частичных функций.

В этих обозначениях

ситуацией называется конечная конъюнкция фактов, через D

обозначается множество всевозможных ситуаций. Понятие ситуации соответствует

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

Если все t

(i = 1... n) в факте суть константы, то факт называется терминальным.

Поскольку среди фактов ситуации могут быть нетерминальные, то в общем случае ей

соответствует неединственный набор множеств носителей.

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

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

множеством, используя операции объединение

∪

, пересечение

∩

, разность \ и отношение

включения ⊇.

Традиционным образом введем понятие подстановки и примера.

Определение 2. Подстановка

– это конечное множество вида {t

,…,t

}, где

каждая v

– переменная, а t

– терм, отличный от v

, при этом все v

различны. Подстановка,

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

Определение

3. Пусть

={t

,…,t

} – подстановка и Е – выражение. Тогда Е

–

выражение, полученное из Е заменой одновременно всех вхождений переменной v

≤

в Е на t

. Е

называют примером Е.

Тогда запись d

является примером d и означает результат одновременной замены

каждого вхождения переменной v

, в d на соответствующий терм t

Определим основные преобразования ситуации, к которым относятся исключение и

добавление фактов. Для фиксированного Dd

∈

′

1. Операция исключения: elim[d'] : D →D; elim[d'](d) = d\ d'

2. Операция добавления: аdd[d'] : D →D; add[d'](d) =d ∪ d'

Определим множество программ

R преобразования ситуации следующим образом.

Во-первых, будем считать элементами

R программы add[d'], elim[d'] при любых Dd

∈

′

, во-

вторых, если две программы r

, r

∈

, то программа (r

, r

), определенная равенством

)(d) = r

(d)), Dd ∈

∀

, также элемент R.

Определение 4. Программу r

, содержащую только операции типа add[d'] (

∈

′

∀

назовем позитивной. Заметим, что out(r

) = ∅ и, если d

= r

), то

dd ⊇ .

Через r

, где

= {t

, ... , t

} — произвольная подстановка, обозначим программу

r, во всех операциях которой аргументы-переменные x

заменены на сопоставленные им

термы t

, i = 1...m.

Определение 5. Продукцией назовем пару <q, r>, в которой q — ситуация, называемая

условием применимости продукции, r - программа,

∈

, называемая действием, причем q

и r связаны соотношением var(q) ⊇ out(r).

Здесь var(q) - это множество имен переменных, входящих в условие

применимости

q, а Out(r) - множество имен переменных, входящих в программу r.

Системой продукций назовем конечное множество пар Рr = {<q, r>}. Будем говорить,

что d

непосредственно выводимо из d

при помощи продукции pr = <q, r>,

→ ,

если найдется такая подстановка

, что d

⊇

, а d

=r(q

)∪(d

Если найдется последовательность продукций рr

, рr

, ..., pr

, pr

∈ Pr, i = 1..k, k

≥

0 и

состояний базы d

, d

, …, d

таких, что

dddddd

→→→

−− 1110

......

, то

говорим, что d

выводимо из d

, и пишем

prpr

→

...

или

dd →

, a pr

, рr

, ..., pr

назовем последовательностью применимых к d

продукций.

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

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

ситуации описываются посредством условия применимости в виде предикатов

),...,():)...(:(

mitmt

ttPDtDt

ΘΘ , где

tt ,...,

- термы предикатного символа Р

, некоторые из

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

Ff ∈

), Θ - оператор, задающий квантификацию формулы и принимающий значение ∀ и

∃,

- задает область интерпретации терма t

, связанных логическими операциями

⊃¬≡∨∧ ,,,, .

Начальное состояние системы продукций должно содержать конъюнкцию

терминальных фактов

),...,(

eeP

∧

, которое будем называть входной ситуацией, и

обозначать

. Программа r продукции pr будет активизирована в том случае, когда

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

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

линейной резолюции Лавленда, Ковальского и Кюнера [132-133]. Чтобы применить данный

метод, необходимо сформировать множество дизъюнктов

. Множество

формируется из

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

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

преобразования формулы, задающей условие применимости

q продукции pr, в

скулемовскую стандартную форму (ССФ).

В результате скулемизации получается множество дизъюнктов

, в котором в

дизъюнктах могут присутствовать скулемовские функции

),...,(

xxg , позволяющие

исключить (элиминировать) кванторы существования













≤≥∨

isrxxxxgxxP

hjsri

,1|)..,),,...,(,...,(

. (1.5)

При выполнении линейной резолюции входные дизъюнкты

выбираются из

множества фактов, задающих текущую ситуацию

. Конъюнкция фактов ),...,(

eeP

∧

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

{

}

фактатогоiкортежадлинаmфактовколичествоieeP

imi

−−− ,|),...,(

. (1.6)

Таким образом,

– это элемент множества d

, являеющийся первым центральным

дизъюнктом при построении дерева вывода для доказательства истинности условия

применимости некоторой

i-той продукции для выбранного факта. Боковые дизъюнкты B

выбираются из множества

. Условием выбора является наличие в дизъюнкте P∈

литеры,

контрарной самой левой литере центрального дизъюнкта

С. Затем дизъюнкты С и B

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

унификации. Два дизъюнкта

С, B унифицируемы, если для них существует унификатор.

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

Определение 6. Пусть

={t

,…,t

} и

={u

,…,u

} – две подстановки. Тогда

композиция

θ•λ

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

,…,t

,…,u

} вычеркиванием всех элементов t

, для которых t

= x

, и всех

элементов

, таких, что y

∈

,…,x

Определение 7. Унификатор

для пары выражений W=(С,B) будет наиболее общим

унификатором (НОУ) ⇔ для каждого унификатора

для С, B существует такая

подстановка

, что

•

Определение 8. Множество рассогласований

пары W получается выявлением

первой (слева) позиции аргумента, в которой не для всех выражений из

W стоит один и тот

же символ.

Алгоритм унификации. На вход алгоритма унификации подается пара W= (С, B):

Шаг 1. Инициализация входных данных:

k = 0, W

= W,

Шаг 2. Вычисление частичных функций. Если в выражениях

С или B присутствует

функция

f∈F, то необходимо их вычислить до начала унификации.

Шаг 3. Если

– единичный дизъюнкт, то

– НОУ для W и остановка, иначе

найдем множество рассогласований для

Шаг 4. Формирование множества рассогласований

. В множество

включаются

термы

∈ С и переменные v

∈ В, стоящие в соответствующих позициях в С и В, их выбор

осуществляется последовательно слева направо.

Шаг 5. Если существуют такие элементы

и t

, что v

– переменная, не входящая

, то перейдем к шагу 5. В противном случае остановка: W не унифицировано.

Шаг 6. Композиция унификаторов

k+1

•{t

} и постановка в множество

выражений

k+1

•{t

Шаг 7. Присвоить значение

k+1 и перейти к шагу 3.

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

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

использовать четыре типа предикатов.

Параметрический предикат: P

par

(х, t(p

), …, t(p

)),

где х – имя понятия; t(p

) – терм, задающий соответствие между p

– именем i-того

показателя понятия и его

j-тым значением v

; m – количество показателей понятия х.

Предикат эквивалентности: P

(y, y). Этот предикат определяет равенство значений

левого и правого элементов кортежа.

Составной предикат: P

(x,y,t

где

x – первое понятие; y – второе понятие; t

– тип отношения r.

Функциональный предикат: P

, …,x

), y, f),

где

, …,x

) – терм, задающий n входных переменных x

; y – выходная переменная;

f – ссылка на функциональную процедуру F.

Каждая функциональная процедура

F реализует некоторый вычислительный

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

y через значения других n

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

утверждения об их взаимосвязи. Таким образом, функциональная процедура

F описывает

некоторую функцию. При этом каждая функциональная процедура ориентирована на

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

функциональным предикатом

через ссылку f при выполнении алгоритма унификации

[83, 84].

2.3. Модель морфологического анализа

2.3.1. Содержательное описание модели морфологического анализа

В результате проведенного анализа методов и подходов морфологического анализа

был разработан алгоритм, в основе которого лежит комбинированный метод

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

[29,30], базирующийся на делении словоформ на морфы и разбиении слов внутри

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

состоит в том, что у словоформы выделяются только основа и окончание, а количество

флективных классов превышает количество, приведенное в подходе Г. Г. Белоногова. Это

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