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

На правах рукописи

ГРИГОРЬЕВ АЛЕКСАНДР СЕРГЕЕВИЧ

РАЗРАБОТКА МЕТОДА И СОЗДАНИЕ СИСТЕМЫ ПОЛНОТЕКСТОВОГО ПОИСКА НА ОСНОВЕ СТАТИСТИЧЕСКОЙ ОБРАБОТКИ ОГРАНИЧЕННОГО КОНТЕКСТА СЛОВА

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва - 2006

— -/с/ 9-

Работа выполнена в Московском государственном техническом университете им. Н.Э. Баумана.

Научный руководитель: доктор технических наук, профессор

Б.Г. Трусов

Официальные оппоненты: доктор технических наук, профессор

Я.Л. Шрайберг

кандидат физико-математических наук В .И. Шабанов Ведущая организация: НТЦ «Информрегистр»

Защита диссертации состоится 29 июня 2006 года в 14:30 на заседании диссертационного совета Д 212.141.10 в Московском государственном техническом университете им. Н.Э. Баумана по адресу 107005, Москва, 2-я Бауманская ул., д. 5.

С диссертацией можно ознакомиться в библиотеке Московского государственного технического университета им. Н.Э. Баумана.

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

Автореферат разослан 15 июня 2006 г.

Ученый секретарь диссертационного совета к.т.н., доцент

С.Р. Иванов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы. Постоянное увеличение объемов хранилищ информации повышает роль поисковых средств, используемых для определения интересующей пользователя части документов. Поиск и предоставление документов читателям чаще всего ограничены описаниями документов, как правило, включающими название издания и его авторов, которые недостаточно полно отражают содержание документа. Для более полного описания документа он снабжается списком ключевых слов и словосочетаний, которые отражают тематику документа. Выделение таких слов и словосочетаний обычно выполняется авторами или библиотекарями. С увеличением количества документов, хранящихся в информационных фондах, задача построения списков ключевых слов и словосочетаний усложняется. Поэтому в настоящее время существует потребность в создании поисковой системы, автоматически выявляющей в текстах документов ключевые слова и словосочетания для обеспечения высокой степени релевантности результатов поиска сформулированным пользователем запросам. Запрос пользователя обычно формулируется в виде строки, содержащей перечисление слов. По аналогии с выделением слов и словосочетаний в текстах документов ключевые слова и словосочетания должны выделяться и в запросах пользователя, сформулированных на естественном языке. Под естественным языком понимается язык, который используется пользователем при общении с другими людьми.

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

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

Для достижения этой цели в диссертации решены следующие задачи:

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

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

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

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

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

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

Методы исследования. При решении поставленных задач в данной работе использованы элементы комбинаторного анализа, теоретико-множественный аппарат, статистические методы и теория автоматической классификации. При разработке программного обеспечения применялись методы объектно-ориентированного и функционального программирования с использованием сред разработки Microsoft Visual Studio.NET и СУБД Microsoft SQL Server. Научная новизна.

В результате выполненной работы получены новые научные результаты:

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

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

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

Основные положения, выносимые на защиту:

• метод статистической обработки ограниченного контекста слова;

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

• метод получения и сравнения структур, использующих сочетания слов для описания текста документов и поискового запроса;

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

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

Апробация и внедрение результатов работы. Полученный в результате выполненной работы программный комплекс внедрен и используется в рамках единой Автоматизированной Библиотечной Информационной Системы МГТУ им. Н.Э. Баумана. Разработанные методы, алгоритмы и модели использованы при создании системы поддержки фонда электронных документов. Основные результаты работы докладывались и обсуждались на 6, 7, 8-м всероссийских научно-практических семинарах «Новые информационные технологии», Москва, 2003 - 2005.

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

Структура и объем диссертации. Диссертация состоит из введения, четырех глав и списка литературы из 113 наименований. Общий объем работы составляет 158 страниц, включая 39 рисунков и 30 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе дана математическая постановка задачи, проведен анализ литературных источников, приведен обзор стратегий текстового поиска и детально рассмотрены методы обработки текстов. Рассмотренная в работе модель естественного языка L=L(W, С) определяется множеством слов W и набором связей С, объединяющих слова в осмысленные обороты и предложения. Множество текстов Т на естественном языке L определено как T=T(L). Для каждого текста teT строится структура Mh описывающая слова этого текста vv,e W, и взаимосвязи этих слов с,еС„ причем W^Wи CtÇzC.

Если пересечение языка запроса и языка текста пусто, множество результатов поиска пусто, поэтому множество запросов Q, адресуемых поисковой системе, также формулируются на языке L, то есть Q-Q{L). Каждый запрос qeQ преобразуется в структуру Мч, описывающую связи cqeCg между словами Wqе Wq, причем WqçzW и С?сС. Построенные структуры, описывающие множество документов и запросов формируют над языком специфичный для каждого метода поиска набор связей С между словами W языка L.

Задача поиска по запросу q состоит в том, чтобы построить структуры Мч и М, и из множества текстов Г выбрать такое подмножество TRçzT, что элементы структуры Mq входят в структуру М, для каждого текста Найденные таким образом документы i оцениваются по величине скалярного значения функции релевантности R{q, t) поисковому запросу q. Эта функция имеет тем большее значение, чем больше элементов структур, описывающих документы и запрос, совпадают. Известные алгоритмы полнотекстового поиска различаются способами построения структур Мч и М„ а также видом функции релевантности R.

Выполненная в работе классификация методов поиска текстовой информации делит их на булевские, формально-грамматические, статистические, алгебраические и лингвистические. Булевские методы учитывают при сравнении запросов с текстом документов слова, как независимые объекты. Документ признается соответствующим запросу, если слово запроса найдено среди слов документа. Практически данный метод реализован в алгоритмах прямого поиска (Д. Кнут, Н. Вирт, Р. Седжвик) и алгоритмах, использующих инвертированный список (Т.П. Лун, С. Брин, JI. Пейдж, И. Сегалович). В формально-грамматических методах для определения связей слов в предложениях составляются формальные пра-

