УДК 681.3.01:81.322.2 Е. Б. АРТАМОНОВ, Е. П. СТЕПУШКИНА, А. А. ЧЕРБУНИН
Национальный авиационный университет, Киев
МЕТОДЫ ПРЕДВАРИТЕЛЬНОЙ РЕСТРУКТУРИЗАЦИИ ТЕКСТА ПРИ ЛЕКСИЧЕСКОМ АНАЛИЗЕ
Темпы роста производительности компьютеров уже исчисляются не годами, а месяцами, но это, к сожалению, никак не сказывается на их интеллектуальных способностях. Естественный для людей способ общения и анализа текста до сих пор недоступен современным компьютерам и программному обеспечению. В данной статье рассматривается одна из основных проблем, возникающая при лексическом анализе текста – реструктуризация текста на естественном языке и предлагаются пути ее решения.
Введение
До сих пор одной из основных проблем автоматизации, которая не имеет четкого и аргументированного подхода, является задача лексического анализа текста на естественных языках (ЕЯ). Данная задача возникает при любой компьютерной обработке документов в информационно-поисковых и аналитических системах, когда необходимо выделить в тексте сложные элементы и специальные конструкции, отличающиеся особого вида написанием или несущие определенную смысловую нагрузку. Также без решения данной задачи нельзя обойтись при построении систем, которые проводят анализ текста на совпадения (раздел задач выявления плагиата и заимствования).
Не смотря на то, что компьютерный анализ текста на ЕЯ активно развивается в последние годы многими коллективами и современные вычислительные мощности позволяют применять для обработки больших массивов документов широкий класс математических методов, способствующих эффективному решению задач поиска, классификации, кластерного анализа, выявления скрытых закономерностей в данных и др. До сих пор внедрение лингвистической составляющей алгоритмов, которая является основой математических методов лексического анализа, представлена явно недостаточно, и это не позволяет достичь высокого качества работы прикладных систем.
При этом, предложенное около тридцати лет, направление исследований при лексическом анализе статистическими методами привел к тому, что компьютерная лингвистика оказалась невостребованной. Во многих известных русскоязычных системах подобного класса из лингвистического обеспечения используется лишь морфологический словарь, позволяющий отождествлять различные словоформы, тогда как алгоритмы синтаксического анализа реализованы исключительно в автоматических переводчиках и вызывают множество нареканий в связи с невысокой точностью [1]. Разработаны и реализованы десятки частных методов для узких и специфических задач, однако до сих пор количество так и не перешло в качество.
1. Реструктуризация текста при различных методах анализа текста
При решении задачи поиска соответствий в текстах (второй уровень поисковых систем) можно строить алгоритм отталкиваясь от следующих постулатов решения данной проблемы:
А. Решение задачи «в лоб», когда построение алгоритма основывается на полном переборе всех возможных вхождений одного текста в другой с выделением наиболее «ярких» (обычно по количественному критерию) участков соответствия.
Данная задача предполагает разбиение текста на структурные подгруппы: абзацы, предложения, слова (обратите внимание, что пропущен такой структурный текстовый элемент как словосочетания – данное допущение увеличивает число тактов выполнения программы при выявлении всевозможных вхождений одного текста в другой, однако упрощает алгоритм реструктуризации текста сводя его к элементарным правилам). Данный подход увеличивает время проверки файлов «1 на 1», но ощутимо выигрывает во времени, которое затрачивается на предварительную обработку текста (при больших объемах текста время реструктуризации при «интеллектуальном поиске» растет экспоненциально).
Б. Решение на основе «интеллектуального поиска». Когда анализ текстов происходит с использованием элементов графематики и морфологических правил языка. Формально целью синтаксического разбора является построение дерева зависимостей между словами во фразе. В случае удачи предложение сворачивается в полносвязное дерево с единственной корневой вершиной. Поскольку одна словоформа может соответствовать нескольким грамматическим формам слова, в том числе для различных слов (например, «стали» у существительного «сталь» и глагола «стать»), в ходе анализа необходимо производить свертку предложения для всех возможных вариантов. Те же из них, которые приводят к максимальной свертке фразы (с минимальным числом висячих вершин), предлагается считать наиболее достоверными при разборе предложения.
Порядок применения правил разбора управляется его алгоритмом, который на каждом шаге проверяет возможность применения следующего правила к очередному фрагменту фразы (двум-трем словам, знакам препинания и т. п.). В случае удачи фрагмент сворачивается. Обычно это приводит к его замене одним главным словом, т. е. удалением подчиненных слов. После чего разбор продолжается. Если дальнейшее применение правил невозможно, на любом из шагов совершается откат. При этом последний свернутый фрагмент восстанавливается, и предпринимается попытка применить другие правила. Окончательным вариантом разбора следует считать такую последовательность применения правил, которая приводит к максимальной свертке предложения [1].
Однако и тот и другой метод требуют предварительной реструктуризации (подготовки) текста. Рассмотрим некоторые общие правила и методы реструктуризации текста для проведения лингвистического анализа.
2. Решение задачи разделения текста на предложения
Это является одной из основных задач в реструктуризации текста. Но не смотря на кажущуюся простоту данной задачи она нетривиальна и может иметь ряд исключений и неоднозначностей.
В зарубежных работах эта задача решается двумя основными способами. В первом случае используется обычный текстовый редактор, в который загружается разбираемый текст, а затем оператор-лингвист вручную специальными знаками размечает морфологическую и синтаксическую структуру каждого предложения:
[N It_PPII1 N]
[V indicates_VVZ]
[Fn [Fn&whether_CSW]
[N a_ATI call_NN1 N]
[V completed_VVD successfully_RR V]Fn&]
or_CC
[Fn+if_CSW
[N some_DD error_NN1 N] @
[V was_VBDZ detected_VVN V]
@[Fr that_CST
[V caused_VVD
[N the_AT call_NN1 N]
[Ti to_TO fail_VVI Ti]V]Fr]Fn+]
(пример взят из работы [4]). Здесь скобки отмечают границы синтаксических групп, а метки (выделены прописными буквами) — морфологические признаки соответствующих текстовых единиц. Символ “@” показывает наличие смежного узла для разрывных составляющих.
Таким образом, текст на ЕЯ превращается в текст на некотором формальном языке (типа языка правильных скобочных структур), который на этапе обучения сканируется анализатором (с помощью любой схемы анализа формальных языков, например, стековой) и используется для построения набора деревьев принятия решений [3].
При другом подходе к реструктуризации текста требуется специальный модуль, обеспечивающий преобразование текста на ЕЯ непосредственно в представление его морфологической и синтаксической структуры. Такой модуль может быть сделан полуавтоматическим, т. е. в нем может быть задействован примитивный структурный анализатор, который будет “подсказывать” оператору варианты разбора или в автоматическом режиме, когда все решения будут приниматься на основе заранее разработанного алгоритма. При таком подходе обеспечивается не только более высокая производительность труда оператора или его полное отстранения от задач реструктуризации текста, но и возможность обучения анализатора на полученном материале (за счет отсутствия фазы сканирования разобранных фрагментов при полуавтоматическом режиме разметки).
Очевидным недостатком первого подхода является высокая трудоемкость создания структуры текста, и, самое неприятное, дополнительные возможности внесения ошибок в формируемую структуру. Ошибки на этапе реструктуризации наиболее опасны, поскольку они будут учтены при возможном обучении анализатора и “повторены” им в последующей работе; не существует способа исправить их в уже обученном анализаторе, и единственным способом их исправления является повторное обучение анализатора на исправленных правилах реструктуризации.
Недостатком второго подхода является, во-первых, необходимость разработки дополнительного программного модуля, и, во-вторых, плохая переносимость полученной структуры, поскольку она оказывается привязанной к конкретному формату, в котором модуль сохраняет синтаксические структуры. Тем не менее, наиболее прогрессивным считается второй подход (особенно при современных мощностях технического обеспечения).
При описании программной реализации в общем виде можно определить следующие шаги программы. Сначала ищется конец предложения и в найденном месте ставится метка конца предложения, после этого находится начало предложения, где ставится метка начала предложения, после чего осуществляется переход к поиску конца следующего предложения. Алгоритм основывается на следующих постулатах:
1. Начало текста совпадает с началом первого предложения, конец текста – с концом последнего.
2. Предложение всегда начинается с большой буквы.
3. Предложение не бывает больше одного абзаца.
4. Предложение не может состоять только из знаков препинания.
Однако даже эти простейшие постулаты имеют ряд исключений, которые должны быть предусмотрены в алгоритме программы.
Так, например, при описании языков программирования часто встречаются предложения, которые описывают знаки разделения, которые допускаются в данном языке. При этом нарушается сразу два постулата: во-первых, четвертый постулат, так как в данном представлении через запятую или точку с запятой идет набор знаков препинания, во-вторых, первый, так как не редко для описания данного набора знаков препинания выделяется отдельный абзац.
В виде примера рассмотрим простейшую реализацию функций разбиения текста на предложения. Так при сканировании предложения, если анализатор встречает подряд два символа перевода строки, то он должен считать данное предложение заголовком; при этом динамический массив лексем полностью очищается и анализ предложения начинается заново с текущей позиции. Анализатор должен содержать начальную функцию (МАРКИРОВКА_ПРЕДЛ), на вход которой подается номер строки и функция возвращает истину, если эта строка содержит символ "?", "!", "." или многоточие и вспомогательную функцию определения конца предложения (КОНЕЦ_ПРЕДЛ), которая возвращает истину в двух следующих случаях:
1. Если для этой строки верна функция МАРКИРОВКА_ПРЕДЛ и контактно справа нет закрывающей кавычки (если предложение закавычено, закрывающая кавычка входит в это предложение);
2. Если строка является закрывающей кавычкой, а контактно слева стоит строка, для которой верно МАРКИРОВКА_ПРЕДЛ.
Но найти конец предложения в тексте тоже не так просто, как может показаться. Восклицательный или вопросительный знак наверняка означают конец предложения, но вот точка может стоять и после сокращения, и в середине десятичной дроби. Например, в следующем фрагменте:
В 2005 г. доход предприятий г. Киева увеличился на 17.2 процента.
точка встречается четырежды, и только в четвертом случае она означает конец предложения. Для точного ответа на вопрос, находится ли данная точка в конце предложения, потребуется выполнить синтаксический (и даже, возможно, семантический) анализ всего фрагмента. Но ведь решение должно быть принято на этапе лексического анализа! Поэтому в анализаторе должна быть введена простейшая проверка: лексема, стоящая непосредственно перед точкой, должна быть грамматически правильным словом и содержать хотя бы одну гласную. Такой проверкой удается отсечь многие сокращения, употребляемые с точкой на конце:
г., с., д. т.н, проф., т. д. , т. е. , др.
Разумеется, такая проверка не гарантирует правильность результата. С одной стороны, сокращение или число с точкой могут действительно стоять в конце предложения, а с другой — некоторые сокращения (например: грн., проч.) эту проверку проходят. Тем не менее опыт работы с документами подтверждает эффективность такой проверки [2].
Тогда для реализации алгоритма разбиения текста на предложения необходимо выполнить следующий набор действий:
1. Пусть i – текущая строка между НАЧАЛО_ТЕКСТ и КОНЕЦ_ТЕКСТ.
2. Если на строке i стоит метка начала абзаца, тогда нужно пройти назад все пробелы и длинные разделители и дойти до конца предыдущего абзаца. Если в конце абзаца (до первого слова) стоит строка, которая удовлетворяет КОНЕЦ_ПРЕДЛ, тогда нужно поставить КОН_ПРЕДЛ[j] этой строке, иначе нужно поставить КОН_ПРЕДЛ[j] на конец предыдущего абзаца.
3. Если на строке i стоит метка макросинтаксическая метка определяющая абзацы, заголовки, которые называются условно предложениями, тогда нужно сделать то же самое, что и в пункте 3, только надо учесть, что данная метка ставится в конце абзаца, а не в начале (как в пункте 3).
4. Если до начала текущего предложений стояла открывающая скобка, и текущая строка указывает на слово до соотв. закрывающей скобки, тогда нужно поставить КОН_ПРЕДЛ[j] на закрывающую кавычку, а текущую строку сместить на ближайшее после закрывающей кавычки слово.
5. Увеличиваем i и j (если был выявлен признак конца предложения) и переходим к пункту 1.
3. Подключение словарных модулей
Подключение словарных модулей является «привлекательной» особенностью методов «интеллектуального поиска».
Словарный модуль должен производить сравнение цепочек лексем, заданных своими описаниями, с цепочками лексем из заданных словарей – словарными образцами. Каждая распознанная цепочка выделяется в новый объект-лексему, который получает свое описание, используемое на следующем этапе обработки. Результатом работы модуля обычно является граф описаний.
Словарные образцы объектов позволяют задавать три способа распознавания: сопоставление всех лексем в цепочке с учетом морфологии (во всех грамматических формах), сопоставление всех лексем в заданных грамматических формах независимо от регистра, точное сопоставление цепочки "как есть".
В результирующее описание выделенного объекта должны входить:
· текст строки, соответствующей цепочке – задается в качестве синонима в словаре или соответствует исходному тексту цепочки;
· грамматические атрибуты – наследуются от заданного слова в цепочке либо задаются явно в словаре;
· семантический тип – задается в словаре;
· ряд прочих атрибутов [5].
При этом отдельно задачей является наполнение баз данных для работы словарных модулей. В простых поисковых системах предусмотрен ручной ввод информации в БД. Пользователь вводит основные реквизиты каждого документа в поле предварительно подготовленной структуры БД. Но в большинстве развитых систем загрузка информации и создание БД осуществляется автоматически.
Создание реляционной БД состоит из двух основных операций:
· копирование исходной информации во внутренний формат системы;
· создание поискового индекса, в котором каждый элемент текста - слово, число и т. п. - привязывается к соответствующей записи.
Обычно реляционная БД содержит 5 файлов: файл идентификации БД, файл документов, файл входов в документы, файл словаря БД, файл инверсных массивов поискового индекса. Основной объем БД занимают файл документов и файл поискового индекса, каждый из которых занимает 60-80% объема исходных загружаемых файлов.
Выводы
В заключение отметим, что, несмотря на ограниченность возможностей анализаторов текста, чаще всего работающих пока без привлечения семантики, их применение открывает новые возможности для систем компьютерного анализа текста. Однако ученые всего мира до сих пор стоят у истоков данной проблемы. Что вызвано не так ограниченностью математических методов решения задач данного класса, как сложностью реализации человеческой логики на машинном уровне, при котором компьютерные модели или оказываются излишне громоздкими, или не обладают всем набором требуемых характеристик. О чем говорят примеры, представленные в данной статье, указывающие на проблемы и неоднозначности даже на этапе реструктуризации текста, который является первым шагом при лексическом анализе текста.
Литература
1. А. Е. Ермаков. Компьютерная лингвистика и анализ текста. Мир ПК, №
2. , , . Лингвистический процессор для информационно-поисковой системы // Компьютерная хроника, 1998. № 11 - стр.
3. , , Вероятностный синтаксический анализатор для информационно-поисковой системы. Компьютерная хроника N1, 1999
4. D. M.Magerman. Natural Language Parsing as Statistical Pattern Recognition. // A dissertation submitted to the department of computer science at the committee on graduate studies of Stanford University, 1994. // Опубликовано на сервере www. xxx. lang. gov/cmp. lg.
5. , , Митюнин и информационная безопасность правоохранительных органов: XI Международная научная конференция. Сборник трудов - Москва, 2003
