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

• Published in: Кибернетика и системный анализ
• Date: 2019
• Main Author: Рачковский, Д.А.
• Format: Article
• Language: Russian
• Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2019
• Subjects: Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/181041
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Индексные структуры для быстрого поиска сходных символьных строк / Д.А. Рачковский // Кибернетика и системный анализ. — 2019. — Т. 55, № 5. — С. 180-202. — Бібліогр.: 80 назв. — рос.

Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных символьными строками. Рассмотрены индексные структуры как для точного, так и для приближенного поиска по расстоянию редактирования. Представлены индексные структуры на основе обратного индексирования, сохраняющего сходство хэширования, древовидных структур. Изложены идеи известных и предложенных в последнее время алгоритмов. Наведено огляд індексних структур для швидкого пошуку за схожістю об’єктів, що представлені бінарними символьными рядками. Розглянуто індексні структури як для точного, так і для наближеного пошуку за відстанню редагування. Описано індексні структури на основі зворотного індексування, гешування, що зберігає схожість, деревовидних структур. Викладено ідеї алгоритмів, відомих та нещодавно запропонованих. 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.