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

Информатика, кибернетика и управление


Авторы

Сизиков Е. В.

Московский авиационный институт (национальный исследовательский университет), Волоколамское шоссе, 4, Москва, A-80, ГСП-3, 125993, Россия

e-mail: sizikov@mail.ru

Аннотация

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

mai.ru — информационный портал Московского авиационного института

© МАИ, 1994-2020