Содержание к диссертации
Введение
1. Аналитический обзор методов и стратегий поиска текстовой информации. Системы обработки текста документов 13
1.1. Задача поиска по текстам документов 13
1.2. Классификация методов полнотекстового поиска 16
Методы классического поиска (без использования контекстной информации) 17
Использование контекстной информации 24
2. Метод поиска 45
2.1. Описание метода обработки статистической сочетаемости слов 45
2.2. Статистическое выявление устойчивых сочетаний слов 49
2.3. Объединение схожих по написанию форм слов 58
2.4. Обработка данных о статистической сочетаемости слов 61
2.5. Группирование текстов по спискам устойчивых сочетаний слов .65
2.6. Выполнение естественно-языкового поискового запроса 68
Краткие выводы 70
3. Алгоритмы обработки текста документов и запросов, реализующие метод поиска 71
3.1. Подготовка документов к обработке и их хранение 71
3.2. Заполнение словаря 73
3.3. Статистическое выявление устойчивых сочетаний слов 78
3.4. Обработка данных о статистической сочетаемости слов 83
3.5. Группирование текстов по спискам связности слов 86
3.6. Определение соответствия текста поисковому запросу 89
4. Программная реализация поискового метода и ее испытания 91
4.1. Описание программной реализации 91
4.2. Описание тестового набора текстов 98
4.3. Определение эмпирических пороговых значений и коэффициентов 99
4.4. Экспериментальные оценки требуемых ресурсов при реализации разработанного метода 109
4.5. Оценка качественных и количественных показателей разработанного метода поиска 118
4.6. Сравнительная оценка ресурсоемкости разработанной поисковой системы 134
Краткие выводы 145
Основные выводы 147
Список литературы
- Методы классического поиска (без использования контекстной информации)
- Статистическое выявление устойчивых сочетаний слов
- Статистическое выявление устойчивых сочетаний слов
- Определение эмпирических пороговых значений и коэффициентов
Введение к работе
Социально-экономические преобразования в нашей стране и во всем мире во многом связаны с процессами информатизации общества [1]. Формируемое при этом информационное общество рассматривает информацию и знания как главные продукты производства и основные ценности. В процессах хранения и предоставления информации фундаментальную роль играют библиотеки [107]. В связи с ростом объемов обрабатываемой библиотеками информации возникают проблемы их радикальной перестройки для использования возможностей, предоставляемых современной вычислительной техникой. Удобство пользования библиотекой определяется ее поисковыми возможностями. Поэтому актуальность изучения существующих методов поиска, их совершенствования и создания нового поискового механизма определяет цель данной работы.
В настоящее время поиск и предоставление документов читателям, чаще всего, ограничены заложенными в систему библиографическими описаниями документов. Использование полей библиографических описаний (заглавие, авторы и др.), хранящихся в библиотечном каталоге, не всегда позволяет читателю найти интересующий его источник. Название издания, как правило, не может достаточно полно и достоверно отразить все содержание документа. Слова, составляющие заданный пользователем поисковый запрос, могут отсутствовать в заглавии документа при том, что сам документ частично или полностью удовлетворяет запросу.
Для устранения данной проблемы документ, помещенный в фонды системы, снабжается текстовым описанием - рефератом [44] или списком ключевых слов. Текст реферата, конечно, полнее заглавия отражает содержание документа, но для использования этого текста при поиске требуются специальные средства для выделения той части слов и словосочетаний, которая отражает тематику документа. Традиционно задачу
получения набора слов, характеризующих документ, «вручную» выполняют редакторы в издательствах или сотрудники библиотеки. Это вносит элемент субъективности в данную процедуру. Списки таких слов, полученные для однотипных документов в разных учреждениях, могут сильно различаться. Чтобы избежать этой проблемы требуются автоматические поисковые средства, самостоятельно анализирующие текст реферата.
Второй традиционный путь поиска документов в библиотеках основан на использовании различных классификаторов (иерархических
тематических рубрикаторов ББК', ГАСНТИ% УДК'[43]), позволяющих распределять документы по информационным группам. Так при помощи широко распространенного классификатора УДК [42] документы классифицируют путем индексирования по заданным рубрикам. Однако, использование дерева рубрик УДК для поиска и размещения информации в нужный раздел «вручную» малоэффективно в связи со сложностью визуального восприятия сильно разветвленного дерева описаний индексов УДК [43]. Автоматизированный поиск в пространстве классифицированных документов сводится к сопоставлению текста запроса с описанием рубрик классификатора и последующим представлением пользователю всех документов выбранной рубрики [73], что мало отличается от поиска по названию издания или по тексту реферата.
Концептуальная схема [71], описывающая механизм доступа пользователей библиотеки к документам через их описания или с использованием классификаторов или других поисковых интерфейсов, изображена на рис. В.1.
Библиографический Библиотечный Классификатор Государственная Автоматизированная Система Научно-Технической Информации 3 Универсальный Десятичный Классификатор
^—Хранилище документов-
Документы
Фонд
документов
Поисковые средства-
Оператор
Текстовые
образы документов
Поисковое
описание
документов
Поисковый интерфейс
Чит а і сми
Запрос^ -_
.:_-/;
Запрос
Поисковый сервер
Рис. В.1. Схема доступа пользователей библиотеки к её фондам
По мере увеличения информационных мощностей вычислительных систем стало возможным помещать в хранилище информационной системы библиотеки вместе с библиографическим описанием и сам документ. Документы, хранящиеся в электронных хранилищах вместе со своими описаниями, называются Электронными Документами (ЭД). ЭД - это неизменяемый во времени объект, сохраненный на машиночитаемом носителе и снабженный описанием [72]. Таким документом может быть как текстовый файл (набор текстовых файлов), так и любой другой вид информации (графическая, аудио), хранимой в виде файлов. Библиотека, организующая хранение ЭД вместе с их описаниями получила название Электронной Библиотеки (ЭБ). В такой библиотеке при поиске используется не только библиографическое описание документа, но и его текстовый образ. Для текстового документа при этом используется его текст. Для построения текстового образа произвольного документа, хранящего графическую или аудио информацию, создается текстовое описание
содержимого этого документа. При этом в ЭБ поиск выполняется по всему тексту текстового образа документа и поэтому называется полнотекстовым поиском.
Темпы роста объема информационных хранилищ документов постоянно увеличиваются. Поэтому классическое решение задачи поиска, заключающееся в отыскании документов, содержащих слова запроса, уже не может удовлетворить пользователя. Количество найденных документов часто превышает объем, который пользователь способен проанализировать. Например, поиск по запросу «цены на персональные компьютеры» в пространстве описаний документов поисковой системы Япсіех [25] дает более 60 миллионов наименований. Очевидно, лишь малая часть из них представляет интерес для автора запроса. Для повышения степени релевантности найденных документов поисковому запросу могут быть использованы формализованные поисковые интерфейсы и сложные классификаторы [42]. За счет этого обеспечивается высокое быстродействие и более точное соответствие результатов запросу. Несмотря на это, большинство пользователей не использует при поиске формализованный интерфейс. Использование формализованного интерфейса требует специального обучения пользователя и наличия у него навыков формальных преобразований запроса с естественного языка на язык, понятный поисковой системе. Поэтому более чем в 90% случаев пользователи предпочитают формулировать запрос в виде набора терминов или некоторой фразы [2].
По названным причинам в настоящее время существует потребность в создании поисковой системы ЭБ, позволяющей пользователю на естественном языке формулировать поисковые запросы, по которым система предоставит документы с высокой степенью релевантности. Для преобразования запроса с естественного языка, на котором пользователь привык мыслить, на формализованный язык интерфейса в настоящей
диссертации предложен метод статистической оценки контекста слова и реализующая его поисковая система.
Определение. Естественный Язык (ЕЯ) - множество терминов и оборотов разговорного, профессионального или литературного языка, используемых пользователем при общении с другими людьми в конкретной среде или области деятельности. В общем случае, ЕЯ могут произвольно пересекаться.
Поиск документов с использованием ЕЯ запросов сводится к задаче обработки текстов. Над решением поставленной задачи работали С. Брин, Л. Пейдж, И. Сегалович, разработавшие методы полнотекстового поиска по инвертированному списку (булев поиск), реализованный в поисковых системах Интернет Google [25], Япсіех [5] и др. При создании Реферативного Журнала ВИНИТИ [44] и в работах Г.П. Луна выполняется более глубокий анализ текста с целью выделения наборов ключевых слов из документов.
Значительный вклад в разработку, исследование и применение методов определения связей слов в предложениях внесли авторы формально-грамматических методов. В.А. Крищенко разработал метод, использующий структурную схему предложения, и реализовал его в «Информационной Метапоисковой Системе» [19]. В разработанном А.В. Бриком вероятностно-грамматическом методе [16], реализованном в программных продуктах «ODB-Text» и «Минерва», формально-грамматическая модель успешно дополнена использованием функции вероятностной оценки связности слов. Метод различительных сил, основанный на статистическом подходе и реализованный В.И. Шабановым в программном комплексе «Классификатор» [54], использует ассоциативные связи между терминами для снижения привязки к конкретному языку.
При обработке ЕЯ текстов используются также алгоритмы искусственного интеллекта. Имитационный подход реализован в диалоговых системах Ф.С. Файном [3]. Адаптивное распознавание образов
используется в поисковой системе Retrieval Ware компании Convera [45]. Программный комплекс 4Thought компании Cognos [8] использует нейронные сети.
Особое место среди методов обработки текстов занимает лингвистический подход. В связи со сложностью применяемого в нем описания языка разработанные модели, как правило, не доводятся до практической реализации, как, например, уникальная модель «Смысл-Текст» И.А. Мельчука [104].
Общими недостатками приведенных методов являются либо игнорирование связей между словами, либо необходимость проведения ручного обучения правилам обработки текстов. В данной работе поставлена задача создания метода обработки ЕЯ текстов, который позволяет автоматически строить структуры, описывающие предложения запроса и документов для их сопоставления при поиске. Обучение обработчика текста особенностям языка, основанное на получении статистических закономерностей при анализе частот появления слов и их статистической сочетаемости между собой в текстах, минимизирует участие человека в обучении. При этом часто встречающиеся объекты образуют устойчивые группы, а редко встречающиеся - исключаются из рассмотрения, так как не служат источником информации о сочетаниях слов.
Автоматическое обучение языку разработанным в диссертации методом производится без подготовки формальных правил, описывающих язык. Для выявления закономерностей статистической сочетаемости слов анализируются все предложения текстов, хранящихся в системе. Это позволило решить задачу выделения частей предложения и выявления их зависимостей между собой, основываясь на статистических данных, полученных из анализа частот повторения сочетаний слов.
Наряду с проблемами обучения систем и выполнения поиска в работе решаются проблемы хранения поискового индекса документов - специально
организованной служебной информации, ускоряющей поиск и расширяющей поисковые возможности используемого метода. Информация, создаваемая при подготовке неструктурированного текстового источника для осуществления поиска, может иметь объем, превышающий объем самого документа. В данной работе решается, какая информация должна быть сохранена для описания документа, а какая исключается из рассмотрения для снижения объема обрабатываемых при поиске данных.
Объект исследования в данной работе - произвольные тексты на естественных языках и их сочетаниях.
Целью диссертационной работы является создание метода, направленного на повышение качества полнотекстового поиска путем выделения повторяющихся сочетаний слов как в анализируемых текстах, так и в поисковых запросах, сформулированных на естественном языке.
Для достижения поставленной цели в диссертации решены следующие задачи:
систематизированы известные методы и стратегии поиска, выделены основные этапы обработки текстов на естественном языке;
разработаны и оптимизированы структуры для хранения служебной информации, создаваемой в процессе статистического анализа текстов;
разработан метод поиска по произвольным документам на естественном языке, использующий устойчивые сочетания слов, автоматически выделяемые как в анализируемых текстах, так и в запросах;
использовано группирование документов по спискам устойчивых сочетаний слов с целью ускорения поиска;
разработан метод автоматического обучения анализатора текста языку по динамически пополняемому библиотечному информационному фонду документов за счет выявления закономерностей при статистическом анализе ассоциативных связей между словами текстов документов;
создан программный комплекс, реализующий разработанный метод поиска. Диссертация состоит из введения, четырех глав, выводов, заключения, списка литературы и приложения. Диссертация изложена на 158 страницах текста, содержит 39 рисунков и 30 таблиц. Библиография содержит 113 наименований. В первой главе выполнена математическая постановка задачи, описаны ключевые понятия и даны определения используемой в работе терминологии. Дан обзор стратегий текстового поиска, детально рассмотрены методы обработки текстов. По результатам проведенного анализа построена классификация методов текстового поиска. Сделаны выводы о достоинствах и недостатках каждого из методов и сформулированы цели и направления данного исследования. Во второй главе описан подход к полнотекстовому поиску с использованием неформализованных запросов. Описан метод статистической обработки текстов для оценки морфологической, синтаксической и семантической сочетаемости слов. В третьей главе разработана алгоритмическая структура, соответствующая описанному методу, а также решены задачи ограничения объемов создаваемой служебной информации. Выбраны параметры функций оценки подобия объектов при выделении значимых слов, формировании групп текстов и сравнении структур предложений запроса и текста. В четвертой главе экспериментальные данные использованы для обоснования принятых зависимостей и ограничений. Разработанный поисковый метод оценен с точки зрения точности и полноты поиска. Произведена его сравнительная оценка с методикой, использованной в поисковой машине Япсіех.
В работе даны теоретические оценки временных затрат на выполнение поиска разработанным методом, подтвержденные экспериментально. Проведено сравнение результатов поиска разработанным программным комплексом с результатами, полученными экспертами. При этом оценены
точность и полнота поиска путем вычисления степени релевантности по выведенной формуле. Полученные результаты позволяют говорить о повышении качества поиска предлагаемым методом обработки статистической сочетаемости слов по сравнению с классическим методом поиска. Практическим результатом работы является реализация метода в виде конечного программного продукта, позволяющего выполнять полнотекстовый поиск по запросам на ЕЯ. Программное обеспечение внедрено и используется в рамках единой Автоматизированной Библиотечной Информационной Системы МГТУ им. Н.Э. Баумана, что подтверждается соответствующим актом. В подтверждение положения о независимости разработанного подхода от используемого в текстах языка созданные методы, алгоритмы и модели успешно опробованы при создании системы обработки текстов византийских документов на древнегреческом языке для описания использованных в них терминов.
Результаты проведенного исследования опубликованы в 6 печатных работах.
Методы классического поиска (без использования контекстной информации)
Различные стратегии поиска отличаются используемым теоретическим аппаратом, называемым моделью поиска [54].
Определение. Модель поиска — абстракция реальности, на основании которой получается формула, позволяющая анализатору текстов принять решение: какой документ считать соответствующим запросу и в какой степени.
Все многообразие моделей поиска [22, 23, 89] может быть разделено на булевские [5], алгебраические [98], статистические [49], формально грамматические [16, 19] и лингвистические [18]. Ключевым модулем каждой поисковой системы, обрабатывающей текст, является лингвистический процессор, выполняющий последовательно лексический (выделение слов), морфологический (определение форм словоупотребления), синтаксический (определение роли слов в предложении для построения подчинительных связей) и семантический (установление ассоциативных связей слов на уровне всего языка) анализ текста документов и пользовательского запроса. В обзоре проанализированы 4 уровня обработки текстов (в порядке усложнения) [103]: Лексический анализ - выделение слов, используемых при сравнении предложений текста с запросами, - специальная обработка имен и дат, - учет регистра представления в тексте слова в целом и первой буквы в частности; Морфологический анализ - объединение словоформ одного слова, - использование морфологических признаков при определении отношений между словами; Синтаксический анализ - деление сложных предложений на простые, - определение подчинительных связей между словами в предложении; Семантический анализ - определение синонимии4 и антонимии между различными словами, - определение омонимии и других смысловых отношений между словами.
Успешность применения любого метода обработки текста во многом определяется качеством заложенных в систему правил и словарей, используемых для проведения обучения анализатора языку. Обучение системы языку может проводиться вручную (правила разбора предложений формируются человеком), автоматизированно (анализатор составляет правила под управлением человека), автоматически (человек может внести коррективы в составленные правила по окончании обучения).
Методы классического поиска (без использования контекстной информации) Как правило, при реализации полнотекстового поиска используют только этот вид семантического анализа
Простейшие поисковые системы используют булевские методы поиска. Поисковые методы этого семейства рассматривают предложения запроса q и текста t как множества слов Wq и Wt, соответственно [44]. При поиске не используется информация о взаимосвязях слов: смысловые отношения и синтаксические связи, то есть Cq=0 и Ct=0. Документ признается соответствующим запросу, если слово запроса найдено среди слов документа. Такой подход дает хорошие результаты при поиске одного или нескольких терминов, с высокой вероятностью определяющих тематику искомого документа. Это упрощение приводит к снижению качества поиска, если запрос содержит связные словосочетания, так как связи слов в этом методе поиска не учитываются, и в результаты поиска попадают документы, не соответствующие запросу пользователя.
В функции релевантности Re(q, t), используемой в булевских методах, учитываются только слова запроса и слова текста документа, поэтому: RD(q,t) RB{Wq,W). (1.6) Значение функции релевантности определяется как мощность пересечения множеств слов запроса q и документа /: RB Wq,Wt) = \WqrsWt\. (1.7)
Практически данный метод реализован, например, в алгоритмах прямого поиска [56]. При выполнении прямого поиска документ представляется как последовательность слов. Эта последовательность просматривается для сравнения с текстом запроса. В частности, при поиске по документу в текстовых редакторах используется поиск по шаблону, требующий полного соответствия строки поискового запроса фрагменту текста документа. Этот же метод использовался в системе БАРС - первой версии электронного каталога библиотеки МГТУ им. Н.Э. Баумана [28].
Статистическое выявление устойчивых сочетаний слов
При выполнении статистического анализа текстов, добавляемых в хранилище документов, все слова обработанных текстов заносятся в словарь с сохранением количества их повторений. При этом новым словом считается любая уникальная комбинация алфавитно-цифровых символов, исключая символы разделителей слов и знаки препинания. После этого слова ранжируются по степени значимости, используя частоту их появления в текстах. Слова с высокой значимостью используются для автоматического определения статистической связности слов - их статистической сочетаемости. Если сочетание слов встречено в нескольких предложениях,
Диаграмма Потоков Данных - спецификационная диаграмма стандарта описания сложных систем (DFD - Data Flow Diagram) оно признается устойчивым и заносится в таблицу устойчивых сочетаний слов.
Последовательность действий при заполнении словаря и составлении сочетаний изображена на рис. 2.3.
Заполнение словаря
Вместе с каждым словом, встреченным при обработке текстов, в словарь заносится информация о его словоформе, количестве повторений в текстах. В отдельной таблице для каждого слова сохраняется информация о том, в каких предложениях и в какой позиции оно встретилось.
Множество всех документов в фонде обозначим как Т. Множество слов в словаре обозначим как W. Отдельное слово в словаре обозначим как \\\ учитывая, что это понятие включает в себя сложную структуру. То есть слово рассматривается как вектор, содержащий комплекс характеристик.
Количество повторений слова в текстах используется для вычисления частоты F=F(w, t) появления слова w в каждом документе t фонда Т. Частота F определяется как отношение количества повторений слова в документе к общему количеству слов в этом документе и подсчитывается для каждого слова w в каждом документе teT.
Определение значимости слова
Модифицируем классическое понятие значимости слова, введенное Дж. Солтоном [85]. Будем определять его не для отдельного документа, а для информационного фонда в целом. Классическое значение подсчитывалось по формуле (1.9). В настоящей работе выражение для значимости S(w) модифицировано так, что частота повторения F(w, t) слова w в конкретном документе t заменяется значением для того документа, для которого эта частота была наибольшей. N max log Т S(w) = а , NT EtaJ, ig N. (2.1) і J где номер текущего слова в словаре; max наибольшее значение частоты повторения F(w, t) слова w среди всех документов фонда Т: Fm.M = max(/7(w,0); (Fma\)i - наибольшее значение частоты повторения F(wh t) слова Wj среди всех документов фонда Г: {Fmax);. = max(F(w;.,0); Л - число документов, в которых встретилось слово W. N=N(w)\ Nj - ЧИСЛО ДОКумеНТОВ, В КОТОРЫХ ВСТреТИЛОСЬ СЛОВО Wj\ Nt=NM; NT - число документов в фонде: 7; Nw - число слов в словаре: \Щ. В знаменателе выражения (2.1) для всех слов вычисляется сумма: AV ( JV.. А2 , которая не зависит от конкретного слова, так как вычисляется для всех слов словаря. Она используется для получения нормированного значения функции значимости и влияет только на масштаб получаемой функции. После умножения выражения (2.1) на такую же константу модифицированная функция значимости слова w примет вид:
Для иллюстрации особенностей рассматриваемой характеристики (2.2) приведем пример, использующий описанный в гл. 4 набор документов. Значения функции значимости, соответствующие словам словаря приведены в табл. 1.
Статистическое выявление устойчивых сочетаний слов
Имена числительные, обозначаемые цифрами, как правило, не несут конкретной смысловой нагрузки, а лишь определяют степень какого-либо признака описываемого объекта. Можно заменить все числа одним единственным эквивалентом в словаре. Но делать это следует только после статистического анализа всех чисел. Так, число «1812» имеет самостоятельный смысл, как историческая дата, и должно рассматриваться как отдельное слово.
В данной работе имена числительные специально обрабатывались только при объединении частей дат, разделенных точками.
После заполнения словаря и группирования родственных слов вычисляется значимость S (w) (см. 2.2) каждого главного слова, представляющего группу родственных слов. Значения функции значимости S (w) находятся в области неотрицательных действительных чисел. Большие значения функции значимости соответствуют значимым словам, а меньшие - незначимым. Для разделения слов на значимые и незначимые введено пороговое значение функции значимости Snopoc. Все слова со значением функции значимости S (w), превышающим значение Sn()po.-являются значимыми и используются при составлении сочетаний слов. S\w) Snopoe. (3.1) Остальные слова являются незначимыми и не используются для составления сочетаний слов.
Для объединения слов по классам значимости использован метод полиграмм (гистограмм) [74,24]. При этом значение выражения (3.1) используется для распределения всех слов словаря по непересекающимся областям наблюдений //, 1=1,2,3. Класс, соответствующий первой области, включает в себя слова, встретившиеся в текстах всего информационного фонда лишь один раз и являющиеся незначимыми, так как для них выражение (3.1) меньше 1 (см. 2.7). Второй класс объединяет значимые слова, для которых выражение (3.1) имеет значение больше 1. В третий класс попадают часто встречающиеся слова, значимость которых мала и выражение (3.1) принимает значения не больше 1.
Рассмотрим названные три класса слов более подробно. Редко встречающиеся слова (класс I) не позволяют извлекать статистические данные об их употреблении в сочетаниях с другими словами. Они не могут быть использованы при составлении сочетаний, но используются при обработке поисковых запросов. Слова класса II используются при формировании устойчивых сочетаний слов и при поиске. Слова, которые встречаются почти во всех текстах (класс III), не несут информации, полезной при проведении поиска. Их значимость мала, поэтому они автоматически не используются ни при составлении сочетаний, ни при поиске.
Признанные незначимыми слова не используются при составлении сочетаний. Но они не удаляются, а данные о частоте их появления в новых текстах дополняются при добавлении новых документов. Так как значение функции значимости S (w) зависит от частоты появления слова в тексте, при возрастании этой частоты значимость слова S (w) может возрасти достаточно для перехода слова в класс значимых. После этого для слова создаются все пропущенные ранее сочетания, и далее оно участвует в определении устойчивых сочетаний слов, которые определяют предметную область документа.
При дальнейшем росте частоты появления слова его значимость снижается. Например, после добавления в хранилище десятого текста тестового набора (см. гл. 4) частота повторения союза «который» возросла достаточно для переведения его в третий класс. При этом все сочетания, образованные с этим словом помечаются как ошибочные и не учитываются при поиске.
Описанный алгоритм контроля значимости слов позволяет сохранить актуальное состояние словаря и хранимой служебной информации при изменении данных о частоте появления слов после пополнения информационного фонда новыми документами.
При поиске устойчивых сочетаний формируются все возможные сочетания слов каждого Смыслового Фрагмента (СФ) текста. В данной работе единицей смысловой фрагментации текста является предложение, так как это основная единица изложения завершенной мысли и является «минимальной и вместе с тем основной единицей речевого общения» [103]. Повторяющиеся в текстах сочетания признаются устойчивыми и используются для оценки статистической сочетаемости этих слов.
Определение эмпирических пороговых значений и коэффициентов
Основную часть тестового информационного фонда составляли реферативные статьи. Использование относительно коротких текстов (1-2 страницы) облегчает экспертам задачу определения релевантности документов тестовым запросам.
Разработанная система предназначена для использования в библиотеке, работающей с постоянно пополняемыми фондами. Поэтому объем добавляемых текстов постепенно наращивался при оценке роста потребляемых системой ресурсов. В процессе исследования также анализировалось, как связан рост объема служебных таблиц с качеством поиска.
Определение порогового значения функции значимости
Для определения порогового значения значимости Snopw все слова словаря, полученного при обработке тестового набора текстов, были упорядочены по убыванию значения функции значимости, вычисленного для каждого слова. Экспертом проанализирован полученный список, в результате чего определена граница, выше которой располагаются слова, способные нести самостоятельный смысл. Для этих слов, являющихся значимыми, значение функции значимости превышает 0,05. Поэтому в данной работе Snopa принято равным 0,05 VJ«O/W=0,05).
Определение длины варьируемой суффиксной части слова Для определения оптимального значения параметра А/, ограничивающего длину варьируемой суффиксной части слова, было проведено фуппирование форм родственных слов с расстоянием редактирования равным 1 (первый этап группирования родственных слов) при А/ из интервала от 1 до 4. Результаты группирования родственных слов приведены в табл. 11.
Выбор допустимого расстояния редактирования р, используемого для признания слов родственными, обусловлен результатами эксперимента, в котором оценивалось качество поиска родственных слов с учетом их статистической сочетаемости с одинаковыми сочетаниями слов (второй этап фуппирования родственных слов) при различных значениях параметра р из интервала от 2 до 5 (табл. 12).
В результате эксперимента (рис. 4.10) определено, что увеличение р вызывает резкое снижение качества группирования слов. Поэтому офаничение на максимальное значение р зафиксировано при достижении суммарной доли верно Сфуппированных слов равной 50% слов в словаре, чтобы сократить объем словаря в 2 раза. Такого эффекта удалось достичь при значении р равном 2, поэтому для значения допустимого расстояния редактирования р выбрано значение 2 (р=2). Определение ограничения для расстояния редактирования Определение длины обрабатываемых сочетаний слов
Для определения максимальной длины К составляемых сочетаний слов проведены эксперименты по составлению словаря контекстно-зависимых синонимов, используя таблицы сочетаний слов различной длины К (для Л=2,3,4,5). При этом оценивалось количество найденных пар контекстно зависимых синонимов и среди них доля верно обнаруженных синонимов (табл. 13).
Из приведенных на рис. 4.11 графиков следует, что при А 3 точность определения синонимов почти прекращает рост. При этом количество полученных контекстно-зависимых синонимов снижается, поэтому принято ограничение на минимальную длину сочетаний, используемых при поиске синонимов, в 4 слова (К 3).
Сокращение количества создаваемых и хранимых сочетаний слов При выполнении предварительных действий по созданию служебных таблиц требуется значительный объем дисковой памяти для хранения служебной поисковой информации. Созданные таблицы могут иметь объем, превышающий объем самих документов. С ростом объемов получаемой и хранимой информации возрастает время её обработки. При обработке тестового набора документов объем служебных данных почти на 2 порядка превысил объем исходного текста. Большую часть этого объема занимают данные таблицы всех сочетаний слов. Количество составленных и сохраненных в ней сочетаний на 3 порядка больше количества слов в словаре. В предельном случае количество хранимых сочетаний слов может достичь числа всех возможных сочетаний слов документа, поэтому важно сократить объем таблицы сочетаний.
Анализ полученных словаря и таблиц служебной информации позволяет исключить избыточные данные при подготовке поисковых индексов и выполнении поисковых запросов. Для оценки полезности составления сочетаний различной длины рассмотрим зависимость количества повторений сочетаний от их длины. Число повторений сочетаний различной длины в тестовом наборе текстов приведено в табл. 14.
