Введение
ГЛАВА 1. Сущность задачи построения системы автокоррекции, индексации и поиска. Постановка задачи исследования . 12
1.1 Проблема сравнения векторных показателей. Методы снижения размерности и построения интегральных критериев 12
1.2 Анализ существующих методов снижения размерности и построения интегральных критериев 13
1.2.1 Эвристические методы 13
1.2.2 Экспертные методы построения интегрального показателя 14
1.2.3 Экспертно-статистические методы построения интегрального показателя 14
1.2.4 Метод экстремальной группировки признаков 16
1.2.5 Многомерное шкалирование 17
1.2.6 Факторный анализ 18
1.2.7 Метод главных компонент 19
1.2.8 Прочие методы снижения размерности 21
1.3 Обзор исследований по проблеме информационного поиска и поиска по сходству 21
1.3.1 Сущность задачи информационного поиска 21
1.3.2 Необходимые определения 27
1.3.3 Сравнение алгоритмов организации индекса ИПС 30
1.3.3.1 Инвертированные файлы (ИФ) 32
1.3.3.2 Сигнатурные файлы (СФ) 32
1.3.3.3 Векторные модели (ВМ) 34
1.3.4 Сущность задачи текстового поиска по сходству 37
1.3.5 Обзор исследований по алгоритмам вычисления расстояния редактирования 39
1.3.6 Анализ методов словарного поиска по сходству 52
1.3.6.1 Методы п-грамм 52
1.3.6.2 Trie-деревья (лучи) 54
1.3.6.3 Метрические (триангуляционные) деревья 54
1.4 Постановка задачи и обоснование методов исследования 56
Выводы по Главе 1 58
ГЛАВА 2. Анализ хеширования по сигнатуре . 59
2.1 Анализов факторов, влияющие на скорость поиска по сходству . 59
2.2 Описание метода хеширования по сигнатуре ключевых слов (ХС) . 64
2.3 Оценки эффективности ХС 70
2.4 Решение задачи коррекции текстов с особенностями с применением обобщенного расстояния редактирования 84
Выводы по Главе 2 86
ГЛАВА 3. Синтез корректирующего модуля с использованием метода главных компонент . 88
3.1 Описание алгоритмов словарного поиска по сходству, использованных для тестирования 88
3.1.1 Trie-деревья или лучи 89
3.1.2 Метод п-грамм 91
3.1.3 Частотные trie-деревья 91
3.1.4 Метрические деревья 92
3.2 Адаптация метода главных компонент для сравнения методов словарного поиска по сходства 93
3.3 Анализ экспериментальных данных методом главных компонент . 97
Выводы по Главе 3 100
ГЛАВА 4. Реализация ИФ на базе реляционной СУБД . 101
4.1 Проблема реализации поискового модуля для персональной ЭВМ . 101
4.2 Оценки размера индекса при «наивном» кодировании 105
4.3 Оценки размера сжатого индекса для коллекций, подчиняющихся обобщенному закону Ципфа со степенной константой, превышающей единицу 109
4.4 Решение задачи создания поискового модуля для персональной ЭВМ с использоанием сжатых модифицируемых ИФ 112
4.4.1 Суть проблемы обновления ИФ 112
4.4.2 Условия экспериментов 115
4.4.3 Описание метода блочной адресации «в чистом виде» 116
4.4.4 Описание модификации метода блочной адресации N 1 117
4.4.5 Описание модификации метода блочной адресации N 2 122
4.4.6 Анализ результатов экспериментальной проверки модификации N 2 124
Выводы по Главе 4 128
