· Полнотекстовое сканирование
· Файлы сигнатур
· Инверсия
· Кластеризация
· Обработка естественного языка (NLP)
· Латентно-семантическое индексирование (LSI)
Полнотекстовое сканирование
· Заключается в поиске всех документов, содержащих искомую строку, представляющую собой последовательность символов.
· В случае запросов, содержащих булевское выражение из нескольких строк, требуется дополнительная проверка терминов, найденных при поиске строк, на соответствие булевскому выражению.
Простейший вариант алгоритма включается в себя шаги:
· Посимвольное сравнение искомой строки с соответствующими символами документа.
· В случае несовпадения выполняется сдвиг искомой строки относительно документа вправо на одну позицию
· Цикл повторяется до тех пор пока либо не будет найдена в какой-либо позиции документа искомая строка, либо не будет достигнут конец документа.
§ При всей простоте данный вариант алгоритма является очень медленным. Количество необходимых операций сравнения составляет O (m*n), где m – длина искомой строки, а n – размер документа (длина документа в символах).
Имеются также более быстрые алгоритмы, для которых требуется выполнить O(m+n) сравнений и дополнительно необходимо затратить O(m) операций на предобработку искомой строки.
Достоинства:
• Минимальные затраты памяти и легкость выполнения вставок и удалений
Недостатки:
• неудовлетворительное время отклика особенно при работе с большими массивами документов.
Однако может вполне эффективно работать на специализированном оборудовании или в сочетании с другими методами доступа (например с инверсией), ограничивающими область поиска.
Файлы сигнатур
Идея:
Все термины документа представляются в виде битовых последовательностей, полученных в резльтате применения хэш-функции к исходным строкам-терминам. Сигнатуры документов размещаются последовательно в отдельном файле – файле сигнатур.
Данный подход позволяет уменьшить исходный размер файла и ускорить поиск.
Вариант метода:
Файл сигнатур хранится в транспонированном виде, что позволяет сократить число операций чтения записей с диска.
Сигнатуры слов
• Путем применения применения хэш-функции к слову получается целое число в интервале от 1 до 16. После применения 3-х хэш-функций получается 3 числа, указывающие номера позиций в 16-битовом идентификаторе, которые будут установлены. Например, если для слова “сеть” были получены значения 2, 7, 13, то его сигнатура будет выглядеть как “0001000001000010”.
• При соответствующем подборе хэш-функций вероятность совпадения сигнатур у разных слов (коллизия) очень мала.
Сигнатуры документов
• Для построения сигнатуры документа используется суперпозиция сигнатур слов, входящих в документ, например логическая операция ИЛИ.
• Для проверки вхождения слова в документ сначала вычисляется сигнатура слова. Затем, если соответствующие биты в установлены в сигнатуре документа, то велика вероятность того, что документ содержит искомое слово.
Ложные совпадения
• Для сокращения вероятности ложного совпадения необходимо увеличивать разрядность сигнатуры.
• Эффективность увеличивается для многословных запросов (уменьшается вероятность ложных совпадений)
Файлы сигнатур
• Достоинства: простота реализации, легкость управления вставками, подходит для работы с большими коллекциями документов (легкость масштабирования), возможности для распараллеливания.
• Недостатки: увеличение времени реакции системы на запрос при большом размере файла.
Инверсия
• Идея: каждый документ представляется списком терминов, которые хранятся упорядоченными в алфавитном порядке в индексном файле. Для каждого термина в данном файле имеется указатель на список содержащих его документов.
• Для ускорения поиска при организации индексного файла используются B-деревья, хэширование и другие подходы.
Инвертированая индексная структура
• Состоит из 2-х частей:
o Словарь. Содержит множество всех индексируемых единиц в данной коллекции.
o Инвертированный файл. Совокупность списков, каждый элемент которого указывает на текст, содержащий индексируемую единицу, и соответствующую статистическую информацию.
• Можно представить себе как транспонированную матрицу “ документ-термин ”.
Инверсия
• Достоинства: относительная простота реализации, высокая скорость работы, поддержка работы с синонимами
• Недостатки: превышения размера инверсного файла над размером исходного (хотя возможно применения сжатия списков), сложность обновления и реорганизации индекса.
Кластеризация
• В основой методов кластеризации является кластерная гипотеза (C.J. van Rijsbergen), которая гласит:
• Тесно связанные между собой документы оказываются релевантными по отношению к тем же запросам.
• Кластеризация может быть использована для распределения документов в коллекции по классам (автоматической классификации), что позволяет повысить скорость поиска документов и точность ответа.
• Кроме того, кластеризация может использоваться для улучшения представления результатов поиска на основе приведенных ранее алгоритмов.
• Кластеризация включает в себя две процедуры: генерацию кластеров и поиск кластеров по запросу пользователя.
• Инвертированный список можно рассматривать как одну из форм кластеризации документов.
Поиск кластера
• Входной запрос представляется в виде t-мерного вектора и сравнивается с центроидами кластеров.
• Поиск продолжается в кластерах степень подобия для которых превысила заданный порог.
• Для вычисления степени подобия часто используется косинусная метрика.