Применение декомпозиции на основе подстрок при построении индексов для поиска по сходству

Abstract

Данная работа посвящена созданию обновляемого индекса для выполнения поиска по подмножеству регулярных выражений и сходству фрагментов текста. За основу взят индекс, использующий мультиграммы (подстроки переменной длины) в качестве индексируемых элементов. Разработаны алгоритмы, позволяющие эффективно изменять индекс при вставке и удалении данных. Также в работе рассматривается использование разреженных суффиксных деревьев для определения степени сходства документов — результатов поиска.

The given work considers creation of a changeable index for search on a subset of regular expressions and on similarity. For a basis we take an index using multigrams (strings of variable length) as indexed elements. We offer the algorithms allowing effectively to change an index at performance of an insert and removal of data. Also we show how to use sparse suffix trees for definition of similarity of search results.