Технология построения многовариантных объектно-ориентированных структур текстов

Вид материала

Содержание

Классы задач
Объектно-ориентированный подход
Продукционный подход
Абстрагирование от вычислительной модели
Индустриальная реализация и расширяемость
Концепция предлагаемой технологии
Подход к анализу текстов
Основные понятия технологии

Подобный материал:

1 2 3 4 5 6 7 8 9

[Рязанский проспект] = Рязанск..._[проспект]

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

[проспект] =

проспект...

пр-т(.)

пр(.)

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

^ Классы задач

Итак, были рассмотрены основные подходы к построению структуры текста, используемые в различных системах, а также приведен обзор этих систем. В обзор были включены только те системы, в которых эксплицитно выделен компонент описания структуры текста. Построение структуры текста является частью любой системы, так или иначе связанной с обработкой текста на ЕЯ. К ним относятся системы, решающие задачи:

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

Этим обусловлена важность проработки компонента построения структуры текста.

Постановка задачи

Предлагаемая в данной работе технология обобщает подходы к распознаванию структуры текста, выделяет их в отдельный компонент, который может быть использован в любых системах, связанных с обработкой текстов как на естественном языке, так и любых других текстов (например, на формальных языках). Исходя из обзора достоинств и недостатков существующих систем и подходов к анализу структуры текста, можно сформулировать ряд требований к предлагаемой технологии, получившей название "ТОМАТ":

Универсальность

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

^ Объектно-ориентированный подход

Для анализа текстовых конструкций должна быть описана модель предметной области в виде системы классов. Это описание должно строиться в соответствии с концепцией объектно-ориентированного проектирования. Структуры, которые строятся в процессе анализа текста, являются системами объектов этих классов.

^ Продукционный подход

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

^ Абстрагирование от вычислительной модели

Формализм представления структуры текста должен быть абстрагирован от конкретной вычислительной модели, реализующей обработку текста на основе данного формализма. Можно лишь предусмотреть основные типы вычислительных моделей, но не исчислить их полностью. Так, в одной задаче может понадобиться одновариантный анализ, тогда как в другой — многовариантный с построением всех возможных структур; в одной задаче эффективным окажется алгоритм поиска снизу-вверх, а в другой лучшие результаты может дать анализ сверху-вниз и т.п.

^ Индустриальная реализация и расширяемость

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

Предлагаемая технология "ТОМАТ" удовлетворяет вышеперечисленным требованиям. Подробное описание компонентов технологии, принципов ее работы и подходов к реализации приведены в следующих главах.

^ Концепция предлагаемой технологии

В этой главе описывается подход, положенный в основу предлагаемой технологии, и вводятся основные понятия (концепты) этой технологии. Также дается объяснение последовательности процессов, составляющих технологию.

^ Подход к анализу текстов

Технология "ТОМАТ" может быть классифицирована как основанная на использовании объектно-ориентированной продукционной системы. Для упрощения изложения в этом разделе будем считать, что обрабатывается текст на естественном языке, хотя технология применима к значительно более широкому классу задач. Для более ясного изложения концепции технологии многие детали метода анализа текстов, на котором основана технология, в этом разделе будут опущены. Как уже отмечалось, под методом анализа подразумеваются действия, выполняемые вычислительной системой для анализа текстов. Технология же описывает действия эксперта, строящего решение задач автоматической или автоматизированной обработки текстов.

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

На первом этапе текст обрабатывается компонентом технологии, называемым препроцессором, который преобразует текст в последовательность объектов, подобных объектам объектно-ориентированных языков программирования. Затем с помощью системы продукций (шаблонов) эта система объектов последовательно трансформируется путем применением шаблонов, и в конечном итоге превращается в сеть объектов, представляющих извлеченный из текста смысл. В некоторых системах обработки текстов, основанных на шаблонах, для обозначения таких объектов используется термин "объект", который происходит от английского слова "hit", в данном контексте означающего успешное применение шаблона. В частности, этот термин используется в работах, посвященных системе управления базами знаний "Абриаль" [Пацкин 2003].

Необходимо пояснить, что структура объектов, построенная в результате использования технологии, в общем случае не является семантической моделью текста. Во-первых, она не обязана представлять полную смысловую модель текста, в большинстве задач требуется извлечь из текста только определенную информацию (хотя формально в большинстве случаев возможна генерация исходного текста по построенной сети). Во-вторых, возможности такой структуры по представлению смысла текста несколько меньше, чем, например, у семантической сети ([Lehman 1992]), в основном благодаря фиксированному множеству отношений между объектами — фактически, только отношения "часть-целое" и "частное-общее" могут быть напрямую отражены в структуре объектов. Но метод анализа разрабатывался с целью предоставить удобный и мощный механизм именно для построения информационной структуры, причем достаточно эффективный и не основанный на полном многоуровневом анализе текста. Семантическая сеть же только описывает смысловую модель, но не предоставляет механизма ее построения.

