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

НА ПРАВАХ РУКОПИСИ УДК 681.5.015.32

БОЙЦОВ Леонид Моисеевич

Синтез системы автоматической коррекции, индексации и поиска текстовой информации.

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

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Москва - 2003

Работа выполнена в Московской академии рынка труда и информационных технологий.

Научный доктор дгаштаоких наук,

руководитель: профессор Крылов Григорий Олегович

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

оппоненты: профессор Казаков Олег Леонидович

кандидат технических наук, Ануфриев Владимир Натанович

Ведущая Институт микропроцессорных вычислительных

организация: систем РАН.

Защита состоится -^СС&С^Ь, 2003 года на заседании диссертационного совета Д 850.01.01 при Московской академии рынка труда и информационных технологий в /У часов.

С диссертацией можно ознакомиться в библиотеке Московской академии рынка труда и информационных технологий по адресу: 121351, г. Москва, ул. Молодогвардейская, д. 46, корп. 1.

Автореферат разослан

2 оо&ил

2003 года.

Учёный секретарь

диссертационного совета Д 850.01А

канд. техн. наук, профессор Чересов Ю.И.

СЬоЗ^А

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

! Актуальность темы. В современных информационных системах полнотекстовый

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

I Первые информационно-поисковые системы (ИПС) появились более тридцати лет назад,

и с тех произошли существенные изменения как в поисковых алгоритмах, так и в | техническом оснащении. Современные поисковые системы (ПС) «научились»

I автоматически собирать информацию в интернете, учитывать морфологические

особенности и гипертекстовую структуру документов.

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

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

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

Программный комплекс коррекции и индексации документов должен 1 функционировать как единая открытая система: оператор принимает решение о выборе

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

Большинство современных программ проверки орфографии такие, как спел-чекер текстового процессора Ms Word или программа ispell - универсальны и используют статические языковые словари. Это значит, что они не подходят для обработки

HjC НАЦИОНАЛЬНАЯ I БИБЛИОТЕКА I

¿n,S&fe? \

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

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

Наиболее распространенные типы ошибок - это орфографические ошибки, опечатки и ошибки распознавания (сканирования). Орфографические искажения часто связаны с похожестью звучания, например, замена «а» на «о», удвоение согласных и пр. Ошибки распознавания возникают из-за визуальной похожести символов и могут порождать с высокой вероятностью замены «8» на «з», «I» на «1», а опечатки вызваны ошибками при наборе на клавиатуре. Как правило, правильный символ заменяется символом одной из соседних клавиш или символом из другого языкового регистра. С использованием языкового словаря описанные искажения могут быть скорректированы автоматически.

Проблема коррекции «фонетических» искажений достаточно неплохо исследована. Так, например, функция вОШТОЕХ, оценивающая похожесть звучания английских слов, реализована в большинстве современных СУБД. К сожалению, алгоритм вОШОЕХ не очень хорошо параметризуется, и, как отмечают в своей работе Зобель и Дарт, обладает невысокой точностью и полнотой.

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

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

Чтобы откорректированные тексты не лежали «мертвым грузом», необходимо обеспечить эффективный и функциональный поиск в массиве документов. Рассматриваемое в диссертационной работе интегрированное программное решение ориентировано на использование на персональной ЭВМ или небольшом сервере. Это значит, что, с одной стороны, оно должно быть недорогим и эффективным, а с другой стороны, экономичным в смысле использования процессорного времени. В идеале процесс индексации и коррекции должен происходить незаметно для пользователя.

