Порождение дерева состояний на основе порождающих грамматик над деревьями строк

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

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

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

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

Как известно, стандартные порождающие грамматики над строками имеют вид четверки: G , где S – начальный символ порождающей грамматики; T – множество терминальных символов; N – множество нетерминальных символов; R – множество правил трансформации одной строки в другую.

Для порождающих грамматик над деревьями строки символов t и n заменяются деревьями (или лесом – деревьями с тождественными узлами). t = t , где t’ = t’ и т. д., n = n , где n’ = n’ и т. д.

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

Порождающая грамматика над деревьями строк строится следующим образом. Пусть A<…B<…C1 → C2…>,…, B’<…C1’ → C2’>…> – правило порождающей грамматики над деревьями из множества таких правил с деревьями строк терминальных символов T и нетерминальных символов N; → – символ перехода одной строки в другую; S<> – начальный символ порождающей грамматики над деревьями.

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

Можно рассмотреть также деревья разнородной информации A = {A, A,A,A} = {A, A, A}. Таким образом, дерево состояний системы может быть вложено в дерево элементов системы и наоборот.

Как результат, высказывание может рассматриваться в виде объединения (сложения) деревьев разных срезов рассмотрения над единым пространством (деревом) точек слов естественного языка [4–6].

Пусть дано дерево A , B’’<…>,…, B’’’<…>>, C , C’’<…>, C’’’<…>>, …, D , D’’<…>, …, D’’’<…>>> или коротко A <…B <…B’’…>…>, тогда лес деревьев рассмотрим как множество деревьев с тождественными узлами на множестве узлов этих деревьев: F…>, X<…Y<…Y’’(=L1)…>…>,…>, где L1 – тождественный узел первых двух деревьев вышеприведенного примера .

Рассмотрим пример дерева комбинаций шахматной партии: Доска <Колонка [1] <Клетка [1], Клетка [2],…>,…>, такое дерево формируется посредством умножения позиции на доске на множество правил возможных полуходов.

Ход конем будет иметь следующий вид: Доска <…Ко-лонка [X] <…Клетка[Y] <Конь → Пусто>>, …, Колонка [(X + 1)or(X–1)] <Клетка[(Y + 2)or(Y-2)] <Пусто → Конь>…>…> .

Генерация, например, образа стула предполагает также потенциальный образ человека на этом стуле. Стул <Сидение, Ножки, Спинка, Человек(= L1) <Руки(= L2), Ноги(= L3),

Математика, механика, информатика

Туловище(= L4), Голова(= L5)>> + Джентльмен(= L1) <Тело <Руки(= L2), Ноги(= L3), Туловище(= L4), Голова(= L5)>, Одежда <Пиджак <Туловище<= L4>>, Ботинки, Цилиндр <Голо-ва(= L5)>>> = Рисунок<Стул<…>, Джентльмен<…>,…>.

Принцип свертки или сложения образов заключается в следующем: семантически схожие элементы – узлы деревьев – объявляются тождественными; в случае наличия нескольких вариантов свертки строится дополнительное подпространство возможных состояний системы – результата сложения деревьев элементов системы и порождения деревьев состояний системы.

Предложение естественного языка также может быть представлено в виде дерева. Например, дерево грамматического разбора предложения упрощенно может иметь следующий вид: Предложение <Вводное слово, Обстоятельство, Субъект <Определитель, Определение <Наречие степени, Группа прилагательного>, Именная часть>, Предикат <Модальность, Обстоятельство, Глагольная часть>, Объект <Определитель, Определение <Наречие степени, Группа прилагательного>, Именная часть>, Обстоятельство>.

Данное дерево может быть прибавлено к (свернуто с) деревом семантического анализа, например, Тема «Здания» <Отношение-Существо-Здание {входить в, строить}, Свойство-Здание {мраморный, многоэтажный}, Здание {дом, библиотека}, Обстоятельство 1 <с/без {с, без}, Сущ-ность-Здание/Комнаты {коридор, зал}>, Обстоятельство 2 <с/без {с, без}, Свойство-Предмет(Сущность-Здание/ Архитектурный элемент {большой, красивый}), Сущ-ность-Здание/Архитектурный элемент {стена, угол}>>.

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

• 1.    Субъект – существо (этот …/ человек / мужчина / женщина).

• 2.    Модальность – действие над отношением (хотеть / желать / любить / обожать).

• 3.    Предикат – действие с одеждой (покупать / получать / примерять / носить).

• 4.    Объект – одежда (этот … / джинсы / свитер / футболка).

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

• 1.    0 → Этот.

• 2.    0 → Атрибут – свойство одежды (стильный / модный / клетчатый).

• 3.    Объект – Одежда (Этот … → 0 / джинсы / свитер / футболка).

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

Можно предположить, что проблемы распознавания образов, анализа естественного языка и ряд других могут быть эффективно решены только на основе их совместного синтетического рассмотрения. Так, например, для перевода выражения «up-link communication» как «связь со спутником» необходимо использовать визуальный образ того, о чем говорится в тексте. Таким образом, в системе перевода при переводе текста должен наращиваться семантиковизуальный образ повествования, без которого невозможен перевод, приближенный к переводу человеком.

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

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