Каждый объект обязательно является экземпляром некоторого класса. Классы ТОМАТа подобны классам объектно-ориентированных языков программирования — класс содержит описание полей данных, значения которых составляют объект. Классы ТОМАТа могут образовывать иерархию наследования, причем поддерживается множественное наследование — класс может иметь несколько базовых классов. Везде, где в технологии требуется объект некоторого класса, допускается объект этого и любого производного от него класса.

Объектно-ориентированный подход хорошо зарекомендовал себя в индустриальном программировании [Буч 2000], так как есть предположение, что человеческое мышление, по крайней мере в вопросах решения той или иной технической задачи, устроено именно по этому принципу. В любом случае, объектно-ориентированный подход крайне популярен при написании прикладных программ, в том числе решающих задачи искусственного интеллекта, и у большинства разработчиков имеется богатый опыт объектно-ориентированного проектирования, который предлагаемая технология позволяет использовать для решения задач анализа текстов. Надо отметить, что объектно-ориентированные программные интерфейсы для взаимодействия между компонентами, поддерживающими некоторую технологию, и даже объектно-ориентированная архитектура методов анализа, положенных в основу технологии, в понимании автора сами по себе не делают технологию объектно-ориентированной. Таковой ее делает именно использование объектно-ориентированного подхода для описания грамматики, по которой ведется анализ (системы классов и шаблонов), и, соответственно, наличие в реализации специального объектно-ориентированного языка.

Шаблон в некотором смысле можно назвать правилом, у которого в правой части стоит регулярное выражение, составленное из классов. Шаблон может примениться к списку объектов, если классы объектов соответствуют (с учетом наследования) классам, указанным в правой части правила. Узлами шаблона называются элементы правой части правила, каждый узел указывает на класс. Покрытием в ТОМАТе называется установление соответствия между объектами, к которым делается попытка применить шаблон, и узлами этого шаблона.

Левой частью правила является еще один класс — при успешном применении шаблона создается новый объект этого класса, а объекты, которые соответствуют покрытым объектам, становятся дочерними объектами для вновь создаваемого (погружаются в новый объект). Таким образом, происходит постепенное строительство деревьев из списка начальных объектов. Непосредственно применением шаблонов занимается компонент технологии, называемый исполнителем. Им управляет другой компонент — планировщик. Он принимает решение, где и какой шаблон следует применить, и представляет собственно алгоритм обработки. Описания классов и шаблонов являются той грамматикой, по которой идет анализ. Они образуют систему модулей, называемых банками, которые ссылаются друг на друга.

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

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

Рис. 1. Схема анализа текстов

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

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

1.  Разработать систему первичных (системных) классов и шаблонов.

2.  Реализовать препроцессор на основе этой системы.

3.  Разработать систему целевых и промежуточных классов и шаблонов.

4.  Подобрать либо реализовать подходящий планировщик.

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

Общая идея, а также цели, которым должна служить предлагаемая технология, излагаются в работе автора [Шевченко, Егорушкин 2004],представленной в научной сессии МИФИ 2004 года.

Важной особенностью технологии является использование недоопределенных значений в качестве значений полей объектов — такие значения представляются множеством, содержащим все варианты значения. Подробно ознакомиться с концепцией недоопределенности можно в работах [Нариньяни 1980а], [Нариньяни 1980б], [Нариньяни 1982], [Нариньяни 1986], [Телерман 1996].

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

О некоторых возможных применениях предлогаемой автором технологии автор рассказывает в докладе [Микрин, Шевченко 2003], вошедшем в сборник трудов международной конференции "Проблемы управления безопасностью сложных систем".

^ Основные понятия технологии

Итак, технология "ТОМАТ" оперирует несколькими специфическими для нее понятиями, такими как объект, шаблон, класс и т.п. По отдельности многие одноименные концепты используются и в других технологиях обработки текстов, хотя их семантика может несколько (а иногда и сильно) отличаться от принятой в ТОМАТе. Поэтому необходимо подробно рассмотреть все концепты ТОМАТа, дав им определения и описав их поведение.

Объекты