вила обработки предложений языка аналогично правилам грамматик, описывающим формальные языки. Практически данный подход реализован в методе, использующем структурную схему предложения (В.А. Кршценко) и вероятностно-грамматическом методе (A.B. Брик). Статистический подход подразумевает использование функции оценки связности слов. Формально-грамматическая модель может быть дополнена использованием функции вероятностной оценки связности слов для учета ассоциативных связей между словами (В.И. Шабанов). Другой метод статистического ранжирования текстов по степени соответствия запросу основан на определении «различительной силы» слов (Т. Джойс, Р. Нидхэм, Дж. Солтон). Алгебраические методы включают в себя алгоритмы искусственного интеллекта. В частности, имитационный подход (Ф.С. Файн), адаптивное распознавание образов, построение нейронных сетей (Е. Шикута) позволяют, не акцентируя внимание на формируемых правилах поиска, моделировать обучение человека языку по принципу «черного ящика». На стыке алгебраических и статистических находится вероятностный метод обучения языку (JI.A. Растригин), получивший распространение в генетических алгоритмах. Лингвистический подход занимает особое место среди методов обработки текстов (Э.В. Попов, H.H. Леонтьева) в связи со сложностью применяемого в нем описания языка. Реализующие данный подход модели пока что используются только в ограниченных предметных областях а, зачастую, и не доводятся до практической реализации, как, например, уникальная модель «Смысл-Текст» (И.А. Мельчук, А. Жолковский).

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

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

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

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

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

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

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

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

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

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

Предложение ^-

Т т -

| Группа текстов ^-Сочетание слов

| Запрос |

