Индексные структуры для быстрого поиска сходных символьных строк

Abstract

Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных символьными строками. Рассмотрены индексные структуры как для точного, так и для приближенного поиска по расстоянию редактирования. Представлены индексные структуры на основе обратного индексирования, сохраняющего сходство хэширования, древовидных структур. Изложены идеи известных и предложенных в последнее время алгоритмов.

Наведено огляд індексних структур для швидкого пошуку за схожістю об’єктів, що представлені бінарними символьными рядками. Розглянуто індексні структури як для точного, так і для наближеного пошуку за відстанню редагування. Описано індексні структури на основі зворотного індексування, гешування, що зберігає схожість, деревовидних структур. Викладено ідеї алгоритмів, відомих та нещодавно запропонованих.

We survey index structures for fast similarity search of objects represented by symbolic strings. Index structures for both exact and approximate search by the edit distance are considered. Mainly, we present index structures based on inverted indexing, similarity-preserving hashing, tree structures. The ideas of specific algorithms, including the recently proposed ones, are outlined.