Начнем с того, что рассмотрим фундаментальное понятие ТОМАТа - объект. Это ключевой концепт технологии, так как вся обрабатываемая информация на любом этапе (что является характерной чертой ТОМАТа) представляется в виде системы объектов. Объект в общем случае порождается применением некоторого шаблона, причем некоторые, так называемые системные шаблоны, "применяет" (а точнее, заявляет, что объект образовался в результате применения) препроцессор на этапе подготовки исходных данных.

На объект можно смотреть с нескольких разных сторон. Если рассматривать ТОМАТ, как систему обработки текстов, а точнее, как систему построения неких информационных структур по информации из исходного текста, то объект — это ни что иное, как совокупность фрагментов исходного текста, и может быть представлен списком отрезков (начальных и конечных позиций в тексте). Объекты образуют иерархию вложения друг в друга (хотя не всякий объект обязан быть вложенным в какой-либо другой объект). Причем в дереве объектов листьями являются так называемые первичные объекты, представляющие в зависимости от конкретной задачи обработки текста отдельные слова или даже символы.

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

Получается, что информация, обрабатываемая ТОМАТом, всегда представлена как список деревьев объектов. В случае простого препроцессора начальный массив данных представляет просто список объектов (каждое дерево состоит всего из одного элемента). Более сложные препроцессоры, например, производящие морфологический анализ, могут строить более сложные начальные структуры.

Необходимо отметить, что технология "ТОМАТ" допускает многовариантный анализ — процесс применения шаблонов обычно неоднозначный, постоянно возникают альтернативы. Известно, что все способы ведения такого анализа можно разделить на два класса — одновременное построение альтернатив в параллельных пространствах, и последовательный перебор альтернатив с запоминанием информации, позволяющей отменить любое число шагов (бэктрекинг). В рамках технологии "ТОМАТ" можно пользоваться любым способом, в зависимости от характера решаемой задачи. Для обеспечения возможности вести анализ с построением всех вариантов деревьев, не производя откаты, допускается многократное вложение объектов друг в друга, то есть любой объект может иметь несколько родительских. Таким образом, система объектов представляет собой сеть, в вершинах которой находятся объекты, а дуги образуются в результате наложения друг на друга всех построенных к данному моменту деревьев объектов. При этом вводится отношение несовместимости между объектами: любые два объекта, имеющие общих детей-объектов, считаются несовместимыми, что делает невозможным их покрытие одним шаблоном (шаблон, проверяя возможность покрытия объектов узлами, дополнительно требует, чтобы никакие два объекта не были несовместимыми). Попутно отметим, что эти возможности не мешают вести анализ бэктрекингом.

Шаблоны

Другим фундаментальным концептом технологии "ТОМАТ" является шаблон. Вообще говоря, шаблон состоит из списка узлов, а каждый узел ссылается на некий класс. Кроме того, сам шаблон связан с некоторым классом. Опять же, как и в случае с объектом, шаблон можно рассматривать под разными углами зрения. Если воспринимать ТОМАТ, как продукционную систему, то шаблон — это ни что иное, как правило грамматики (продукция), которое имеет левую часть (класс шаблона) и правую часть — список узлов (каждый узел ссылается на класс). Правило может примениться к списку объектов, классы которых в соответствующем порядке совпадают с классами, указанными в узлах шаблона (точнее говоря, либо классы должны совпадать, либо класс узла должен быть базовым для класса объекта).

С другой стороны, шаблон можно рассматривать как конструктор класса. Действительно, в объектно-ориентированных языках программирования конструктор класса — это функция, обязательно вызывающаяся при создании объекта и производящая инициализацию данных объекта. Все это остается справедливым и для ТОМАТа. Можно считать, что тело шаблона (список узлов) представляет собой инициализатор для агрегированных объектов, которыми являются вложенные объекты. Кроме того, в шаблонах ТОМАТа могут находиться действия, осуществляющие присваивания полям создаваемого объекта, причем помещаемые в эти поля данные могут конструироваться с помощью выражений, ссылающихся на поля объектов, покрываемых узлами. Кроме присваиваний, действия также могут быть проверкой ограничений (логических выражений над теми же данными). Если ограничение не выполняется, то применение шаблона отменяется и объект не создается. Заметим, что есть принципиальное расширение возможностей шаблоны по сравнению с конструктором: возможные варианты списков вложенных объектов определяются не в классе, а в шаблоне, поэтому все объекты некоторого класса всегда имеют один и тот же набор полей, но в зависимости от шаблона, которым они были созданы, могут иметь разнотипные наборы вложенных объектов.

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

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

