Синтез системы автоматической коррекции, индексации и поиска текстовой информации тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Бойцов, Леонид Моисеевич

• Бойцов, Леонид Моисеевич
• кандидат технических наук
• 2003

Оглавление диссертации кандидат технических наук Бойцов, Леонид Моисеевич

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

ВВЕДЕНИЕ

ГЛАВА 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 млн. документов, среднее время поиска равно примерно одной секунде, а полное время переиндексации коллекции - менее трех часов.

Список литературы диссертационного исследования кандидат технических наук Бойцов, Леонид Моисеевич, 2003 год

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