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

Интеллектуальные решатели задач. Стратегии поиска с оценочными функциями. Игровые стратегии поиска решения, страница 4

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

Этап синтаксического анализа

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

1. Система составляющих.

2. Деревья зависимостей.

Система составляющих

Произвольная последовательность словоформ называется цепочкой. Длиной цепочки ω(по модулю) является число словоформ в цепочке. Вхождение словоформ в цепочку называют точками. Точки могут быть расположены относительно друг друга левее или правее. Если α расположена левее β, то пишут α<β. Для любых двух точек альфа и бета цепочки омега вводится понятие отрезка или составляющей, представляющей собой множество точек ζ, удовлетворяющим неравенство α≤ζ≤β.

Множество С отрезков цепочки х является системой составляющих, если:

1. Множество С содержит отрезок, состоящий из всех точек цепочки х, и все одноточечные отрезки х.

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

Элементы С называются составляющими, одноточечные отрезки называются точечными (тривиальными) составляющими. Реальные предложения ЕЯ описывают размеченными системами составляющих. Размеченная система составляющих это <С, W, φ>, С – система составляющих, W – множество меток, φ – отображение С в W. Множество всех возможных систем составляющих для цепочки «фи» называется пространством составляющих. Из пространства выделяют некоторое число систем составляющих, называемых правильными системами составляющих (ПСС). ПСС – это такая система составляющих, которая соответствует определенному толкованию синтаксической структуры предложения. Если существует несколько ПСС, это называют синтаксической омонимией. Недостатком систем составляющих является невозможность описания главенствования одних словосочетаний над другими, в то время как такое главенствование существует.

Деревья зависимостей

Пусть задана цепочка х. Х – множество всех точек х. Отношение -> на множестве Х, при котором граф <X,->> является деревом, называют отношением зависимостей. Само дерево называется деревом зависимостей для цепочки х. Дерево зависимостей изображается в виде последовательности точек, соединенных дугами (ребрами) дерева и расположенных по одну сторону от точек этой цепочки. При анализе ЕЯ используется размеченные деревья зависимостей, аналогичные размеченным системам составляющих. Большинство предложений русского языка можно отнести к синтаксической структуре описываемой проективными деревьями зависимостей. Для дерева зависимостей <X,->> отношение -> называется проективным, если для любых трех точек «альфа», «бета», «гамма» из того что альфа -> бета и гамма лежит между альфа и бета, следует что гамма -> бета. Графически признаки проективности дерева:

1. Ни какие две дуги не пересекаются.

2. Корень дерева не лежит ни под одной из дуг.

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

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

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

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

Семантический анализ (анализ смыла)