Эффективный полнотекстовый поиск и индексирование с использованием упакованного инвертированного сигнатурного файла и нечеткого объединения ключа

Авторы

Сизиков Е. В.

e-mail: sizikov@mail.ru

Аннотация

В работе рассмотрен набор алгоритмов и структур данных для индексирования и контекстного поиска в текстовых массивах. Особое внимание уделено решению проблемы эффективного поиска в массивах текстов с применением приближенного сравнения атомарных строковых образцов (сравнение строк, содержащих k ошибок). Этот метод обладает высокой производительностью при поисковых запросах, которые используют регулярные выражения с большим числом атомарных шаблонов. Для компактного хранения индексных данных предложен новый тип индексного файла — упакованный инвертированный сигнатурный файл. Высокая эффективность нестрогого поиска строковых образцов в словаре индекса достигается за счет использования разработанной автором динамической структуры данных — нечеткого объединения ключа. Данный индекс и алгоритмы работы с ним могут быть использованы в качестве ядра полнотекстовой поисковой системы нового поколения.