Индексные структуры для быстрого поиска сходных символьных строк
Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных символьными строками. Рассмотрены индексные структуры как для точного, так и для приближенного поиска по расстоянию редактирования. Представлены индексные структуры на основе обратного индексирования, сохраняющего...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2019 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2019
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/181041 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Индексные структуры для быстрого поиска сходных символьных строк / Д.А. Рачковский // Кибернетика и системный анализ. — 2019. — Т. 55, № 5. — С. 180-202. — Бібліогр.: 80 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-181041 |
|---|---|
| record_format |
dspace |
| spelling |
Рачковский, Д.А. 2021-10-29T18:17:53Z 2021-10-29T18:17:53Z 2019 Индексные структуры для быстрого поиска сходных символьных строк / Д.А. Рачковский // Кибернетика и системный анализ. — 2019. — Т. 55, № 5. — С. 180-202. — Бібліогр.: 80 назв. — рос. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/181041 004.22+004.93'11 Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных символьными строками. Рассмотрены индексные структуры как для точного, так и для приближенного поиска по расстоянию редактирования. Представлены индексные структуры на основе обратного индексирования, сохраняющего сходство хэширования, древовидных структур. Изложены идеи известных и предложенных в последнее время алгоритмов. Наведено огляд індексних структур для швидкого пошуку за схожістю об’єктів, що представлені бінарними символьными рядками. Розглянуто індексні структури як для точного, так і для наближеного пошуку за відстанню редагування. Описано індексні структури на основі зворотного індексування, гешування, що зберігає схожість, деревовидних структур. Викладено ідеї алгоритмів, відомих та нещодавно запропонованих. 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. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу Индексные структуры для быстрого поиска сходных символьных строк Індексні структури для швидкого пошуку схожих символьних рядків Index structures for fast similarity search for symbolic strings Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Индексные структуры для быстрого поиска сходных символьных строк |
| spellingShingle |
Индексные структуры для быстрого поиска сходных символьных строк Рачковский, Д.А. Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу |
| title_short |
Индексные структуры для быстрого поиска сходных символьных строк |
| title_full |
Индексные структуры для быстрого поиска сходных символьных строк |
| title_fullStr |
Индексные структуры для быстрого поиска сходных символьных строк |
| title_full_unstemmed |
Индексные структуры для быстрого поиска сходных символьных строк |
| title_sort |
индексные структуры для быстрого поиска сходных символьных строк |
| author |
Рачковский, Д.А. |
| author_facet |
Рачковский, Д.А. |
| topic |
Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу |
| topic_facet |
Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу |
| publishDate |
2019 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Індексні структури для швидкого пошуку схожих символьних рядків Index structures for fast similarity search for symbolic strings |
| description |
Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных символьными строками. Рассмотрены индексные структуры как для точного, так и для приближенного поиска по расстоянию редактирования. Представлены индексные структуры на основе обратного индексирования, сохраняющего сходство хэширования, древовидных структур. Изложены идеи известных и предложенных в последнее время алгоритмов.
Наведено огляд індексних структур для швидкого пошуку за схожістю об’єктів, що представлені бінарними символьными рядками. Розглянуто індексні структури як для точного, так і для наближеного пошуку за відстанню редагування. Описано індексні структури на основі зворотного індексування, гешування, що зберігає схожість, деревовидних структур. Викладено ідеї алгоритмів, відомих та нещодавно запропонованих.
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.
|
| issn |
1019-5262 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/181041 |
| citation_txt |
Индексные структуры для быстрого поиска сходных символьных строк / Д.А. Рачковский // Кибернетика и системный анализ. — 2019. — Т. 55, № 5. — С. 180-202. — Бібліогр.: 80 назв. — рос. |
| work_keys_str_mv |
AT račkovskiida indeksnyestrukturydlâbystrogopoiskashodnyhsimvolʹnyhstrok AT račkovskiida índeksnístrukturidlâšvidkogopošukushožihsimvolʹnihrâdkív AT račkovskiida indexstructuresforfastsimilaritysearchforsymbolicstrings |
| first_indexed |
2025-11-28T08:08:12Z |
| last_indexed |
2025-11-28T08:08:12Z |
| _version_ |
1850853503314952192 |