Классы

Основополагающим концептом ТОМАТа является класс. И опять же класс ТОМАТа можно рассматривать по-разному. Если придерживаться концепции объектно-ориентированного программирования, то класс ТОМАТа является классом объектов. Класс содержит описания полей объекта (каждое поле характеризуется именем и типом). Также класс может являться наследником одного или нескольких других классов, что означает, что он наследует все поля, действия и т.п. своих базовых классов.

Разумеется, выразительная возможность любого языка программирования, к которому можно причислить и язык, использующийся в технологии для описания классов и шаблонов, сильно зависит от предлагаемых в языке типов данных и операций над этими данными. Сразу оговоримся, что здесь не идет речь о типах, определяемых пользователем, то есть классах. В традиционных языках программирования общего назначения, таких, как Паскаль, типы обычно представляют скалярные числовые, строковые, символьные и т.п. значения. В языках, ориентированных на решение задач искусственного интеллекта, например, Лисп [McCarthy 1978] [Хювенен 1990] и Пролог [Bobrow 1984], предлагаются также встроенные в язык типы для списков значений. Однако операции для таких списков задаются явно, позволяя обращаться к нужному элементу списка и выполнять над ним те же скалярные операции, что и над обычным значением.

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

Уже много лет при решении некоторых научных задач применяется концепция недоопределенных вычислений. С использованием этой концепции, например, решались задачи финансового [Shvetsov 1997], [Нариньяни, Корниенко 1998], а также календарного [Борде 1991], [Borde 1993], [Нариньяни, Напреенко 1998] планирования. Новизной данной работы является в том числе применение этой концепции, изначально задуманной для вычислительных задач, для анализа текстов. Сама концепция была предложена А.С. Нариньяни (см., например, [Нариньяни 1980а], [Нариньяни 1980б]). Суть ее вкратце такова. Вместо того, чтобы работать со скалярной величиной, мы заменяем ее множеством значений. Считается, что это множество представляет собой набор возможных значений переменной наподобие множества элементарных исходов в теории вероятностей. В процессе вычислений значения переменных могут доуточняться (множества сужаются). Операции над такими переменными напоминают скалярные (например, для чисел это обычные арифметические действия), но их семантика формулируется как составление множества результата из результатов операции для каждого с каждым из значений аргументов.

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

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

Возможны также ситуации, когда некий класс B является базовым для классов D и E, а от них унаследован класс С. В этом случае в классе С будет ровно одна копия каждого поля класса B. Подобная схема наследования в языке программирования С++ называется "виртуальные базовые классы" [Страуструп 2001].

В С++ у программиста существует выбор: если в нашем примере класс B не был бы объявлен виртуальным базовым, то в объекте класса С было бы две копии подобъектов класса B — по одной для D и E. В зависимости от концептов, моделируемых классами, в разных случаях рекомендуется разная схема наследования. При проработке этого вопроса применительно к технологии "ТОМАТ" не было выявлено ни одного убедительного примера, требующего введения невиртуальных базовых классов (что, конечно же, не означает, что таких примеров не существует), поэтому в ТОМАТе базовые классы всегда виртуальные.

Другое видение класса позволяет считать, что класс — это средство группирования шаблонов. В некоторых задачах, решаемых с помощью технологии "ТОМАТ", достаточно использовать классы именно в таком смысле. Конечно, класс должен представлять некое понятие предметной области, например, для задачи синтаксического анализа текста на естественном языке классами могут быть слова (базовый класс), части речи, затем группы, обороты, и, наконец, предложения. В то же время существуют задачи, для которых достаточно формализма регулярных выражений, и вообще не обязательно иметь поля данных в классах.

Технология "ТОМАТ" предполагает, что шаблоны и классы группируются в банки — модули, которые могут использовать друг друга. Для того, чтобы произвести собственно обработку данных, необходимо сформировать проект — собрать полную систему банков, то есть такую, в которой не остается неразрешенных ссылок на используемые модули. Проект, таким образом, фиксирует, какие банки будут подключены к обработке, и какие версии банков следует использовать. Если реализация технологии, например, хранит банки в файлах, то проект может представлять собой список имен таких файлов.

Таким образом, проект ТОМАТа в конечном итоге является той грамматикой (системой продукций), по которой идет анализ данных, и в то же время представляет собой некую модель предметной области в отношении информации, которая извлекается из текста.

Blog

Технология построения многовариантных объектно-ориентированных структур текстов

Содержание