•—«(Слово! [Синоним^

Рис. 1. Логическая диаграмма сущностей структуры хранения данных

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

Рис. 2. Общая функциональная схема системы обработки текста и поиска Проанализированные тексты и запросы представляются в виде списков

предложений (рис. 2). Предложения образуют списки слов. Слова заполняют словарь системы. Слова предложений используются для составления всех возможных сочетаний этих слов.-Отобранные из них устойчивые сочетания слов позволяют определить степень сочетаемости слов в предложениях и обнаружить контекстно-зависимые синонимы. Контекстно-зависимыми синонимами признаются главные слова в устойчивых сочетаниях, отличающихся в одном слове. Главным называется слово, которое при анализе текстов чаще других слов появляется в этом сочетании и реже других слов появляется в других сочетаниях.

Статистическая обработка текста

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

¿»^■МоЬ^. (1)

где V? - слово в словаре; Ртах - наибольшее значение частоты повторения слова м> (то есть отношение числа появлений слова -м/ в документе к количеству слов в этом документе) среди всех документов фонда Т\ Ыт - число документов в фонде Т-,И- число документов фонда, в которых встретилось слово Ь — настроечный коэффициент, позволяющий регулировать влияние распространенности слова в текстах фонда на значение функции значимости.

Практика показала, что частота появления слова в документе находится в интервале [0; 0,1]. Доля документов, в которых встречаются те или иные слова, лежит в интервале (0; 1] (рис. 3).

гОДб

0,10 0,00

ОД 4 0,12 ОД

0,08 в'(к>) 0,06 0,04 0,02 О

1 0,8 0,6 0,4 0,2

Рис. 3. График функции значимости слова

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

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

дельных документов.

Слова, имеющие высокую значимость, используются для составления сочетаний слов. Выделенные из них устойчивые сочетания заносятся в таблицу устойчивых сочетаний слов (М). Для всех слов w устойчивых сочетаний т вычисляется степень их статистической сочетаемости A(w, т), используя функцию сопряженности Чупрова.

А(щт) = --У" , (2)

2 Pm+Pw+P„

где pwm - частота совместного использования слова w и сочетания т (отношение количества сочетаний т к общему количеству всех сочетаний); pw - частота использования слова w в сочетаниях, отличных от т (отношение количества появлений этих сочетаний в текстах к общему количеству всех сочетаний); рт - частота использования в тексте сочетания т (отношение количества повторений этого сочетания в текстах к общему количеству всех сочетаний).

Функция статистической сочетаемости A(w, т) слов использована для построения иерархии подчинения слов в содержащих их сочетаниях. Это позволяет различать контексты слов, используемых в разных предметных областях и различных языках.

Объединение схожих по написанию слов

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

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

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

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

В предлагаемом методе использован кластерный анализ для автоматического группирования документов. Для каждого документа ie Т строится вектор, называемый профилем документа P(t), в котором каждый элемент хранит значение функции K{t, m), выражающей степень связности текста t с каждым соче-

танием слов т из множества всех устойчивых сочетаний М. Значение функции K(t, т) определено как доля предложений текста t, в которых встретилось сочетание слов т.

где Н, — множество предложений текста t, М, — множество устойчивых сочетаний, встретившихся в тексте t. Если г"-е предложение текста t содержит сочетание т, то v,=l. В противном случае - v,=0.

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

Обработка естественно-языкового поискового запроса

Из слов текста запроса q формируется список сочетаний слов Мг Алгоритм составления сочетаний для запроса совпадает с алгоритмом, описанным для смыслового фрагмента текста. Полученный из слов запроса набор сочетаний расширяется, используя словарь синонимов. Для каждого сочетания теМ9, в Mq добавляются сочетания, образующие с ним контекстно-зависимые синонимы.

На первом этапе поиска по сочетаниям определяется список групп, содержащих эти сочетания целиком или частично. На втором этапе для всех текстов документов t полученных групп вычисляется значение функции релевантности R(q, t), зависящей от числа совпадений в наборах сочетаний слов, полученных из текста запроса (Мя) и текста документов (М,). Полученный список документов, упорядоченных по значению функции релевантности, является результатом поиска.

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

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

Деление слов на значимые и незначимые

Область значений функции значимости S'(w) находится в области неотрицательных действительных чисел. Для разделения слов на значимые и незначимые введено пороговое значение функции значимости S„opoe. Все слова со значением функции значимости S(w) (см. 1), превышающим Snop<x являются значимыми и используются при составлении сочетаний слов.

Выявление устойчивых сочетаний слов

При поиске устойчивых сочетаний формируются все возможные сочетания слов каждого смыслового фрагмента текста. В данной работе единицей смысловой фрагментации текста является предложение. Из последовательности слов предложения Н=<м>1, и^..., и;/,... и>Л> длиной N составляются все сочетания длиной от 1 до К. Длиной сочетания называется количество слов в сочета-

(3)

(4)

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

Группирование документов по их профилям

Для определения степени связности всех текстов из Г с каждым сочетанием из М строится таблица Р, строки которой проиндексированы номерами текстов, а столбцы — сочетаниями слов из М. Таким образом, к-я строка Рк таблицы Р является профилем документа Т. На пересечении строки профиля Р* и столбца некоторого сочетания слов т&М записывается значение функции Л"(4, т) связности текста 4 и сочетания т (см. 3).

Для вычисления степени схожести пары текстов /„еГпри к, ие[1; Л^] их профили Рк и Р„ сравниваются с использованием функции Жаккара, значения которой образуют матрицу /, строка и столбец которой проиндексированы номерами текстов. Эта функция содержит операции пересечения и объединения векторов профилей документов. В программной реализации пересечение вычисляется как покомпонентное произведение векторов профилей, а объединение — как сумма этих векторов. Формула для заполнения ячейки таблицы I, находящейся на пересечении Аг-ой строки и л-го столбца, имеет вид:

Матрица / коэффициентов связности текстов является симметричной относительно главной диагонали, поэтому рассматривается только ее часть, расположенная выше главной диагонали. Для группирования текстов последовательно рассматриваются все строки таблицы /. Все тексты t„ (п>1), для которых указанный в этой строке коэффициент связности с первым текстом // больше порогового значения 1е, образуют с этим текстом группу. Аналогично рассматриваются все последующие (к-е) строки и указанные в них коэффициенты связности с текстом tk остальных текстов tm п>к. Если ни один текст t„ из строки не образует группу с главным текстом строки, и главный текст до этого не был добавлен ни в одну группу, то он образует группу, состоящую только из самого себя. Так как операция создания группы выполняется для каждой строки таблицы /, максимальное количество групп текстов не превышает количество текстов. При этом текст может входить в несколько групп.

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

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

(5)

равное 1 расстояние редактирования с главным словом. Слова, имеющие расстояние редактирования, не превышающее р, признаются родственными, если входят в сочетания, различающиеся в одном слове. Существенно, что редактированию подвергаются только символы, занимающие в слове w позиции в интервале (IJ2+A¡; /„], где 1Ш- длина анализируемого слова, а Д;- определяет длину варьируемой суффиксной части слова. Все найденные слова включаются в эту группу. Если какое-то из найденных слов уже входит в некоторую группу, все слова той группы также перемещаются в формируемую группу.

При построении иерархии подчинения слов в сочетании рассматриваются устойчивые сочетания максимальной длины К. Для каждого слова w устойчивого сочетания т уровень подчинения определяется по значению функции A(w, т). Слово, имеющее наибольшее значение этой функции — главное в сочетании. Остальные слова аналогично рассматриваются в рамках его подсочета-ния длины (К-1), полученного из исходного удалением главного слова. Значение A(w, т) сохраняется в таблице сочетаний.

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

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

Все документы t из списка групп, полученного на первом этапе обработки поискового запроса, упорядочиваются по убыванию значения функции релевантности R(q, t) запросу q. Значение функции релевантности R{g, t) вычисляется как сумма относительного числа совпадений сочетаний различной длины /е[1; К\ для предложений текста M¡(1) и запроса МЯ(Г), умноженного на весовую функцию в (/), значение которой возрастает с увеличением длины сочетания.

«*i>-t(lM<m"'mw) <6)

№ tr( \М,(П\ )

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

Описание тестового набора документов

Разработанная система предназначена для использования в постоянно пополняемых фондах документов. Поэтому использованный при испытаниях информационный фонд постепенно наращивался и достиг 572 397 документов общим объемом 334 Мбайта, что соответствует примерно 300 ООО страниц печатного текста. В этот набор включены технические статьи (10 статей), художе-

чатного текста. В этот набор включены технические статьи (10 статей), художественные произведения (21 документ) и реферативные статьи ВИНИТИ. Количественно рефераты распределены по предметным областям следующим образом: автоматика —77675, биология — 69729, сварка - 18447, экономика промышленности - 33424, физика - 70773, информатика — 19804, коррозия и защита от коррозии — 40640, математика - 26179, машиностроение - 100887, механика -84645, охрана окружающей среды — 22146, вычислительные пауки - 8017. Основную часть тестового информационного фонда составили рефераты, так как использование относительно коротких текстов (1-2 страницы) облегчает экспертам задачу определения релевантности документов запросам.

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

Для определения порогового значения функции значимости S„npai, все слова словаря, полученного при обработке тестового набора текстов, были упорядочены по возрастанию ее значения, вычисленного для каждого слова. Экспертом проанализирован полученный список, в результате чего определена граница, ниже которой располагаются слова, способные нести самостоятельный смысл. Для этих слов, являющихся значимыми, значение функции значимости превышает 0,05. Поэтому в данной работе S„npM принято равным 0,05 (5,по^ог=0,05).

Для определения значения параметра А/, ограничивающего длину варьируемой суффиксной части слова, было проведено группирование форм родственных слов с расстоянием редактирования равным 1 при Дг=1,2,3,4. По результатам проведенных экспериментов определено, что с увеличением значения А/ (при Д/>2) качество группирования различных форм слова растет незначительно, а количество сгруппированных слов при этом стремительно снижается (рис. 4). Поэтому в данной работе А/ принято равным 2 (Д/=2).

ы та - о

й G g

о о а

и * 5

' Длина варьируемой суффиксной части слова, символов ^

- Сокращение количества заглавных слов в словаре * Доля верно сгруппированных слов_

Рис. 4. Определение длины варьируемой суффиксной части слова Выбор допустимого расстояния редактирования р, позволяющего признать слова родственными, обусловлен результатами эксперимента, в котором оценивалось качество поиска родственных слов с учетом их статистической сочетаемости с одинаковыми словами при значениях параметра р=1, 3, 4, 5. В результате эксперимента (рис. 5) определено, что увеличение р вызывает резкое снижение качества группирования слов. Поэтому для расстояния редактирования р выбрано минимальное значение 2 (р=2).

Расстоянии

е редактирования, символов

- Сокращение количества заглавных слов в словаре •Доля верно сгруппированных слов _

Рис. 5. Определение ограничения расстояния редактирования Для определения ограничения на длину К составляемых сочетаний слов проведены эксперименты по составлению словаря контекстно-зависимых синонимов, используя таблицы сочетаний слов различной длины К (для К=2, 3,4, 5). Из приведенных на рис. 6 графиков следует, что при К>3 точность определения синонимов почти прекращает рост. При этом количество полученных контекстно-зависимых синонимов снижается, поэтому принято ограничение на минимальную длину сочетаний, используемых при поиске синонимов, в 4 слова (А>3).

90

30

а X

X о, 3 а еГ о

« га д о г

§ ч (и 53

Ч О

£ 3 т Я К и

Количество слов в устойчивом сочетании | —И—Количество найденных пар синонимов ~+~Доля верно выделенных синонимов |

Рис. 6. Определение длины сочетаний слов С увеличением длины сочетания растет число составляемых сочетаний слов. Но сочетания большой длины редко повторяются и не могут служить источником данных о статистической сочетаемости слов. Например, среди сочетаний из 5 слов в текстах тестового информационного фонда повторяющиеся составляют менее 6%. Поэтому устанавливается ограничение на максимальную длину сочетания, равное 4 (К=4).

При определении количества повторений и сочетаний слов в текстах, достаточного для признания сочетания устойчивым, исследовано количество найденных контекстно-зависимых синонимов и качество их определения при числе повторов и= 1,2,3,4,5. Увеличение количества повторов при ££>1 незначительно увеличивает качество выделения синонимов (рис. 7). При этом существенно сокращается количество найденных синонимов. Таким образом, устойчивыми признаются сочетания, повторяющиеся больше 1 раза (11=2).

о

1 2 3 4 5

___Количество повторений устойчивых сочетаний_

Количество найденных пар синонимов —♦—Доля верно выделепных синонимов

Рис. 7. Определение достаточного числа повторений сочетаний слов Для выбора значения параметра /„ влияющего на количество создаваемых групп и насыщенность этих групп текстами, проведены эксперименты с различными значениями 1С е [0; 1]. Из результатов экспериментов следует, что уменьшение значения 1Ё повышает количество текстов в каждой группе (рис. 8). Это сокращает время поиска соответствующих запросу групп текстов (первый этап обработки поискового запроса). Увеличение значения /£ снижает количество текстов в каждой группе, что сокращает время, необходимое для вычисления значений функции релевантности для текстов найденных групп (второй этап).

1 2

* га

1

0,8 0,6 0,4 0,2 0

с " <-,

к Б

о. о х

§ н

3 >д

§ I

И

0,1

0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

_Граничное значение коэффициента схожести текстов_

| —И— Время поиска —♦— Количество групп, приходящихся на каждый текст [

Рис. 8. Определение граничного значения для группирования текстов

При 0,2</£<0,3 время поиска минимально при наибольшем количестве групп текстов, поэтому в данной работе 1С принято равным 0,25 (7£=0,25).

Экспериментальные оценки требуемых ресурсов

Группирование схожих по написанию форм родственных слов, позволило существенно снизить количество слов, используемых для составления сочетаний, так как вместо всех форм слова используется одно заглавное слово. Для рассмотренного тестового набора документов количество обрабатываемых слов сократилось в 2,05 раза. Во столько же раз снизилось время составления сочетаний и дисковое пространство, требуемое для их хранения.

При последовательном добавлении документов в хранилище системы было обнаружено снижение темпов роста количества слов в словаре с каждым новым текстом (рис. 9).

§ 800000

5 о бооооо

| § 400000

Р 5 200000 -

о

10000000 20000000 30000000 40000000 Количество слов во всех обработанных текстах фонда

50000000

Рис. 9. Зависимость количества слов в словаре от объема обработанного текста Количество слов (уникальных комбинаций символов), занесенных в словарь в результате анализа тестового набора текстов, составило чуть более 1% количества слов в обработанном тексте.

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

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

-т 25000000 9 ~ 20000000

8 V

я §

а .15000000 § 10000000 5000000

о

10000000 20000000 30000000 40000000 50000000 Количество слов во всех обработанных текстах фонда

■Сочетания из 1-4 слов

"Повторяющехся сочетания из 1-4 слов

Рис. 10. Зависимость количества сочетаний от объема обработанного текста Сохраняя тенденцию к снижению темпов роста количества сочетаний, при достижении объема текста в 35 000 000 слов скорость роста количества повторяющихся сочетаний увеличивается. После обработки 35 000 000 слов с каждым новым предложением создается все меньше новых сочетаний и собирается все больше информации о контексте употребления уже сохраненных сочетаний слов. Таким образом, с увеличением объема фонда документов не происходит пропорционального роста объема потребляемых ресурсов, а интенсивность его увеличения постоянно снижается с пополнением фонда новыми документами. Оценка качественных показателей разработанного метода поиска Проведенная проверка качества группирования 631 873 слов в 307 193 группы родственных слов показала, что предложенный вариант поиска родственных слов допускает малое количество ошибок: 8 на 1 000 слов. Это позволяет автоматически находить различные формы слов при обработке больших объемов текста.

Автоматически составленный по разработанному алгоритму список незначимых слов был ограничен 2000 слов, что составляет почти 2% от количества слов в словаре. В созданный список незначимых попало 38 слов, которые могут нести самостоятельный смысл. Таким образом, погрешность процедуры выделения значимых слов не превысила 2% от количества слов, признанных незначимыми.

В результате обработки тестового набора текстов были получены 40903 пары слов, устойчиво встречающиеся в одинаковом контексте. Из них 2034 пары слов были признаны синонимичными в соответствии с разработанным алгоритмом выделения синонимов. Экспертная проверка процедуры автоматического поиска контекстно-зависимых синонимов подтвердила успешность для 79% и отвергла 21% результатов.

Для оценки полученного поискового программного продукта проведены эксперименты, в которых использован набор всех запросов, которые были адресованы поисковой системе библиотеки в период с июня 2004 по февраль 2006. В этот период системой было обработано 76615 запросов. Число запросов для полнотекстового поиска равно 40478. Среди них выделено 22369 различающихся запросов, из которых случайным образом было отобрано 500 запросов. Для оценки соответствия результатов поиска запросам введена функция качества поиска <2%.

г \ 2 /■ \ 2 ~

1Л

ву.=

1 + £

+ к

400%

(7)

где к — коэффициент, определяющий приоритет точности над полнотой поиска; Т*1- множество найденных документов; Е - множество искомых документов.

Средний показатель качества поиска созданным программным комплексом по 500 тестовым запросам среди документов тестового фонда составил 88%. Для сравнения рассмотрена поисковая методика, реализованная в локальной версии поисковой машины Яндекс (www.yandex.ru), используемой в некоторых библиотеках для поиска по фондам документов. Д ля нее средний показатель качества поиска, оцененный по такой же методике и при таких же условиях, составил 65%.

^30

о 20

|ю

1°

II 1

—1 р I - -1--

10

20

30

40 50 60 Качество поиска, %

70

80

90

100

- Тех САпа1уз13 ■ Яндекс

Рис. 11. Сравнение качества поиска исследуемыми поисковыми системами Сравнение распределения значений функции качества поиска показало, что качество поиска созданной поисковой системой выше (рис. 11) благодаря учету контекстных связей слов, а также использованию словаря контекстно-зависимых синонимов. При этом на выполнение запросов требовалось от 2 до 15 секунд. Созданная система использовалась для анализа текстов византийских источ-

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

тексты на различных языках. Качество обработки текстов положительно оценено

сотрудниками Института Всеобщей Истории Российской Академии Наук.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

РАБОТЫ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Григорьев A.C. Организация хранения, обработки и доступа к полнотекстовым документам в современных АБИС // Новые информационные технологии: Матер, шестого всерос. научн.-практ. сем. - М., 2003. - С. 128-138.

2. Григорьев A.C. Принципы создания современной библиотечной поисковой системы // Информатика и системы управления в XXI веке: Труды молодых ученых, аспирантов и студентов. Сб. тр. - 2003. - №1. - С. 330-333.

3. Григорьев A.C. Машинное понимание естественного языка при составлении запросов к поисковой системе библиотеки // Новые информационные технологии: Матер, седьмого всерос. научн.-практ. сем. - М., 2004. - С. 70-76.

4. Григорьев A.C. Новая система обработки естественно-языковых текстов в исследовании понятий и терминов византийских источников // Межкультурное взаимодействие и его интерпретации: Материалы всероссийской научной конференции. - М., 2004. - С. 197-200.

5. Григорьев A.C. Исследование проблемы проектирования систем обработки естественно-языковых текстов и организации поиска по ним // Информатика и системы управления в XXI веке: Труды молодых ученых, аспирантов и студентов. Сб. тр. - 2004. - №2. - С. 184-188.

6. Григорьев A.C. Автоматическое получение ключевых словосочетаний текста электронного документа на произвольном языке // Новые информационные технологии: Матер, восьмого всерос. научн.-практ. сем,- М., 2005.-С.110-118.

Подписано к печати 26.04.2006 г. Заказ № 200. Объем 1.0 п.л. Тир. 100 экз. Типография МГТУ им. Н.Э. Баумана.

Введение.

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

1.1. Задача поиска по текстам документов.

1.2. Классификация методов полнотекстового поиска.

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

Использование контекстной информации.

2. Метод поиска.

2.1. Описание метода обработки статистической сочетаемости слов.

2.2. Статистическое выявление устойчивых сочетаний слов.

2.3. Объединение схожих по написанию форм слов.

2.4. Обработка данных о статистической сочетаемости слов.

2.5. Группирование текстов по спискам устойчивых сочетаний слов

2.6. Выполнение естественно-языкового поискового запроса.

Краткие выводы.

3. Алгоритмы обработки текста документов и запросов, реализующие метод поиска.

3.1. Подготовка документов к обработке и их хранение.

3.2. Заполнение словаря.

3.3. Статистическое выявление устойчивых сочетаний слов.

3.4. Обработка данных о статистической сочетаемости слов.

3.5. Группирование текстов по спискам связности слов.

3.6. Определение соответствия текста поисковому запросу.

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

4.1. Описание программной реализации.

4.2. Описание тестового набора текстов.

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

4.4. Экспериментальные оценки требуемых ресурсов при реализации разработанного метода.

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

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

Краткие выводы.

Социально-экономические преобразования в нашей стране и во всем мире во многом связаны с процессами информатизации общества [1]. Формируемое при этом информационное общество рассматривает информацию и знания как главные продукты производства и основные ценности. В процессах хранения и предоставления информации фундаментальную роль играют библиотеки [107]. В связи с ростом объемов обрабатываемой библиотеками информации возникают проблемы их радикальной перестройки для использования возможностей, предоставляемых современной вычислительной техникой. Удобство пользования библиотекой определяется ее поисковыми возможностями. Поэтому актуальность изучения существующих методов поиска, их совершенствования и создания нового поискового механизма определяет цель данной работы.

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

Для устранения данной проблемы документ, помещенный в фонды системы, снабжается текстовым описанием - рефератом [44] или списком ключевых слов. Текст реферата, конечно, полнее заглавия отражает содержание документа, но для использования этого текста при поиске требуются специальные средства для выделения той части слов и словосочетаний, которая отражает тематику документа. Традиционно задачу получения набора слов, характеризующих документ, «вручную» выполняют редакторы в издательствах или сотрудники библиотеки. Это вносит элемент субъективности в данную процедуру. Списки таких слов, полученные для однотипных документов в разных учреждениях, могут сильно различаться. Чтобы избежать этой проблемы требуются автоматические поисковые средства, самостоятельно анализирующие текст реферата.

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

1 2 3 тематических рубрикаторов ББК , ГАСНТИ\ УДК" [43]), позволяющих распределять документы по информационным группам. Так при помощи широко распространенного классификатора УДК [42] документы классифицируют путем индексирования по заданным рубрикам. Однако, использование дерева рубрик УДК для поиска и размещения информации в нужный раздел «вручную» малоэффективно в связи со сложностью визуального восприятия сильно разветвленного дерева описаний индексов УДК [43]. Автоматизированный поиск в пространстве классифицированных документов сводится к сопоставлению текста запроса с описанием рубрик классификатора и последующим представлением пользователю всех документов выбранной рубрики [73], что мало отличается от поиска по названию издания или по тексту реферата.

Концептуальная схема [71], описывающая механизм доступа пользователей библиотеки к документам через их описания или с использованием классификаторов или других поисковых интерфейсов, изображена на рис. В.1.

1 Библиографический Библиотечный Классификатор Государственная Автоматизированная Система Научно-Технической Информации 3 Универсальный Десятичный Классификатор

--Хранилище документов

Фон д документов

Документы

Оператор

Текстовые образы документов

Запрос^

-Поисковые средства

Документы

11оисковое описание документов

Поисковый интерфейс N

Читатели

Запрос

Поисковый сервер

Рис. В.1. Схема доступа пользователей библиотеки к её фондам

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

Темпы роста объема информационных хранилищ документов постоянно увеличиваются. Поэтому классическое решение задачи поиска, заключающееся в отыскании документов, содержащих слова запроса, уже не может удовлетворить пользователя. Количество найденных документов часто превышает объем, который пользователь способен проанализировать. Например, поиск по запросу «цены на персональные компьютеры» в пространстве описаний документов поисковой системы Япс1ех [25] дает более 60 миллионов наименований. Очевидно, лишь малая часть из них представляет интерес для автора запроса. Для повышения степени релевантности найденных документов поисковому запросу могут быть использованы формализованные поисковые интерфейсы и сложные классификаторы [42]. За счет этого обеспечивается высокое быстродействие и более точное соответствие результатов запросу. Несмотря на это, большинство пользователей не использует при поиске формализованный интерфейс. Использование формализованного интерфейса требует специального обучения пользователя и наличия у него навыков формальных преобразований запроса с естественного языка на язык, понятный поисковой системе. Поэтому более чем в 90% случаев пользователи предпочитают формулировать запрос в виде набора терминов или некоторой фразы [2].

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

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

Поиск документов с использованием ЕЯ запросов сводится к задаче обработки текстов. Над решением поставленной задачи работали С. Брин, JI. Пейдж, И. Сегалович, разработавшие методы полнотекстового поиска по инвертированному списку (булев поиск), реализованный в поисковых системах Интернет Google [25], Япс1ех [5] и др. При создании Реферативного Журнала ВИНИТИ [44] и в работах Г.П. Луна выполняется более глубокий анализ текста с целью выделения наборов ключевых слов из документов.

Значительный вклад в разработку, исследование и применение методов определения связей слов в предложениях внесли авторы формально-грамматических методов. В.А. Крищенко разработал метод, использующий структурную схему предложения, и реализовал его в «Информационной Метапоисковой Системе» [19]. В разработанном А.В. Бриком вероятностно-грамматическом методе [16], реализованном в программных продуктах «ODB-Text» и «Минерва», формально-грамматическая модель успешно дополнена использованием функции вероятностной оценки связности слов. Метод различительных сил, основанный на статистическом подходе и реализованный В.И. Шабановым в программном комплексе «Классификатор» [54], использует ассоциативные связи между терминами для снижения привязки к конкретному языку.

При обработке ЕЯ текстов используются также алгоритмы искусственного интеллекта. Имитационный подход реализован в диалоговых системах Ф.С. Файном [3]. Адаптивное распознавание образов используется в поисковой системе Retrieval Ware компании Convera [45]. Программный комплекс 4Thought компании Cognos [8] использует нейронные сети.

Особое место среди методов обработки текстов занимает лингвистический подход. В связи со сложностью применяемого в нем описания языка разработанные модели, как правило, не доводятся до практической реализации, как, например, уникальная модель «Смысл-Текст» И.А. Мельчука [104].

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

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

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

Объект исследования в данной работе - произвольные тексты на естественных языках и их сочетаниях.

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

Для достижения поставленной цели в диссертации решены следующие задачи:

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

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

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

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

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

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

Диссертация состоит из введения, четырех глав, выводов, заключения, списка литературы и приложения. Диссертация изложена на 158 страницах текста, содержит 39 рисунков и 30 таблиц. Библиография содержит 113 наименований. В первой главе выполнена математическая постановка задачи, описаны ключевые понятия и даны определения используемой в работе терминологии. Дан обзор стратегий текстового поиска, детально рассмотрены методы обработки текстов. По результатам проведенного анализа построена классификация методов текстового поиска. Сделаны выводы о достоинствах и недостатках каждого из методов и сформулированы цели и направления данного исследования. Во второй главе описан подход к полнотекстовому поиску с использованием неформализованных запросов. Описан метод статистической обработки текстов для оценки морфологической, синтаксической и семантической сочетаемости слов. В третьей главе разработана алгоритмическая структура, соответствующая описанному методу, а также решены задачи ограничения объемов создаваемой служебной информации. Выбраны параметры функций оценки подобия объектов при выделении значимых слов, формировании групп текстов и сравнении структур предложений запроса и текста. В четвертой главе экспериментальные данные использованы для обоснования принятых зависимостей и ограничений. Разработанный поисковый метод оценен с точки зрения точности и полноты поиска. Произведена его сравнительная оценка с методикой, использованной в поисковой машине Япёех.

Основные результаты разработки и реализации метода статистической обработки контекста могут быть формулированы в следующем виде:

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

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

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

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

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

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

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

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

1. Соловьева Д.Я., Коссаковская Н.К., Гордон С.А. Перспективы развития научно-технических библиотек // Юбилейный сб. научн. тр. ГПНТБ России 1970-1995 гг. М., 1999.-С. 94-111.

2. Jansen В., Spink A., Bateman J. Real life information retrieval: a study of user queries on the web // ACM SIGIR Forum. 1998. - V. 32, № 1. -P. 22-28.

3. Файн B.C. Распознавание образов и машинное понимание естественного языка. М.: Наука, 1987. - 176 с.

4. Бронников В. Виртуальная жизнь клеточных автоматов // Компьютер в школе. 1998. - №2. - С. 10-19.

5. Холмогоров В. Поиск в Интернете и сервисы Яндекс. СПб.: Питер, 2006. - 122 с.

6. Тихомиров Ю.В. Microsoft SQL Server 7.0. СПб.: БХВ-Санкт-Петербург, 1999. - 720 е.: ил.

7. Уоссермен Ф. Нейрокомпьютерная техника: Теория и практика / Пер. с англ. Ю.А. Зуева, В.А. Точенова. М.: Мир, 1992. - 175 с.

8. Шапот М. Интеллектуальный анализ данных в системах поддержки принятия решений // Открытые системы. 1998. - №1. - С. 30-35.

9. Hsu С., Dung М. Generating finite-state transducers for semi-structured data extraction from the web // Information Systems. 1998. - V. 23, №. 8. -P. 521 - 538.

10. Вирин В. Кто ищет, тот всегда найдет! // ComputerWorld Россия. 2003. -№8. - С. 6-8.

11. Bittco Solutions NetReality: neural net virtual reality document management thing//Linux Weekly News. 1999. - № 0225. - P. 38-41.

12. Бобровский С. Досье искусственного интеллекта // PC Week. 1999. -№45 (219).-С. 18-20.

13. Нейман Дэн:., Моргенштерн О. Теория игр и экономическое поведение. М.: Наука, 1970. - 230 с.

14. Урманн Дж. Oracle 8. Программирование на языке PL/SQL. М.: Лори, 1999.-610 с.

15. Neuhaus P., Hahn U. Restricted Parallelism in Object-Oriented Lexical Parsing // Proc. Of the 16th Int. Conf. On Computational Linguistics. -Copenhagen, 1996. P. 36-49.

16. Брик А.В. Исследование и разработка вероятностных методов синтаксического анализа текста на естественном языке: дис. . канд. техн. наук: 05.13.11 / МГТУ им. Н.Э. Баумана. М., 2002. - 160 с.

17. Collins М. Three Generative, Lexicalised Models for Statistical Parsing /Dept. Of Computer and Information Science, University of Pennsylvania. -Philadelphia, 1997.- 216 p.

18. Бахвалов Т. Язычество без тайн // Компьютерра. 2005. - №39. -С. 23-30.

19. Крищенко В.А. Программное обеспечение для метапоиска информации в гипертекстовой среде: дис. канд. техн. наук: 05.13.11. М., 2002. -143 с.

20. Свинарев С. Нейроагенты Neugents приступают к управлению информационными системами // Computer Weekly. 1999. - №3. -С. 16-17.

21. Ахо У., Ульман Дж. Синтаксический анализ. М.: Мир, 1978. -612с.-(Теория синтаксического анализа, перевода и компиляции; Т.1).

22. Компьютерный синтаксический анализ: описание моделей и направлений разработок / Г.Д. Карпова, Ю.К. Пирогова, Т.Ю. Кобзарева и др. М., 1991. - 130 с. - (Итоги науки и техники / ВИНИТИ. Сер. Вычислительные науки; Т.6).

23. Architectures and mechanisms for language processing / Edited by Matthew W. Crocker, Martin Pickering, Charles Clifton, Jr. Cambridge; New York: Cambridge University Press, 2000. - 365 p.

24. Губарев В.В. Алгоритмы статистических измерений. М.: Энергоатомиздат, 1985. - 272с.

25. Brin S., Page L. The Anatomy of a Large-Scale Hypertextual Web Search Engine. Stanford: Stanford University, 1999. - 20 p.

26. Волошина Т. Нормативное регулирование контрольно-надзорных отношений //Грани Гаранта. 2004. -№3 (11). - С. 19-23.

27. Романенко В.Н., Никитина Г.В. Сетевой информационный поиск: Практическое пособие. СПб.: Профессия, 2005. - 285 с.

28. Григорьев А.С. Организация хранения, обработки и доступа к полнотекстовым документам в современных АБИС // Новые информационные технологии: Матер, шестого Всерос. научн.-практ. сем.-М., 2003.-С. 128-138.

29. London Т. Guidelines and Good Practice for Developing SQL. Illinois: Northern Illinois University, 1992. - 65 p.

30. Feuerstein S. Oracle PL/SQL Best Practices: Optimizing Oracle Code. -Cambridge: O'Reilly, 2001. 204 p.

31. Костюк В.И., Ходаков B.E. Системы отображения информации и инженерная психология. Киев: Вища школа, 1977. - 192 с.

32. Корн Г., Корн Т. Справочник по математике (для научных работников и инженеров). М.: Наука, 1978. - 832 с.

33. Современный русский язык. Фонетика. Лексикон. Словообразование. Морфология. Синтаксис. СПб.: Лань, 2001. - 864 с.

34. Башмаков А.И., Башмаков И.А. Интеллектуальные информационные технологии: Учеб. пособие. М.: Изд-во МГТУ им. Н.Э. Баумана, 2005.304 с. - (Информатика в техническом университете).

35. Библиография: Общий курс / Под ред. М.А. Брискмана, А.Д. Эйхенгольца. М.: ВИНИТИ, 1969. - 560 с.

36. Хамилтон С. Научно-исследовательские проекты Microsoft // Computer World. 1998. - №31. - С. 40-42.

37. Хроленко А.Т. Лингвокультуроведение: Учебное пособие. Курск: Издательство Регионального Открытого Социального Института, 2001. -180 с.

38. Григорьев А.С. Исследование проблемы проектирования систем обработки естественно-языковых текстов и организации поиска по ним // Информатика и системы управления в XXI веке: Тр. молодых ученых, аспирантов и студентов: Сб. тр. 2004. - №2. - С. 184-188.

39. Черемных С.В., Семенов И.О., Ручкин B.C. Структурный анализ систем: IDEF-технологии. М.: Финансы и статистика, 2001. - 208 с.

40. Концепция семантического поля исторического источника / Ю.Я. Вин, А.Ю. Гриднева, Д.Е. Кондратьев и др. // Диалог со временем. Альманах интеллектуальной истории. 2004. - №12. - С. 84-99.

41. Григорьев А.С. Машинное понимание естественного языка при составлении запросов к поисковой системе библиотеки // Новые информационные технологии: Матер, седьмого Всерос. научн.-практ. сем. М., 2004. - С. 70-76.

42. Вспомогательные таблицы: Универсальная десятичная классификация /Ред. Ю.М. Арский. М.: ВИНИТИ, 2001. - 246 с. - (УДК. Универсальная десятичная классификация; Т. 1).

43. Зайцева Е.М. Отчет по первому этапу разработки Схемы классификации печатной продукции. М.: Российское книжное общество, 2004. -С. 3-7.

44. Черный А.И. Введение в теорию информационного поиска. М.: Наука, 1975.-238 с.

45. Рузайкин Г.И. Развитие поисковых систем в Интернете // Мир ПК. -2005.-№ 9 .-С. 100-102.

46. Bittco Releases NetReality at Comdex Fall '99; The Most Advanced Personal Internet Search Tool // Business Wire. 1999. - November 18. - P. 18-19.

47. Браславский П.И. Стиль как дополнительный параметр поиска информации в Internet // Русская компьютерная и квантитативная лингвистика. М., 2000. - С. 396.

48. Воронина И.Е. Проблемы формализации русского языка // Русская компьютерная и квантитативная лингвистика. М., 2000. - С. 398-399.

49. Шабанов В.И. Модели и методы автоматической классификации текстовых документов: дис. . канд. техн. наук: 05.13.1 1. М., 2003. -227 с.

50. Григорьев А.С. Автоматическое получение ключевых словосочетаний текста электронного документа на произвольном языке // Новые информационные технологии: Матер, восьмого Всерос. научн.-практ. сем.-М., 2005.-С. 110-118.

51. Волкова И.А., Головин И.Г. Синтаксический анализ фраз естественного языка на основе сетевой грамматики // Тр. международного сем. ДИАЛОГ'98. М., 1998. - С. 39-45.

52. Вудс В.А. Сетевые грамматики для анализа естественных языков // Кибернетический сборник. Новая серия. 1978. - Вып. 13. - С. 86-113.

53. Magerman D. Natural Language Parsing as Statistical Pattern Recognition. Doctoral thesis. Stanford: Stanford University, 1994. - 161 p.

54. Сегалович И.В. Как работают поисковые системы. М.: КОЛИНТ, 2005.-25 с.

55. Растригин Л.А. По воле случая. М.: Молодая гвардия, 1986. - 208 с.

56. Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning. Massachusetts: Addison-Wesley, 1989. - 412 p.

57. Зайцев А.В. Методика создания индексных файлов для осуществления полнотекстового поиска в сети Интернет. СПб: ГУАГ1 CODENET, 2001.-49 с.

58. Кондратьев Д.Е., Тихонова О.В. Алгоритм сравнения статей на основе семантической близости понятий // Новые информационные технологии: Матер, шестого Всерос. научн.-практ. сем. М., 2003. -С. 26-31.

59. Григорьев А.С. Новая система обработки естественно-языковых текстов в исследовании понятий и терминов византийских источников // Межкультурное взаимодействие и его интерпретации: Матер. Всерос. научн. конф. М., 2004. - С. 197-200.

60. Куралеиок И.Е., Некрестьянов И.С. Автоматическая классификация документов с использованием семантического анализа // Электронные библиотеки, перспективные методы и технологии: Тр. первой Всерос. научн.-метод. конф. СПб, 1999. - С. 86-96.

61. Manning C.D., Carpenter R. Probabilistic Parsing Using Left Corner Language Models // Information Processing & Management. 1997. - №1. -P. 12-24.

62. Raychauclhuri S., Schutze H., Altman R.B. Using text analysis to identify functionally coherent gene groups // Genome Research. Stanford; San Mateo, 2002.-P. 1582-1590.

63. Бойцов JI. Классификация и экспериментальное исследование современных алгоритмов нечеткого словарного поиска // Электронные библиотеки: перспективные методы и технологии, электронные коллекции: Шестая Всерос. научн. конф. М., 2004. - С. 148-156.

64. Damerau F.J. A technique for computer detection and correction of spelling errors//Communications of the ACM. 1964. - VoI.7(3). - P. 171-176.

65. Левенштейи В.И. Двоичные коды с исправлением выпадений, вставок и замещений символов // Докл. АН СССР.- 1965,- Т. 163, №4. С. 845-848.

66. Luhn H.P. A statistical approach to mechanized encoding and search of library information // IBM Journal of Research and Development. 1957. -№1. - P. 309-317.

67. Григорьев А. С. Принципы создания современной библиотечной поисковой системы // Информатика и системы управления в XXI веке: Тр. молодых ученых, аспирантов и студентов: Сб. тр. 2003 .- №1. -С. 330-333.

68. Абызгильдин А.Ю., Руднев Н.А. Проект информационной системы учебного предприятия // Новые образовательные технологии: Сб. тр. научн.-метод, сем. Уфа, 2001. - С. 28.

69. Седжвик Р. Фундаментальные алгоритмы на С. Анализ/Структуры данных/Сортировка/Поиск/Алгоритмы на графах: Пер. с англ. СПб: ООО «ДиаСофтЮП», 2003. - 1136 с.

70. Гренандер У. Лекции по теории образов: Регулярные структуры: Пер. с англ. М.: Мир, 1983. - 432 с.

71. Трофимов С.A. Rational XDE для Visual Studio .NET. М.: Бином-Пресс, 2003.-304 с.

72. Авторское право: Нормативные акты. Национальное законодательство и международные конвенции / Сост., авт. вступ. ст. И. Силонов; оформл. Г. Сыроватского. М.: Элит-Клуб; Юридическая книга, 1998. -429 с.

73. Фомин Я.А., Тарловский Г.Р. Статистическая теория распознавания образов. М.: Радио и связь, 1986. - 264 с.

74. Елохин В.Р., Елохин И.В. Имитационный метод статистической аппроксимации. Апатиты: Изд-во Кольского научного центра РАН, 2002. - 120 с.

75. Васильев В.И., Коноваленко В.В., Горелов Ю.И. Имитационное управление неопределенными объектами. Киев: Наукова думка, 1989. -216 с.

76. Колмогоров А.Н. Основные понятия теории вероятностей. М.: Наука, 1974.- 119 с.

77. Ибрагимов И.А., Хасьмииский Р.З. Асимптотическая теория оценивания. М.: Наука, 1970. - 384 с.

78. Клейнен Дж. Статистические методы в имитационном моделировании: Пер. с англ. / Под ред. Ю.П. Адлера, В.Н. Варыгина. М.: Статистика, 1978.- 335 с.

79. Бойцов Л. Поиск по сходству в документальных базах данных //Программист. 2001. -№ 1. - С. 32-35.

80. Риоло P.JI. Естественный отбор в мире битов // В мире науки (Scientific American). 1992. - Сентябрь-Октябрь. - С. 160-165.

81. Manber U., Myers G. Suffix Arrays: A New Method for On-line String Searches // 1st ACM-SIAM Symposium on Discrete Algorithms. -Philadelphia, 1990.-P. 12-20.

82. Manber U. Finding similar files in a large file system // USENIX Conference. Boston, 1994. - P. 343-349.

83. Joyce Т., Needham R.M. The Thesaurus Approach to Information Retrieval // American Documentation. 1958. - №12. - P. 611-625.

84. Automatic query expansion using SMART TREC-3 / G. Salton, C. Buckley, J. Allan etc. // An Overview of the Third Text Retrieval Conference (TREC 3). - 1995. - №500-225. - P. 69-80.1. Г