В последнее время все чаще задачу создания недорогих и эффективных поисковых систем пытаются решить с помощью готовых инструментов для хранения и обработки данных, в основном, реляционных и объектных СУБД. В качестве примера можно привести ИПС MnogoSearch (littpV/www.rnnogosearch rul и AspSeek (http'/Avww aspseck org). Существенной особенностью такого подхода является многоплатформенность, понимаемая как совместимость с различными СУБД: пользователь может купить дешевую СУБД, либо использовать уже приобретенную.

Существует довольно много расширений СУБД (т.к. называемых экстендеров), обеспечивающих полнотекстовый поиск в текстовых полях таблиц баз данных. Расширения СУБД для полнотекстового поиска достаточно специфичны: они не удовлетворяют единому стандарту, их внедрение может потребовать больших затрат на обучение специалистов и закупку нового программного обеспечения, поэтому их область применения ограниченна. Используя такую систему, пользователь «привязывает» себя к конкретной реализации СУБД

В свою очередь, подход, основанный на использовании стандартных интерфейсов баз данных, в т.ч. языка SQL, отличается большой гибкостью и низкой стоимостью разработки. Однако СУБД имеет ряд недостатков. Вели используется чисто реляционная модель, когда каждое вхождение слова в документ представлено записью в таблице ссылок, то скорость поиска и индексации оставляют желать лучшего Проблемы появляются при работе с коллекциями среднего размера: порядка 1 млн. документов. При этом среднее время индексации одного документа может составлять 2-3 секунды, а средняя скорость поиска - 10-20 секунд.

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

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

Наиболее популярное решение проблемы низкой производительности заключается в кластеризации. Как правило, рядовой пользователь не имеет возможности выделить несколько ЭВМ для распараллеливания поискового процесса, поэтому задача повышения производительности пользовательских поисковых систем или поисковых систем малых предприятий, использующих СУБД в качестве хранилища индекса, исключительно актуальна.

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

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

□ Создание модуля индексации и поиска, использующего для хранения индекса реляционную СУБД. Модуль должен быть переносимым, те. «уметь» работать с различными СУБД, обеспечивать высокую скорость индексации и поиска: порядка одного запроса в секунду для текстуальных коллекций среднего размера вплоть до 1 млн. документов. Модуль индексации должен обеспечивать создание, а также обновление сжатых (упакованных) индексов.

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

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

Задачи исследования.

1. Выбрать набор характеристик для оценки целесообразности алгоритмов нечеткого словарного поиска Получить числовые значения выбранных характеристик и применить МГК для выбора структуры словаря в модуле автокоррекции.

2. Оптимизировать и реализовать метод хеширования по сигнатуре, получить теоретические оценки его эффективности и проверить их экспериментально.

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

4. Произвести экспериментальную проверку метода блочной адресации.

Методы исследования. Для решения поставленных задач в работе использованы методы системного анализа, математической статистики, теории вероятности, математического анализа, комбинаторики и численные методы линейной алгебры.

Научная новизна.

1. Разработана методика ранжирования реализаций алгоритмов нечеткого словарного поиска на основе данных экспериментальной проверки и экспертных оценок. В результате се применения было получено, что реализации йче-деревьев и ХС лучше других использованных методов. Они обеспечивают хорошее время доступа: менее 20 мс в случае индекса, загруженного в ОЗУ, и порядка 100 мс в случае «дискового» поиска для словарей, содержащих 3 миллиона терминов.

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

' до 1 млн документов со средним объемом текста 4-5 килобайт

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

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

Практическая значимость. Разработанный метод словарного поиска использован в поисковой машине Пунто ЛШр/Ауууц' рипЮ-ш). разработанной фирмой «Аллсистем», что подтверждается актом внедрения.

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

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

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

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

4. Экспериментальная проверка показала, что метод блочной адресации может быть использован для индексации коллекций среднего размера: порядка 1 млн. документов. Предложенный метод является переносимым с точки зрения использования различных СУБД, по скорости поиска и индексации соответствует коммерческим аналогам, системам с открытым кодом, а по некоторым показателям и превосходит их.

Апробация работы. Материалы исследования доложены и обсуждены:

1. Международная конференция «Математика, Компьютер, Образование». Пугцино 2001.

2. Международная конференция студентов и молодых ученых «Системный анализ и информационные технологии». Киев 2001.

Публикации материалов исследований. По теме диссертации автором опубликовано пять работ общим объемом около 2 печатных листов.

Объем и структура диссертации. Диссертация состоит из введения, 4 глав, заключения, приложений, списка литературы и изложена на 147 листах машинописного текста, в том числе основного текста на 134 листах. Работа иллюстрирована 13 таблицами и 9 графиками Список литературы содержит 99 источников, в том числе 80 на иностранных языках.

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

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

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

Во второй главе анализируется алгоритм хеширования по сигнатуре (ХС) Метод ХС: разновидность комбинаторного хеширования и основан на группировке слов по сигнатуре. В качестве сигнатуры слова выбирается битовая маска, в которой i-ый бит равен 1, если слово содержит хотя бы одну букву из i'-ой группы алфавита.

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

В третьем разделе второй главы выводится формула эффективности ХС для частных случаев: точного соответствия и соответствия в пределах одной операции редактирования в предположении, что вероятности появления букв из различных алфавитных групп приблизительно равны. Стремление равномерно распределить слова по группам не случайно: такое распределение позволяет примерно в 2-3 раза улучшить время поиска.

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

Пусть максимальная длина слова равна п, общее число слов равно L, для всех I (О < / < п) известна pt - вероятность появления слова длины I. Обозначим через qt(k)

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

для поиска на точное равенство:

Шг

для нечеткого поиска в пределах одной ошибки: L J^CkmPlipq (Л)((1 + т{т-k)gh (к)+kq,2 (к) + (т-k)qu (к +1)) (2)

Величины qj{k) имеют аналитическое выражение через числа Стирлинга второго

рода:

Число Стерлинга второго рода I' I равно числу разбиения множества из /

ш

элементов на к групп без учета порядка множеств.

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

Если через ^ (г,,г2,..., ¡к ) обозначить вероятность появления сигнатуры с

единичными битами, номера которых равны г(, г2,..., г^» в слове длины то для

математического ожидания сложности поиска справедлива следующая формула:

1 X Е Л,АД,,(<„'2.....'»)■

XX О»'г.....+

к

IX 1.4......'1 Ч)+ IX ('"'г.....'»

У-1 I,)

(3)

Для компактной записи оценки эффективности поиска на неточное равенство используются следующие упрощающие обозначения:

(¡и г2,...,г4 ¡]) ~ это набор индексов размером к+1, который получается из

набора (('/.,/.) в результате добавления индекса / . Аналогично,

(г'1,г2,...,г1[ \ /,) _ э™ набор индексов размером к-1, который получается из

исходного набора размером к в результате «изъятия» индекса ¡^

Вероятности ^ (/,, г2,..., ) сложно рассчитать аналитически, но их можно

эффективно вычислить на компьютере (то же самое верно и для равных вероятностей ? )

с помощью формулы:

к к яЛЧ'Н.....Й) = 2>.,<7-10'.,<'2.•••>'* Ч) + 2Х?»-1(«1»1'2»•••»<*)

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

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

В третьей главе проводится сравнительный анализ пяти наиболее известных методов словарного поиска по сходству, включая ХС, с помощью метода главных компонент. Анализ базируется на результатах экспериментальной проверки алгоритмов на словарях, содержащих от ста тысяч до 3.2 миллионов терминов, и экспертных оценках сложности реализации методов. Для экспериментальной проверки используется компьютер Pentium с тактовой частотой 1 Гц объемом ОЗУ 512 мегабайт и IDE диском, работающий под управлением ОС Linux Red Hat 7 2. В процессе исследования учитывались следующие характеристики:

□ размер индекса

□ время создания индекса в памяти

□ время записи индекса на диск

□ время поиска при максимально допустимом расстоянии Левенштейна равном 0,1 и 2 для индекса загруженного в память.

□ время поиска при максимально допустимом расстоянии Левенштейна равном 0,1 и 2 для «дискового» поиска.

□ сложность реализации, в том числе «дисковой» версии.

□ используется ли для реализации индекса библиотека индексных файлов.

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

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

Хеширование по сигнатуре (мнемонический код SignHashDisc) описано нами выше и основано на группировке слов по набору, содержащихся в них букв.

Trie-деревья или лучи (Tries). Trie-дерево строится по следующему принципу: все слова, имеющие одинаковый префикс, размещаются в одном и том же поддереве. Например, для слов тара, тарелка, торт, тормоз соответствующее trie-дерево изображено на рис. 1:

Рис. 1 Пример trie-дерева

Каждая ветка поддерева помечена строкой. Конкатенация строк веток при спуске из корня дерева в лист - это слово, соответствующее листу дереву. Например, в дереве, изображенном на рис.1, самый левый лист соответствует слову тара. При спуске из корня дерева сначала присоединяется подстрока т, потом подстрока ар, а в самом конце - подстрока а.

Trie-дерево особенно эффективно для поиска слов по префиксу, но его можно использовать и для нечеткого поиска. Если задано максимально допустимое число ошибок к, префикс р и искомое слово w, то, используя метод динамического программирования, можно определить, есть ли у искомого слова префикс, отличающий от р не более чем на к опечаток. Это свойство позволяет искать в trie-деревьях достаточно эффективно и отличать поддеревья, содержащие искомые слова от тех, которые искомые слова не могут содержать.

Пусть, например, нужно найти слово ара с точностью до одной опечатки. Искать ' начинаем с корня дерева. У корня есть поддерево, которому соответствуют префикс т. Расстояние редактирования между т и началом слова ара длины 1 равно 1, значит нужно продолжать поиск в поддеревьях рассмотренного узла. У этого узла есть два поддерева, соответствующие префиксам тар и тор, соответственно. Минимальное расстояние редактирования между префиксом искомого слова ара (длины 2) и префиксом первого поддерева (тар) равно 1, значит нужно продолжить поиск в левом поддереве (см. рис 1) Это не верно для правого поддерева, которое исключается из дальнейшего рассмотрения. Окончательно получаем два слова-кандидата: тара и тарелка, из которых только одно соответствует поисковому образцу.

Метод n-грамм (Ingram), n-граммы слова - это подстроки длины п. Если построить для каждого слова множество его n-грамм и проиндексировать слова относительно встречаемости в них различных n-грамм, то построенный индекс позволит искать по сходству.

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

Рассмотрим пример поиска для максимально допустимого расстояния Левенштейна равного 1. Разобьем слово w на два подслова щ и . С помощью построенного индекса

можно найти номера всех слов, содержащих подстроку vv, или ц/2 следующим образом. Если искомая подстрока w имеет длину больше чем длина п-граммы, то считываются списки вхождений всех n-грамм искомой подстроки и строится их пересечение, а если меньше, то считываются списки вхождений всех n-грамм, начинающихся с искомой подстроки, и строится их объединение. Для каждого слова из найденного списка номеров проверяется соответствие поисковому образцу непосредственно, а именно: текст слова считывается по номеру и сравнивается с поисковым образцом с помощью «от-line» метода

Частотные trie-деревья (FreqTries). Разобьем алфавит на М пронумерованных подмножеств (М порядка 20) и преобразуем слова в векторы размера М следующим образом: положим i-ый компонент равным числу букв из i-ro подмножества, которые встречаются в слове. Такой вектор будем называть частотной сигнатурой слова. Между частотной сигнатурой и сигнатурой слова в методе ХС есть много похожего. Например, сигнатуры обеих типов строятся без учета позиций букв. Тем не менее, частотная сигнатура более информативна и потенциально должна обеспечивать большую избирательность: вероятность того, что слово имеет заданную частотную сигнатуру в среднем меньше, чем для сигнатуры метода ХС.

Если расстояние редактирования между словами vf, и ц>2 равно г, то расстояние

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

Для быстрой выборки векторы организуются в виде trie-дерева. При этом алгоритм поиска в таком дереве отличается от алгоритма поиска в текстовом trie-дереве: проверка наличия похожих префиксов заменяется вычислением расстояние между префиксами

векторов равной длины и сравнением с удвоенным максимально допустимым расстоянием Левенштейна.

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

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

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

Поиск основан на неравенстве треугольника. Пусть, например, нужно найти слово и», удаленное от поискового образца не более чем на к. Рассмотрим корень дерева \vroot. В силу неравенства треугольника искомые слова не могут быть в поддеревьях с номерами меньшими Цу/,уиго<л)-к или большими Цм.у/гоо^+к. Для поддеревьев с номерами от Цтм.мгоо^-к до ¿(ш^гоо!)+к описанная поисковая процедура повторяется рекурсивно.

2 4 8 16

Число терминов (согни тысяч)

Рис. 2 Зависимость скорости поиска в индексе, загруженном в память, от числа терминов в словаре

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

дисковых страниц. В силу простоты метода, такой менеджер дисковых страниц был реализован только для ХС.

Для реализации метода n-грамм используется библиотека индексных файлов Berkley DB, а все древовидные структуры (метрические деревья, текстовые и частотные trie-деревья) имеют статический дисковый индекс, который не позволяет добавлять новые записи без полного его пересоздания.

Прежде чем применить МГК, рассмотрим графики зависимости скорости поиска от размера словаря для методов ХС, trie-деревьев, и частотных деревьев, составляющих Парето оптимальное множество по совокупности всех характеристик, кроме оценок сложности реализации. Данные по скорости поиска приведены на рисунках 2 и 3.

Из анализа первого графика видно, что самым эффективным методом поиска являются trie-деревья. При этом ч&гко прослеживается сублинейность: время поиска практически не зависит от числа терминов и составляет примерно 3 миллисекунды.

Методы сигнатурного кеша и частотных деревьев, работают медленнее и не являются строго сублинейными: увеличение размера словаря в 32 раза приводит к примерно десятикратному замедлению. Как несложно заметить, метод ХС является также и самым «медленным».

450 400

| 350

§ 300

ч

| 250

I" 200

и

| 150

3 100

<3

!§- 50 О

Рис. 3 Зависимость скорости поиска в индексе (прямые чтения с диска) от числа терминов словаря

Ситуация в корне меняется для случая прямых дисковых чтений. Как видно из рис 3, метод ХС не только является самым «быстрым», но и имеет самый маленький рост времени поиска с увеличением размера словаря, в то время как trie-деревья - самый большой. Налицо неоднозначность, свойственная сравнению векторных показателей. Для разрешения этой неоднозначности используется метод главных компонент (МГК). Суть метода заключается в выделении совокупности небольшого числа наиболее

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

МГК применим в случае, если результаты исследований п объектов могут быть представлены в виде матрицы (V у ... Y ) размерности пхт, где т - число

V I' z>* ' fít /

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

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

Одна из основных трудностей сравнения методов на основе наблюдений случайной величины У заключается в том, что компоненты У не являются независимыми и коррелируют между собой. В предположении линейности модели можно представить результаты наблюдений У в виде линейной комбинации наблюдений компонентов случайной величины F размерности т, которые не коррелируют между собой:

т

Уц №

*=i

Известно, что если матрица корреляции R компонентов векторной случайной величины у положительно определена, то матрица А, удовлетворяющая равенству (4) существует, имеет обратную, а элементы А равны корреляции между компонентами случайных величин у и/. corr (у:, f ) - а, ■

Столбцы f матрицы наблюдений случайной величины F принято называть главными компонентами (ГК). Они, как и у/, центрированы и нормированы.

Для вычисления матрицы А нужно решить характеристическое уравнение матрицы корреляции. Если U - матрица из собственных векторов R, X - собственные числа R, а

Л1'2 - диагональная матрица, диагональ которой составлена из чисел я|/г, то

А = Í/A1'2 (5)

Используя (5), выразим значения главных компонент через значения наблюденных (центрированных и нормированных) характеристик:

ft=YyLmk*auyL (6)

Интерпретация и осмысленное ранжирование является наиболее тонким моментом применения МГК. Дело в том, что для осуществления такого ранжирования необходимо

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

Применим МПС в задаче синтеза модуля коррекции Рассмотрим сначала случай словаря самого большого размера (3.2 млн. терминов). Перечислим измеряемые характеристики методов в порядке возрастания нумерации:

Номер характер. Расшифровка

1 размер индекса (в байтах),

2 время создания индекса в памяти (в миллисекундах)

3 время записи индекса на даек (в миллисекундах)

4-6 время поиска (в миллисекундах) при максимально допустимом расстоянии Левенштейна равном 0,1 и 2 для индекса загруженного в память.

7-9 время поиска (в миллисекундах) при максимально допустимом расстоянии Левенштейна равном 0,1 и 2 для случая «дискового» поиска.

10 сложность реализации для поиска в памяти

11 сложность реализации для прямых дисковых чтений

12 Признак использования библиотек индексных файлов

Табл. 1 Результаты тестирования для словаря размером 3.2 млн. терминов

1 2 3 4 5 6 7 8 9 10 11 12

SignHashDisc 28655 226248 9293 0 258 19.806 162.976 40.044 219.275 490.581 1.5 2 0

Тпев 16005 62663 6018 0.071 3.291 51.653 61.96 352.651 581.468 2 4 0

Рга]Тпез 28208 397682 8353 0.189 15.023 162.026 137.229 416.71 1277.5 3 4 0

МЬгее 63507 364714 45798 0.074 268.069 3246.37 122.239 1436.13 13620.8 2.5 3.5 0

1п§гаш 130060 869851 167408 313.68 29633.5 42429 1216.36 75317 160349 1 2 1

Анализ матрицы корреляции признаков (см. табл. 2) позволяет выявить интересные закономерности. В частности, как время поиска, так и время создания индекса, положительно коррелируют с размером индекса, и отрицательно, но в меньшей степени, со сложностью реализации. Размер индекса также отрицательно коррелирует со сложностью реализации.

Табл. 2 Матрица корреляции характеристик поисковых методов2

1 2 3 4 1 6 7 Я 9 10 11 12

1 1000 0 938 0 986 0 924 0 927 0949 0 937 0 929 0 951 -0 575 ■0 515 0 924

2 0 938 1 ООО 0 924 0 899 0901 0912 0 924 0 902 0913 -0 422 -0 522 0 899

3 0 986 0 924 1000 0971 0 973 0 986 0 977 0 974 0 987 -0 644 -0 576 0 971

4 0 924 0 899 0 971 1 000 1 000 0 997 0 997 1 000 0 997 -0 707 -0 600 1000

5 0 927 0 901 0 973 1 000 1 000 0 998 0 997 1 000 0 997 -0 706 -0 600 1 000

6 0 949 0 912 0986 0997 0 998 1000 0 997 0 998 1 000 -0 692 -0 594 0 997

7 0 937 0 924 0 977 0 997 0 997 0 997 1 000 0 997 0 997 -0 650 -0 357 0 997

8 0 929 0 902 0 974 1000 1000 0 998 0 997 1 000 0 998 -0 703 -0 597 1 000

9 0951 0913 0 987 0997 0997 1000 0 997 0 998 1 000 -0 688 -0 591 0997

10 -0 575 -0 422 -0 644 -0 707 -0 706 -0 692 -0 650 -0 703 -0 688 1000 0 849 -0 707

II -0 575 -0 522 •0 576 -0 600 -0 600 -0 594 -0 557 -0 597 -0 591 0 849 1000 -С 600

12 0 924 0 899 0 971 1 000 1000 0 997 0 997 1 000 0 997 -0 707 -0 600 1 000

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

Еще одна интересная закономерность заключается в том, что значения времени поиска для различных величин максимально допустимого расстояния Левенштейна и типа поиска («дисковый» или поиск в памяти) очень сильно коррелируют.

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

Действительно, решив характеристическое уравнение, получаем, что четыре максимальных собственных значения равны: 10.58, 1.01, 0.30, 0 09, а самое большое собственное значение отвечает примерно за 89% всей дисперсии. Остальные собственные значения настолько малы, что их можно считать равными нулю. Даже 3-е и 4-ое собственное значение и соответствующие собственные вектора не играют особой роли в задаче факторного анализа, потому что им соответствует не более четырёх процентов дисперсии. Это подтверждает предположение, что решаемая задача фактически двумерна.

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

2 все значения для удобства отображения округлены до Зх знаков после запятой

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

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

Зная величины первых главных компонент (см. табл. 4), можно вычислить эффективность согласно данному определению. Как и ожидалось, для всех методов она одинакова и равна отношению сумм положительных элементов первого столбца матрицы А к сумме абсолютных значений отрицательных элементов первого столбца А. Поскольку относительно ГК1 все методы одинаково эффективны, то необходимо ранжировать их по производительности. В итоге, используя данные таблицы 4, получаем, что лучшим является метод Цте-деревьев, за ним идут ХС и частотные деревья. Замыкают рейтинг метрические деревья и метод п-грамм.

Табл. 3 Матрица преобразования главных компонент к центрированным, нормированным векторам наблюдений3

0952 -0 141 -0 175 -0208 0 0 0 0 0 0 0 0

0 914 -0 264 -0 292 0 098 0 0 0 0 0 0 0 0

0 984 -0 ПО -0 032 -0 139 0 0 0 0 0 0 0 0

0 993 -0044 0090 0 057 0 0 0 0 0 0 0 0

0994 -0046 0 086 0 050 0 0 0 0 0 0 0 0

0 996 -0 066 0 056 -0003 0 0 0 0 0 0 0 0

0990 -0 118 0.059 0 056 0 0 0 0 0 0 0 0

0 994 -0 050 0 084 0 045 0 0 0 0 0 0 0 0

0 996 -0072 0 054 -0 008 0 0 0 0 0 0 0 0

-0 725 -0651 -0215 0067 0 0 0 0 0 0 0 0

-0 659 -0 680 0315 -0 060 0 0 0 0 0 0 0 0

0 993 -0 044 0 090 0 057 0 0 0 0 0 0 0 0

Эксперименты были проведены для шести словарей различных размеров. Было бы неправильным использовать только часть результатов для построения рейтинга. С точки

3 все значения для удобства отображении округлены до Зх знаков после запитой

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

□ ГК1 соответствует более 80% дисперсии, а доля дисперсии первых двух ГК больше 95%.

□ Рейтинг методов относительно ГК1 практически неизменен для различных тестовых наборов.

Табл. 4 Значения первых четырёх главных компонет

SignHashDisc Tries FreqTries Mtree Ingram

ГК1 -0.05 -0.18 -0.01 0.224 3.077

ГК2 1.825 1.669 1 084 0.991 -1.17

ГКЗ -1.9 -0.59 -2 25 -2.72 -0.75

ГК4 -1.47 -1.44 -0.54 -4.24 -2.13

Единственное небольшое отличие заключается в том, что для небольших словарей ГК1 «уравнивает» ХС и частотные деревья, поэтому для более тонкого сравнения были использованы значения второй ГК.

Смысл ГК2 также довольно прост: единственный фактор, с которыми она заметно и притом отрицательно коррелирует - это сложность реализации. Относительно ГК2 метод ХС предпочтительнее метода частотных деревьев.

В четвертой главе исследуется задача применимости метода блочной адресации в качестве базового метода модуля индексации.

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

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

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

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

Кроме словаря индекс содержит списки вхождений слов в текст. Списки вхождений слова описывают множество вхождений слова в документы. ИФ и СФ отличаются в способе кодирования этого множества. В общем случае множество вхождений — это линейный список всех четвёрок вида:

('номер слова', 'номер документа', 'раздел документа,' 'позиция слова в документе')

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

('номер слова', 'номер документа')

Если позиция слова и номер раздела документа не хранятся в индексе, то индекс называется некоординатным.

В СФ в отличие от ИФ хранится только маска вхождений. В простейшей модификации, методе битовых строк, такая маска строится следующим образом. Выбирается достаточно большое число N и хеш-функция /(п), отображающее номер документа в число от 1 до N. Затем для всех номеров документов к, в которых встречается данный термин, элементам битовой строки с номерами /(к) присваивается значение 1. Остальные элементы обнуляются.

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

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

В работах Дж. Зобеля анализируется и проверяется экспериментально несколько модификаций СФ. В результате авторы приходят к выводу, что ИФ по всем параметрам лучше СФ. Основной недостаток СФ заключается в необходимости считывания текстов всех «кандидатов» для исключения «ложных попаданий». В случае ИФ это требуется

только на стадии отображения результатов дм формирования так называемой аннотации4. Следует также отметить, что индекс ИФ файла может быть исключительно компактным - не более 30-40% от общего объема текста Таким образом, ИФ являются более подходящей структурой для реализации полнотекстового индекса, чем СФ.

Ранее были упомянуты две ПС с открытыми исходными текстами: Aspseek и MnogoSearch. Эти ПС используют два наиболее распространенных метода хранения ИФ с использованием реляционной СУБД. В том, что касается реализации словаря текстового массива, оба подхода совпадают: словарь хранится в виде таблицы, где есть поля: 'номер слова', 'слово', 'адрес списка вхождений', проиндексированной по полям 'номер слова' и 'слово'. Различаются они в хранении списков вхождений (инвертированных списков).

Напомним, что списки вхождений - это множество четверок вида: ('номер слова', 'номер документа', 'раздел документа', 'позиция слова в документе')

Такие четверки, называемые в реляционной алгебре кортежами, идеально соответствуют понятию строки таблицы в реляционной СУБД. Чтобы иметь возможность быстро считать все кортежи, относящиеся к одному слову и/или документу, необходимо проиндексировать их по полям 'номер слова' и 'номер документа'. Будет называть такую реализацию ИФ чисто реляционной. Чисто реляционный подход существенно упрощает реализацию индексирующих и поисковых модулей, однако обеспечивает низкую скорость индексации и поиска.

ПС MnogoSearch не может индексировать более 50-80 тысяч страниц в день даже с использованием довольно быстрых серверов таких, как двухпроцессорный Pentium 800 с рейд-массивом из 4 SCSI-дисков и 1Гб ОЗУ. При этом среднее время поиска в документальной коллекции, содержащей 1млн документов, составляет порядка 20 секунд.

Добавление документа в ИФ требует нескольких сотен операций типа INSERT, поэтому на индексацию одного документа затрачивается 2-3 секунды. Проблема заключается не только в низкой скорости, но и также в высокой загрузке компьютера. Кластеризация позволяет решить проблемы с производительностью, но существенно увеличивает так называемую стоимость владения: арендная плата за помещение, плата за электроэнергию и расходы на администрирование и поддержку системы многократно возрастают.

4 Аннотация - это краткая выдержка из документа, в которую входят несколько предложений, или частей предложений, содержащих найденные слова запроса

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

Описанный способ хранения обеспечивает большую производительность. За счет физической близости считываемых в процессе поиска данных достигается почти десятикратный выигрыш в скорости: на объеме данных порядка 1 млн. документов среднее время поиска сокращается с 20 до 3 секунд.

Тем не менее, обновление такого ИФ в реальном времени, когда сразу же после добавления документа возможен поиск по его содержимому, невозможно Актуализация индекса осуществляется инкрементно: в процессе разбора документов накапливается множество кортежей, на основе которого формируется временный ИФ. После окончания индексации заданного набора документов производится слияние основного и временного индексов.

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

В основе блочной индексации лежит разбиение на блоки, содержащие примерно одинаковое число документов. Блокам присваиваются уникальные идентификаторы. Каждый блок может рассматриваться, как некоторый документ. Список таких документов инвертируется: строится некоординатный инвертированный файл, не содержащий данных по точному местоположению слов в блоке. Построенный инвертированный файл используется для поиска. Поиск слова w осуществляется следующим образом: считывается список блоков, содержащих термин и>, после чего каждый блок сканируется, В процессе обработки конъюнктивного запроса wt

Wj... дочитываются списки блоков, содержащие слова w2 > ■•■.w„>

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

3 Blob или Memo поля позволяют хранить неструктурированные данные очень большого размера

длиною в несколько сотен или даже тысяч мегабайт.

Как показали эксперименты, метод блочной адресации «в чистом виде» не слишком пригоден для использования на практике, а поиск в довольно скромной базе данных (100 тысяч документов) может осуществляться более 30 секунд Тем не менее, блочный индекс очень привлекателен с точки зрения скорости обновления, поэтому он был модифицирован, а разработанные модификации были проверены экспериментально.

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

1200 1000

I •00 | 600

400

200

о

1 2 3 4 5

чмспадцщшиил >бк!1ос»мщщ*>Ч№(мпи ДВфммт)

Рис. 4 Время индексация миллиона документов

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

Эксперименты с хранением в индексе верхнего уровня сигнатурного файла показали, что вместо сигнатуры целесообразнее использовать сжатый покоординатный индекс и список так называемых «титульных» вхождений. «Титульные» вхождения были впервые использованы создателями поисковой машины Google fhttp7/w\wv google.com) и с точки зрения автора работы вклад этого нововведения в успех поисковой машины был не меньшим, чем применение взвешенного индекса цитирования.

Почти в любом текстовом документе можно выделить набор наиболее важных ключевых слов. Как правило, они берутся из начала документа и из заголовка (отсюда и название «титульные»). Такие ключевые слова являются псевдо-рефератом документа, а

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

овин баш млн докрмкпм)

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

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

- существенная оптимизация операций ввода/вывода. Кроме того, индекс второго уровня

- статический, а значит, обеспечивает максимальное быстродействие при чтении с диска и может быть сжатым.

Для проверки эффективности метода была исследована зависимость скорости поиска и индексации' от размера базы. Дополнительно подсчитывалось количество запросов в разрезе числа слов, для которых титульных ссылок достаточно для выдачи первой (10 записей) страницы результатов. Результаты экспериментов для блока размером 10000 приведены на рисунках (4-6).

' время индексации очередного миллиона документов в зависимости от размера документальной базы

Рис. б Скорость поиска в зависимости от размера коллекции

По сравнению с чисто реляционным решением время индексации меньше почти на два порядка. Обработка миллиона документов занимает порядка трбх часов, что позволяет осуществлять полную переиндексацию такой коллекции каждый день практически без увеличения загрузки компьютера. Скорость поиска также заметно выше чем, скажем, в ПС MnogoSearch и сопоставима со скоростью поиска коммерческих систем и ПС AspSeek. Так, например, поисковое устройство Google7 обеспечивает аналогичное быстродействие (около 1 запроса в секунду) в документальной базе данных размером до 300 тысяч документов.

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

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

7 http:/№a w.google conv'appliance/hard^are html

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

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

В процессе исследований были получены следующие научные и практические результаты:

1. Разработана методика ранжирования реализаций алгоритмов нечеткого словарного поиска на основе характеристик, полученных в результате экспериментальной проверки для набора словарей различного размера и экспертных оценок. В результате применения предложенной методики было получено, что реализации trie-деревьев и ХС лучше других использованных методов. Они обеспечивают хорошее время доступа: менее 20 мс в случае индекса, загруженного в ОЗУ, и порядка 100 мс в случае «дискового» поиска для словарей, содержащих 3 миллиона терминов.

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

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

4. Эффективность предложенных алгоритмов индексации была проверена экспериментально. В частности, на ЭВМ Pentium с тактовой частотой 1 Гц объемом ОЗУ 512 мегабайт для документальной коллекции, содержащей 1 млн. документов, среднее время поиска равно примерно одной секунде, а полное время переиндексации - менее трех часов.

РАБОТЫ, ОПУБЛИКОВАННЫЕ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Реализация блочных индексных файлов с применением реляционных СУБД в задачах поиска информации. / Бойцов Л.М., Крылов Г.О.; Академия рынка труда и информационных технологоий - М. 2003, - 15 е.: - Библиогр. 6 назв. - Рус - Ил - Деп. в ВИНИТИ 18.04.03, № 748-В2003.

2. Использование хеширования по сигнатуре для поиска по сходству./ Бойцов Л.М.; ВМиК, МГУ - М. 2001, Прикладная математика и информатика. №8 2001, сс. 135-154.

3. Поиск по сходству в документальных базах данных. / Бойцов JIM.; Профессиональный журнал программист, (http//www programme ru), 2001. № 1, сс. 32-35.

4. Экспериментальное сравнение современных словарных методов поиска по сходству с хешированием по сигнатуре. / Бойцов Л.М., Тезисы международной конференции: «Системный анализ и информационные технологии», Киев 2001.

5. Поиск по сходству в документальных базах данных: хеширование по сигнатуре — оптимальное соотношение скорости поиска, простоты реализации и объема индексного файла. / Бойцов Л.М.; - M Прогресс-Традиция 2001, Труды международной конференции «Математика Компьютер. Образование», Выпуск №8.

Подписано в печать 21.05.2003 Формат 60x84 _Тираж 60 экз._

vi 2 O t

Qoo^-A

Список сокращений

ВВЕДЕНИЕ

ГЛАВА 1. Сущность задачи построения системы автокоррекции, индексации и поиска. Постановка задачи исследования.

1.1 Проблема сравнения векторных показателей. Методы снижения размерности и построения интегральных критериев.

1.2 Анализ существующих методов снижения размерности и построения интегральных критериев.

1.2.1 Эвристические методы.

1.2.2 Экспертные методы построения интегрального показателя

1.2.3 Экспертно-статистические методы построения интегрального показателя.

1.2.4 Метод экстремальной группировки признаков.

1.2.5 Многомерное шкалирование.

1.2.6 Факторный анализ.

1.2.7 Метод главных компонент.

1.2.8 Прочие методы снижения размерности.

1.3 Обзор исследований по проблеме информационного поиска и поиска по сходству.

1.3.1 Сущность задачи информационного поиска

1.3.2 Необходимые определения

1.3.3 Сравнение алгоритмов организации индекса ИПС.

1.3.3.1 Инвертированные файлы (ИФ).

1.3.3.2 Сигнатурные файлы (СФ).

1.3.3.3 Векторные модели (ВМ).

1.3.4 Сущность задачи текстового поиска по сходству.

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

1.3.6 Анализ методов словарного поиска по сходству.

1.3.6.1 Методы п-грамм.

1.3.6.2 Trie-деревья (лучи).

1.3.6.3 Метрические (триангуляционные) деревья.

1.4 Постановка задачи и обоснование методов исследования.

Выводы по Главе

ГЛАВА 2. Анализ хеширования по сигнатуре.

2.1 Анализов факторов, влияющие на скорость поиска по сходству

2.2 Описание метода хеширования по сигнатуре ключевых слов (ХС)

2.3 Оценки эффективности ХС.

2.4 Решение задачи коррекции текстов с особенностями с применением обобщенного расстояния редактирования.

0 Выводы по Главе

ГЛАВА 3. Синтез корректирующего модуля с использованием метода главных компонент.

3.1 Описание алгоритмов словарного поиска по сходству, использованных для тестирования.

3.1.1 Trie-деревья или лучи.

3.1.2 Метод п-грамм.

3.1.3 Частотные trie-деревья.

3.1.4 Метрические деревья. it 3.2 Адаптация метода главных компонент для сравнения методов словарного поиска по сходства.

3.3 Анализ экспериментальных данных методом главных компонент

Выводы по Главе

ГЛАВА 4. Реализация ИФ на базе реляционной СУБД.

4.1 Проблема реализации поискового модуля для персональной ЭВМ

4.2 Оценки размера индекса при «наивном» кодировании.

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

4.4 Решение задачи создания поискового модуля для персональной ЭВМ с использоанием сжатых модифицируемых ИФ.

4.4.1 Суть проблемы обновления ИФ.

4.4.2 Условия экспериментов.

4.4.3 Описание метода блочной адресации «в чистом виде».

4.4.4 Описание модификации метода блочной адресации N 1.

4.4.5 Описание модификации метода блочной адресации N 2.

4.4.6 Анализ результатов экспериментальной проверки модификации N 2.

Выводы по Главе

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

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

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

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

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

Большинство современных программ проверки орфографии, такие как спел-чекер текстового процессора Ms Word или программа ispell, - универсальны и используют статические языковые словари. Это значит, что они не подходят для обработки документов в условиях наличия небольшого набора вероятных искажений. В частности, такие искажения естественным образом возникают в результате сканирования с бумажных носителей, и обусловливаются спецификой процесса распознавания. Задача обработки считанных данных заключается в поиске правильных аналогов написания слов.

Наиболее распространенные типы ошибок - это орфографические ошибки, опечатки, и ошибки распознавания (сканирования). Орфографические искажения связаны, в основном, с похожестью звучания, например, замена «а» на «о», удвоение согласных и пр. Ошибки распознавания возникают из-за визуальной похожести символов и могут порождать с высокой вероятностью замены «8» на «з», «I» на «1», а опечатки вызваны ошибками при наборе на клавиатуре. Как правило, правильный символ заменяется символом одной из соседних клавиш, или символов из другого языкового регистра. С использование языкового словаря описанные искажения могут быть скорректированы автоматически.

Проблема, коррекции «фонетических» искажений достаточно неплохо исследована. Так, например, функция SOUNDEX, оценивающая похожесть звучания слов английских слов, реализовала в большинстве современных СУБД. К сожалению, алгоритм SOUNDEX не очень хорошо параметризуется, и, как отмечают в своей работе Зобель и Дарт, обладает невысокой точностью и полнотой.

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

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

Чтобы откорректированные тексты не лежали «мертвым грузом» необходимо обеспечить эффективный и функциональный поиск в массиве документов. Рассматриваемое в диссертационной работе интегрированное программное решение ориентировано для использования на персональной ЭВМ. Это значит, что с одной стороны, оно должно быть недорогим и эффективным, а с другой стороны, экономичным в смысле использования процессорного времени. В идеале процесс индексации и коррекции должен происходить незаметно для пользователя.

В последнее время все чаще задачу создания недорогих и эффективных поисковых систем пытаются решить с помощью готовых инструментов для хранения и обработки данных, в основном, реляционных и объектных СУБД. В качестве примера можно привести информационно поисковые системы (ИПС) MnogoSearch (http://www.mnogosearch.ru) и AspSeek (http://www.aspseek.org) . Существенной особенностью такого подхода является многоплатформенность, понимаемая, как совместимость с различными СУБД: пользователь может купить дешевую СУБД, либо использовать уже приобретенную.

Существует довольно много расширений СУБД (т.к. называемых экстенде-ров), обеспечивающих полнотекстовый поиск в таблицах базы данных. Расширения СУБД, обеспечивающие полнотекстовый поиск достаточно специфичны: они не удовлетворяют единому стандарту, их внедрение может потребовать больших ^ затрат на обучение специалистов и закупку нового программного обеспечения, поэтому их область применения ограниченна. Используя такую систему, пользователь «привязывает» себя к конкретной реализации СУБД.

В свою очередь, подход, основанный на использовании стандартных интерфейсов баз данных, в т.ч. языка SQL, отличается большой гибкостью и низкой стоимостью разработки. Однако применение СУБД имеет и свои недостатки. Если используется чисто реляционная модель, когда каждое вхождение слова в документ представлено записью в таблице ссылок, то скорость поиска и индексации оставляют желать лучшего. Проблемы появляются при работе с коллекциями среднего 10 размера: порядка 1млн. 2-3 трех-страничных документов. При этом среднее время индексации одного документа может составлять 2-3 секунды, а средняя скорость поиска - 10-20 секунд.

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

Наиболее популярное решение проблемы с производительностью - кластеризация. Как правило, рядовой пользователь не имеет возможности выделить несколько ЭВМ для распараллеливания поискового процесса, поэтому задача повышение производительности пользовательских поисковых систем или поисковых систем малых предприятий, использующих СУБД в качестве хранилища индекса, исключительно актуальна. Ее решение видится нам в использовании блочных индексов с инкрементной индексацией.

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

Для достижение цели потребовалось:

1. Выбрать набор характеристик для оценки целесообразности алгоритмов нечеткого словарного поиска. Получить числовые значения выбранных характеристик и применить МГК для выбора представления словаря в модуле автокоррекции.

2. Оптимизировать и реализовать метод хеширования по сигнатуре в модуле коррекции, получить теоретические оценки его эффективности и проверить их экспериментально.

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

4. Произвести экспериментальную проверку метода блочной адресации.

Решение поставленных в диссертации задач определило научную новизну исследования, которая заключается в том, что впервые:

1. Предложена методика ранжирования реализаций алгоритмов нечеткого словарного поиска на основе характеристик, полученных в результате экспериментальной проверки и экспертных оценок, с помощью метода главных компонент. В результате применения предложенной методики было получено, что реализации trie-деревьев и ХС лучше других использованных методов. Они обеспечивают хорошее время доступа: менее 20 мс для поиска в памяти и порядка 100 мс для «дискового» поиска для словарей, содержащих 3 млн. терминов.

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

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

4. Предложены алгоритмы для поисково-индексирующего модуля, использующего СУБД, дающие компромиссное решение задачи индексации и поиска на персональной ЭВМ. Предложенные алгоритмы обеспечивают высокую скорость инкрементной индексации, приемлемую скорость поиска, компактность индекса и переносимость в смысле использования различных СУБД.

Практическая значимость работы заключается в том, что результаты исследования используются в поисковой машине Punto (http://punto.ru), разработанной фирмой «Аллсистем» , что подтверждается актом внедрения.

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

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

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

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

4. Экспериментальная проверка показала, что метод блочной адресации может быть использован для индексации коллекций среднего размера: порядка 1 млн. документов. Предложенный метод является переносимым с точки зрения использования различных СУБД, а по скорости поиска и индексации соответствует коммерческим аналогам, системам с открытым кодом, а по некоторым показателям и превосходит их.

Диссертация состоит из введения, четырех глав, выводов, списка литературы, приложений и изложена на 144 листах машинописного текста, в том числе основного текста на 130 листах. Работа иллюстрирована 15 таблицами и 9 рисунками. Список литературы содержит 99 источников в том числе 80 на иностранных языках.

Выводы по Главе 4

1. Блочные индексы на основе реляционных СУБД позволяют сочетать эффективное индексирование и высокую скорость поиска в текстовых базах данных объемом до 1 млн. записей. Коммерческие продукты, например google search appliance, обеспечивают сходное быстродействие.

2. Блочные индексы позволяют создавать переносимые решения: программа может работать с любой реляционной СУБД при условии, что последняя поддерживает BLOB-поля. Это возможно в силу того, что при обращении к СУБД используется стандартизованный язык запросов SQL.

3. Описанная модификация N 2 как по скорости поиска, так и по скорости индексации превосходит чисто реляционные ПС. При этом чисто реляционное решение отстает в десятки раз по скорости индексации, и в 2-3 раза по скорости поиска.

4. В зависимости от объема индекса и частоты его обновления размер блока может быть от 10 тысяч до 50-100 тысяч документов.

5. Сложность реализации описанных блочных индексов на основе современных реляционных СУБД невелика, а время разработки продукта «под ключ» одним программистом варьируется от нескольких недель до нескольких месяцев. В частности, нами было затрачено менее двух месяцев на разработку и отладку всех описанных модификаций. Реализовать поисковую систему на основе блочных индексов лишь немного сложнее, чем чисто реляционный вариант.

ЗАКЛЮЧЕНИЕ

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

В процессе исследований были получены следующие научные и практические г%. результаты:

1. Разработана методика ранжирования реализаций алгоритмов нечеткого словарного поиска на основе характеристик, полученных в результате экспериментальной проверки и экспертных оценок. В результате применения предложенной методики было получено, что реализации trie-деревьев и ХС лучше других использованных методов. Они обеспечивают хорошее время доступа: менее 20 мс для поиска в памяти и порядка 100 мс для «дискового» поиска, для словарей, содержащих 3 миллиона терминов.

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

3. Предложены алгоритмы индексации, использующие СУБД в качестве вспомогательного хранилища индекса, реализующие компромиссное решение для сочетания высокой скорости инкрементной индексации, приемлемой скорости поиска, компактности индекса и переносимости в смысле использования разил личных СУБД.

4. Эффективность предложенных алгоритмов индексации была проверена экспериментально. В частности, на ЭВМ Pentium с тактовой частотой 1 Гц, объемом ОЗУ 512 мегабайт и документальной коллекции, содержащей 1 млн. документов, среднее время поиска равно примерно одной секунде, а полное время переиндексации коллекции - менее трех часов.

1. Абусев Р. А., Лумельский Я.П. Несмещенные оценки и задачи классификации многомерных нормальных совокупностей / / Теория вероятностей и ее применения. 1980. - No 2. - С. 381 - 389.

2. Айвазян С. А., Бухштабер В. М., Енюков И. С. и др. Классификация и снижение размерности М.: Финансы и статистика, 1989.- 607 с.

3. Айвазян С. А., Бежаева 3. И., Староверов О.В. Классификация многомерных наблюдений. М.: Статистика. 1974.- 240 с.

4. Андерсон Т. Введение в многомерный статистический анализ /Пер. с англ. М.: ГИФМЛ, 1963.- 500 с.

5. Использование хеширования по сигнатуре для поиска по сходству./ Бойцов Л.М.; ВМиК, МГУ М. 2001, Прикладная математика и информатика. No8 2001, сс. 135-154.

6. Р.Грэхем, Д.Кнут, О. Паташник, Конкретная математика. М. Мир 1998.

7. Дубров А. М. Обработка статистических данных методом главных компонент. М.: Статистика, 1978.- 130с.

8. Дубров A.M., Мхитарян B.C., Трошин Л.И. Многомерные статистические методы, М.: Финансы и статистика, 1998.

9. Д. Кнут, Искусство программирования, том 1, 3-е изд. М. Издательский дом «Вильяме», 2000

10. Д. Кнут, Искусство программирования, том 3, 3-е изд. М. Издательский дом «Вильяме», 2000

11. Конотопский В. Ю. Экспертно-статистический метод построения интегрального показателя экономической эффективности деятельности промышленного предприятия: Дис. . канд. экон. наук. М.: МГУ им. М. В. Ломоносова. 1986. -171 с.

12. Крылов Г.О., Агафонов В.П. Системный анализ исследования операций:Лекции.- М.:МИРЭА,1990-216с.

13. Левченков B.C., Гривко И.Л. Свойства самосогласованного выбора. ДАН 1992, т.321, N1.

14. Левченков B.C., Гривко И.Л. Нормативные свойства правила самосогласованного выбора. Автоматика и телемеханика, 1994, N5.

15. Э. Озкархан, Машины баз данных и управления базами данных, М. Мир 1989.

16. Терехина А. Ю. Анализ данных методами многомерного шкалирования. М.: Наука, 1986. - 168 с.

17. В. Феллер, Введение в теорию вероятностей, М. 1967.

18. И. Шабаев, Universe и jBase: «multivalued» СУБД. www.citforum.ru/seminars/cbd2002/010.shtml

19. Aiwzian S. A. Probabilistic Statistical Modelling of the Distributary Relations in Society // Private and Enlarged Consumption. - Ed. by L. Solari, Q. - N Du Pasquier North - Holland: Publishing Company Amsterdam - New York - Oxford.- 1976. P. 285-247.

20. Amihood Amir, Gary Benson, Martin Farach. Let Sleeping Files Lie: Pattern Matching in Z-Compressed Files Georgia Tech U. of Southern California DIM ACS October 20, 1993

21. Anderson T. W. Asymptotic theory for component analysis// Ann. Math. Statist.- 1963. Vol. 34. - P. 122-148.

22. Baeza-Yates R.A., G.H. Gonnet, A new approach to text searching, Proceedings of the 12th Annual ACM-SIGIR conference on Information Retrieval, Cambridge, MA (June 1989),pp. 168-175.

23. Baeza-Yates R.A, W. Cunto, U. Manber, and S. Wu. Proximity matching using fixed-quieris trees. In Combinatorial Pattern Matching, June 1994.

24. R. Baeza-Yates and G. Navarro, Block Addressing Indices for Approximate Text Retrieval, Journal of the American Society on Information Systems 51 (1), 69-82, Jan 2000.

25. A. Berman, A new data structure for fast approximate matching. Andrew Berman. 3/94.http://citeseer.nj.nec.com/berman94new.html)

26. Bryan T. Bartell,Latent Semantic Indexing is an Optimal Special Case of Multidimensional Scaling, 1992.http://citeseer.nj .nec.com/bartell921atent.html)

27. S. Brin, L. Page, The Anatomy of a Large-Scale Hypertextual Web Search Engine, Proc. 7th International World Wide Web Conference, 1998, and February 2001http://www7.scu.edu.au/programme/fullpapers/1921/coml921.htm)

28. E. W. Brown J. P. Callan, W. Bruce.

29. Fast Incremental Indexing for Full-Text Information Retrieval Proceedings of the 20th International Conference on Very Large Databases (VLDB)

30. E. W. Brown, "Execution Performance Issues in Full-text Information Retrieval," UMass Technical Report UM-CS-1995-081 (Ph.D. thesis), October, 1995ftp.cs.umass.edu / pub / techrept / techreport /1995/UM-CS-1995-081.ps

31. W.Burkhard, R.Keller, Some approaches to bestmatch file searching. CACM, 16(4):230-236, 1976

32. F. J. Burkowski. Surrogate subsets: A free space management strategy for the index of a text retrieval system. In Proc. 13th ACM/SIGIR Conference, pages 211-226, 1990.

33. Damashek. Method of retrieving documents that concern the same topic. Patent No. US5418951.

34. M Patent Server: http://www.patents.ibm.com)

35. U. Deppisch: S-Tree: A Dynamic Balanced Signature Index for Office Retrieval.1. SIGIR 1986: 77-87http://wwwl.acm.org/pubs/contents/proceedings/ir/253168/)

36. A. Ehrenfeucht, D. Haussler. A New Distance Metric on Strings Computable in Linear Time. Discrete Applied Mathematics, 20:191-203, 1988.

37. P. Elias, Universal codeword sets and representations of the integers. IEEE Trans, on Inf. Theory, IT-21: 194^203, 1975.

38. С. Faloutsos, D. Oard, Survery of Information Retrieval and Filtering Methods, University of Maryland.http://citeseer.nj.nec.com/faloutsos96survey.html)

39. M. Farach, M. Thorup. String Matching in Lempel-Ziv Compressed Strings Rutgers University University of Copenhagen.

40. P. Fenwick, Punctured Elias Codes for variable-length coding of the integers, Technical Report 137 ISSN 1173-3500 5 December 1996.http://www.firstpr.com.au/audiocomp/lossless/TechRepl37.pdf)

41. P. Ferragina. Dynamic Data Structures for String. Ph.D. Thesis: TD-3/97. (htt p: / / www.di. unipit .it/ferragin / ferragin .html)

42. A. F. Gelbukh, G. Sidorov: Zipf and Heaps Laws' Coefficients Depend on Language. CICLing 2001: pp 332-335.

43. T. R. Girill, Fuzzy Matching as a Retrieval-Enabling Technique for Digital Libraries.http://www.asis.org/midyear-96/girillpaper.html)

44. Girshik M. A. Principal components // J. Amer. Stat. Ass 1936. - Vol. 31- P. 519-528.

45. Charles L. A., C. Gordon, V. Cormak, C. Forbes, J. Burkowski, Fast Inverted Indexes with On-Line Update (1994)http://citeseer.nj.nec.com/clarke94fast.html)

46. Golomb S., 1996, Run-length encodings. IEEE transactions on information theory. IT-12, 3 (July), pp 399-401.

47. C. Gordon, V. Cormack, Dynamic Inverted Indexes for a Distributed Full-Text Retrieval System (1995)http://citeseer.nj.nec.com/clarke95dynamic.html)

48. Harrison M.C. (1971) "Implementation of the substring test by hashing," Communications of the ACM, Vol. 14, No. 12, p. 777-9, December 1971.

49. H. Heaps. Information Retrieval Computational and Theoretical Aspects. Academic Press, NY, 1978.

50. Joseph M. Hellerstein, Avi Pfeffer, THE RD-TREE: AN INDEX STRUCTURE FOR SETS.http://s2k-ftp.cs.berkeley.edu:8000/postgres/papers/UW-CS-TR-1252.pdf)

51. Norio Katayama, The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries.ht tp: //citeseer. nj. nec .com/68737. html)

52. Stefan Kurtz, Fundamental Alogorithms for declarative pattern matching. University Bielefeld, 1995, Ph.D Thesis (Report 95-03).

53. LUHN, H.P., A statistical approach to mechanised encoding and searching of library information, IBM Journal of Research and Development, 1, 309-317 (1957).

54. Manber U., A text compression scheme that allows fast searching directly in the compressed file, technical report 93-07, Department of Computer Science, University of Arizona (March 1993).ftp.cs.arizona.edu

55. U. Masek, M. S. Peterson. A faster algorithm for computing string-edit distances. Journal of Computer and System Sciences, 20(1), 785-807,1980.

56. E.W. Myers, An 0{W-D) differences algorithm. Algorithmica, 2(1), 251-266,1986.

57. E.W. Myers. An overview of sequence comparison algorithms in molecular biology. Technical report TR 91-29, University of Arizona, Tucson, Department of Computer Science, 1991.

58. E.W. Myers, Fast Bit-Vector Algorithm for Approximate String Matching Based on Dynamic Programming, Journal of the ACM Volume 46 , Issue 3 (1999) pp 395-415www.cs.arizona.edu/people/gene/PAPERS/bit .mat .ps

59. G. Navarro, E. Moura, M. Neubert, N. Ziviani and R. Baeza-Yates, Adding Compression to Block Addressing Inverted Indices. Information Retrieval, 3(1): 49-77, 2000.

60. Okamoto M. Optimality Principal Components Multivariate Analysis // Proc. 3 Int. Symp. Dayton. 1967.

61. Okamoto M., Kanazawa M. Minimization of Eigenvalues of a matrix and Optimality of principal components // Ann. Math. Statist. 1968. - Vol. 39. - N 3.

62. W. Rogers, G. Candela, D. Harman, Space and Time Improvements for Indexing in Information Retrieval (1995)http: / / citeseer.nj .nec.com / rogers95space.html)

63. Rao C. .R.The use and interpretation of principal components analysis in applied research , // Sankhya, A. 1964. - Vol. 26.- N 4. - P. 329-358.

64. Samraon J. W. A nonlinear mapping for Data Structure Analysis // IEEE Trans. Comput. 1969. - С - 18. - N 5. - p. 401-409.

65. H. Shang, Т.Н. Merret, Tries For Approximate String Matching. IEEE Transactions on Knowledge and Data Engineering, Vol. 8, No. 4, August 1996.

66. Shepard R. N. The analysis of proximites: multidimensional scaling with an unknown distance function // Psychometrika. 1962. - Vol. 27. - N 2-3.

67. Takane Y., Young F. W., de Leeuw J. Nonmetric individual differences multidimensional scaling: an alternative least squares method with optimal scaling features // Psychometrika. 1977. - Vol. 42. - N1.

68. Distributed Queries And Incremental Updates In Information Retrieval, Anthony Slavko Tomasic, A dissertation presented to the faculty of priceton University in candidacy for the degree of doctor of philosophy.http: / / citeseer.nj .nec.com/81351. html)

69. Torgerson IF. S. Multidimensional Scaling. Theory and Method// Psychometrika. 1952. - Vol. 17. - N 4.

70. The TELLTALE Dynamic Hypertext Environment: Approaches to scaleability. Claudia Pearce, Ethan Miller, Intelligent hypertext, 1997, 109-130

71. Porter M.F., An Algorithm For Suffix Stripping Program 14 (3), July 1980, pp. 130-137.

72. C.J. van Rjisbergen, Information Retrieval, London: Butterworths, 1979 (http://www.dcs.gla.ac.uk/ir/new/pages/IRPubli.html)

73. G. Salton and C. Buckley, Term-weighting approaches in automatic text retrieval, Information Processing and Management, 1988,volume 24,number 5,pages 513523.

74. P.H. Sellers, The Theory of Computation of Evolutionary Distances: Pattern recognition. Journal of Algorithms, 1:359-373, 1980.

75. E. Ukkonen, Algorithms for approximate string matching, 1985, Information and Control, 64, 100-118.

76. E. Ukkonen, Finding approximate patterns in strings, 0(k • n) time. Journal of Algorithms 1985, 6 , 132-137.

77. E. Ukkonen, Approximate String Matching with q-Grams and maximal matches. Theoretical Computer Science, 92(1), 191-211,1992.

78. E. Ukkonen, Approximate String Matching over Suffix-Trees. In ACGM93] pp. 229-242, 1993.

79. R.A. Wagner and M.J. Fisher, The String to String Correction Problem. Journal of the ACM, 21(1):168-173, 1974.

80. H. Williams and J. Zobel , Compressing integers for fast file access. Computer Journal, Volume 42, Issue 03, pp. 193-201,www3.oup.co.uk/computerjournal /hdb/Volume42/Issue03/420193.sgm.abs.html

81. Wu S. and U. Manber, Agrep A Fast Approximate Pattern-Matching Tool, Usenix Winter 1992 Technical Conference, San Francisco (January 1992), pp. 153162.ftp. cs. arizona. edu

82. Wong, Lee, "Implementation of Partial Document Ranking Using Inverted Files", Information Processing and Management , Vol. 29, No. 5, pp. 647-669, Oct. 1993.http://citeseer.nj.nec.com/3233.html)

83. Wu S., U. Manber, Fast Text Searching With Errors, Communications of the ACM 35 (October 1992) pp. 83-91.ftp .cs. arizona. edu

84. Wu S., U. Manber, GLIMPSE: A Tool to Search Through Entire File Systems, Winter USENIX Technical Conference, 1994.ftp.cs.arizona.edu

85. Young F. W. Null С. H. Multidimensional scaling of nominal data: the recovery of metric information with ALSCAL // Psychometrika. 1978: - Vol. 43. - N 3.

86. G.K. Zipf, The Psycho-Biology of Language (Boston, Mass.: Addison-Wesley, Houghton Mifflin, 1935)

87. G.K. Zipf, Human Behavior and the Principle of Least Effort (Reading, Mass.: Addison-Wesley, 1949)

88. N. Ziviani, E. Moura, G. Navarro, Ricardo Baeza-Yates, Compression: A Key for Next-Generation Text Retrieval Systems.http://cse.hanyang.ac.kr/ jmchoi/class/2001-l/ir/papers/Compression.pdf)

89. J. Zobel, A. Moffat, Ron Sacks-Davis: An Efficient Indexing Technique for Full Text Databases. 352-362,http://itlab.uta.edu/paperArchive/vldb8997/TOC/vldb92.html)

90. J. Zobel, A. Moffat, Ron Sacks-Davis: Searching Large Lexicons for Partially Specified Terms using Compressed Inverted Files. VLDB 1993: 290-301

91. Zobel J. Moffat, Adding compression to a full-text retrieval system. Software -Practice and Experience, 25, 891-903