Индексные структуры для быстрого поиска сходных символьных строк
Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных символьными строками. Рассмотрены индексные структуры как для точного, так и для приближенного поиска по расстоянию редактирования. Представлены индексные структуры на основе обратного индексирования, сохраняющего...
Збережено в:
| Дата: | 2019 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2019
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/181041 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Индексные структуры для быстрого поиска сходных символьных строк / Д.А. Рачковский // Кибернетика и системный анализ. — 2019. — Т. 55, № 5. — С. 180-202. — Бібліогр.: 80 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-181041 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1810412021-10-30T01:26:19Z Индексные структуры для быстрого поиска сходных символьных строк Рачковский, Д.А. Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных символьными строками. Рассмотрены индексные структуры как для точного, так и для приближенного поиска по расстоянию редактирования. Представлены индексные структуры на основе обратного индексирования, сохраняющего сходство хэширования, древовидных структур. Изложены идеи известных и предложенных в последнее время алгоритмов. Наведено огляд індексних структур для швидкого пошуку за схожістю об’єктів, що представлені бінарними символьными рядками. Розглянуто індексні структури як для точного, так і для наближеного пошуку за відстанню редагування. Описано індексні структури на основі зворотного індексування, гешування, що зберігає схожість, деревовидних структур. Викладено ідеї алгоритмів, відомих та нещодавно запропонованих. 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. 2019 Article Индексные структуры для быстрого поиска сходных символьных строк / Д.А. Рачковский // Кибернетика и системный анализ. — 2019. — Т. 55, № 5. — С. 180-202. — Бібліогр.: 80 назв. — рос. 1019-5262 http://dspace.nbuv.gov.ua/handle/123456789/181041 004.22+004.93'11 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу |
| spellingShingle |
Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу Рачковский, Д.А. Индексные структуры для быстрого поиска сходных символьных строк Кибернетика и системный анализ |
| description |
Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных символьными строками. Рассмотрены индексные структуры как для точного, так и для приближенного поиска по расстоянию редактирования. Представлены индексные структуры на основе обратного индексирования, сохраняющего сходство хэширования, древовидных структур. Изложены идеи известных и предложенных в последнее время алгоритмов. |
| format |
Article |
| author |
Рачковский, Д.А. |
| author_facet |
Рачковский, Д.А. |
| author_sort |
Рачковский, Д.А. |
| title |
Индексные структуры для быстрого поиска сходных символьных строк |
| title_short |
Индексные структуры для быстрого поиска сходных символьных строк |
| title_full |
Индексные структуры для быстрого поиска сходных символьных строк |
| title_fullStr |
Индексные структуры для быстрого поиска сходных символьных строк |
| title_full_unstemmed |
Индексные структуры для быстрого поиска сходных символьных строк |
| title_sort |
индексные структуры для быстрого поиска сходных символьных строк |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2019 |
| topic_facet |
Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/181041 |
| citation_txt |
Индексные структуры для быстрого поиска сходных символьных строк / Д.А. Рачковский // Кибернетика и системный анализ. — 2019. — Т. 55, № 5. — С. 180-202. — Бібліогр.: 80 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT račkovskijda indeksnyestrukturydlâbystrogopoiskashodnyhsimvolʹnyhstrok |
| first_indexed |
2025-07-15T21:34:07Z |
| last_indexed |
2025-07-15T21:34:07Z |
| _version_ |
1837750288432234496 |
| fulltext |
Ä.À. ÐÀ×ÊÎÂÑÊÈÉ
ÓÄÊ 004.22+004.93'11 ÈÍÄÅÊÑÍÛÅ ÑÒÐÓÊÒÓÐÛ ÄËß ÁÛÑÒÐÎÃÎ
ÏÎÈÑÊÀ ÑÕÎÄÍÛÕ ÑÈÌÂÎËÜÍÛÕ ÑÒÐÎÊ
Àííîòàöèÿ. Äàí îáçîð èíäåêñíûõ ñòðóêòóð äëÿ áûñòðîãî ïîèñêà ïî ñõîäñòâó
îáúåêòîâ, ïðåäñòàâëåííûõ ñèìâîëüíûìè ñòðîêàìè. Ðàññìîòðåíû èíäåêñíûå
ñòðóêòóðû êàê äëÿ òî÷íîãî, òàê è äëÿ ïðèáëèæåííîãî ïîèñêà ïî ðàññòîÿíèþ
ðåäàêòèðîâàíèÿ. Ïðåäñòàâëåíû èíäåêñíûå ñòðóêòóðû íà îñíîâå îáðàòíîãî èí-
äåêñèðîâàíèÿ, ñîõðàíÿþùåãî ñõîäñòâî õýøèðîâàíèÿ, äðåâîâèäíûõ ñòðóêòóð.
Èçëîæåíû èäåè èçâåñòíûõ è ïðåäëîæåííûõ â ïîñëåäíåå âðåìÿ àëãîðèòìîâ.
Êëþ÷åâûå ñëîâà: ïîèñê ïî ñõîäñòâó, ðàññòîÿíèå ðåäàêòèðîâàíèÿ, áëèæàé-
øèé ñîñåä, áëèæíèé ñîñåä, èíäåêñíûå ñòðóêòóðû, îáðàòíîå èíäåêñèðîâàíèå,
n-ãðàììû, ëîêàëüíî-÷óâñòâèòåëüíîå õýøèðîâàíèå, äðåâîâèäíûå ñòðóêòóðû.
ÂÂÅÄÅÍÈÅ
Ïîèñê îáúåêòîâ áàçû, ñõîäíûõ ñ îáúåêòîì-çàïðîñîì ïî íåêîòîðîé ìåðå ðàñ-
ñòîÿíèÿ/ñõîäñòâà, íàçûâàþò ïîèñêîì ïî ñõîäñòâó. Îáúåêòû-çàïðîñû ìîãóò íå
ïðèíàäëåæàòü áàçå. Ìåðó ðàññòîÿíèÿ/ñõîäñòâà ìåæäó ïðåäñòàâëåíèÿìè îáúåê-
òîâ, ïî êîòîðîé âûïîëíÿåòñÿ ïîèñê, áóäåì ñ÷èòàòü çàäàííîé.
Âûïîëíåíèå çàïðîñîâ ïîèñêà ïî ñõîäñòâó (òèïû çàïðîñîâ ñì. â ïîäðàçä. 1.2, 1.3)
ëèíåéíûì (èëè ïîñëåäîâàòåëüíûì) ïîèñêîì çàêëþ÷àåòñÿ â âû÷èñëåíèè ðàññòîÿ-
íèé/ñõîäñòâ îáúåêòà-çàïðîñà äî âñåõ îáúåêòîâ áàçû è âîçâðàùåíèè îáúåêòîâ, óäîâëåò-
âîðÿþùèõ óñëîâèÿì çàïðîñà. Ïîýòîìó ñëîæíîñòü (âðåìÿ) âûïîëíåíèÿ çàïðîñà ïðî-
ïîðöèîíàëüíà N è âðåìåíè âû÷èñëåíèÿ ðàññòîÿíèÿ/ñõîäñòâà ìåæäó äâóìÿ îáúåêòàìè.
Òàêîé ïîèñê ÷àñòî îêàçûâàåòñÿ íåäîïóñòèìî ìåäëåííûì äëÿ áîëüøèõ áàç è îáúåêòîâ
ñî ñëîæíûìè ìíîãîêîìïîíåíòíûìè ïðåäñòàâëåíèÿìè, îñîáåííî äëÿ âû÷èñëèòåëüíî
ñëîæíîé ìåðû ðàññòîÿíèÿ/ñõîäñòâà.
Îäèí ïîäõîä ê óñêîðåíèþ ëèíåéíîãî ïîèñêà ïî ñõîäñòâó ñîñòîèò â òîì, ÷òî-
áû áûñòðî (õîòÿ è ïðèáëèæåííî) îöåíèòü âåëè÷èíû âñåõ ðàññòîÿíèé/ñõîäñòâ.
Äðóãîé ïîäõîä çàêëþ÷àåòñÿ â ïîñòðîåíèè ïî áàçå òàêîé ñòðóêòóðû äàííûõ (èí-
äåêñíîé ñòðóêòóðû, ÈÑ), èñïîëüçîâàíèå êîòîðîé ïðè âûïîëíåíèè çàïðîñà ïîèñêà
ïî ñõîäñòâó ïîçâîëèëî áû ñîêðàòèòü êîëè÷åñòâî âû÷èñëåíèé ñõîäñòâà îáúåê-
òà-çàïðîñà ñ äðóãèìè îáúåêòàìè ïî ñðàâíåíèþ ñ ëèíåéíûì ïîèñêîì (ò.å. îáåñïå-
÷èòü ïîèñê, ñóáëèíåéíûé îòíîñèòåëüíî N ). Îòìåòèì, ÷òî àëãîðèòìû îáîèõ ïîä-
õîäîâ çà÷àñòóþ óñêîðÿþò ïîèñê öåíîé ïîëó÷åíèÿ ðåçóëüòàòîâ, íå ïîëíîñòüþ ñî-
âïàäàþùèõ ñ ðåçóëüòàòàìè (òî÷íîãî) ëèíåéíîãî ïîèñêà ïî ñõîäñòâó (ò.å. öåíîé
ïðåâðàùåíèÿ ïîèñêà ïî ñõîäñòâó èç òî÷íîãî â ïðèáëèæåííûé).
Îáçîðû áûñòðîé îöåíêè ñõîäñòâà îáúåêòîâ ïî âåêòîðàì, â êîòîðûå îíè ïðåîá-
ðàçóþòñÿ, ïðèâåäåíû â [1, 2]. Îáçîð ÈÑ äëÿ áûñòðîãî ïîèñêà ïî ñõîäñòâó îáúåêòîâ,
äëÿ êîòîðûõ èçâåñòíû òîëüêî çíà÷åíèÿ ñõîäñòâ èëè ðàññòîÿíèé äî äðóãèõ îáúåêòîâ,
180 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5
© Ä.À. Ðà÷êîâñêèé, 2019
ïðåäñòàâëåí â [3]. ÈÑ äëÿ âåêòîðîâ ñ êîìïîíåíòàìè — áèíàðíûìè ÷èñëàìè — ðàñ-
ñìîòðåíû â [4], à ñ êîìïîíåíòàìè — âåùåñòâåííûìè ÷èñëàìè — â [5, 6].
 íàñòîÿùåé ðàáîòå ïðèâåäåí îáçîð ÈÑ äëÿ ïîèñêà ïî ñõîäñòâó ñòðîê,
ò.å. ïîñëåäîâàòåëüíîñòåé ñèìâîëîâ èç íåêîòîðîãî àëôàâèòà.  êà÷åñòâå ìåðû íå-
ñõîäñòâà ïðèìåíÿåòñÿ ðàññòîÿíèå ðåäàêòèðîâàíèÿ ñòðîê (ïîäðàçä. 1.1). Â îòëè-
÷èå îò [7–9] â äàííîé ñòàòüå ïðåäñòàâëåíû íåäàâíî ïîÿâèâøèåñÿ ÈÑ äëÿ ïîèñêà
ñòðîê, à òàêæå ÈÑ ñ òåîðåòè÷åñêèìè ãàðàíòèÿìè ñêîðîñòè ïîèñêà è îøèáêè ðå-
çóëüòàòîâ ïî ñðàâíåíèþ ñ òî÷íûì ïîèñêîì. Îñíîâíûå ïîíÿòèÿ ðàññìîòðåíû
â ðàçä. 1. Ñòðóêòóðà îáçîðà ïðèâåäåíà â ïîäðàçä. 1.8.
1. ÎÑÍÎÂÍÛÅ ÏÎÍßÒÈß
1.1. Ðàññòîÿíèÿ ìåæäó ñòðîêàìè è âåêòîðàìè. Äëÿ îöåíêè ñõîäñòâà ìåæäó
îáúåêòàìè ÷àñòî èñïîëüçóþò ðàññòîÿíèå, ò.å. íåñõîäñòâî. Áîëüøèì çíà÷åíèÿì
ñõîäñòâà ñîîòâåòñòâóþò ìàëûå çíà÷åíèÿ ðàññòîÿíèÿ. Ìíîãèå ðàññòîÿíèÿ ÿâëÿ-
þòñÿ ìåòðèêàìè, ò.å. ïîä÷èíÿþòñÿ ìåòðè÷åñêèì àêñèîìàì, òàêèì êàê íåðàâåí-
ñòâî òðåóãîëüíèêà è äð. [3].
Øèðîêî ðàñïðîñòðàíåíî ðàññòîÿíèå ðåäàêòèðîâàíèÿ ìåæäó ñòðîêàìè (îáîçíà-
÷èì åãî dist edit ), êîòîðîå îïðåäåëÿåòñÿ êàê ìèíèìàëüíàÿ ñóììàðíàÿ ñòîèìîñòü
ïîñëåäîâàòåëüíîñòè ýëåìåíòàðíûõ îïåðàöèé ðåäàêòèðîâàíèÿ ñèìâîëîâ ñòðîê,
ïðåîáðàçóþùåé îäíó ñòðîêó â äðóãóþ. Ýëåìåíòàðíûìè ÿâëÿþòñÿ îïåðàöèè óäà-
ëåíèÿ, âñòàâêè è çàìåíû ñèìâîëà. ×àñòî ïðèìåíÿþò âàðèàíò dist edit ñ îäèíàêîâîé
ñòîèìîñòüþ ýëåìåíòàðíûõ îïåðàöèé (ðàññòîÿíèå Ëåâåíøòåéíà), òîãäà èõ ñóì-
ìàðíàÿ ñòîèìîñòü ýêâèâàëåíòíà îáùåìó êîëè÷åñòâó îïåðàöèé ðåäàêòèðîâàíèÿ.
Ê ñòðîêàì îäèíàêîâîé äëèíû D (êîòîðûå ìîæíî ðàññìàòðèâàòü â êà÷åñòâå
âåêòîðîâ) ïðèìåíèìî ðàññòîÿíèå Õýììèíãà (dist Ham ), âû÷èñëÿåìîå êàê êîëè-
÷åñòâî íåñîâïàäàþùèõ ñèìâîëîâ ñòðîê (êîìïîíåíòîâ âåêòîðîâ) ñ îäèíàêîâûì
ïîðÿäêîâûì íîìåðîì. Â íàñòîÿùåì îáçîðå òàêæå èñïîëüçóåòñÿ ìàíõýòòåíñêîå
ðàññòîÿíèå ( )dist Man ìåæäó âåêòîðàìè a, b ðàçìåðíîñòè D ñ êîìïîíåíòàìè ai , bi :
| | | | | |
,
a b� � �
��1 1
a bi ii D
.
Ñëîæíîñòü âû÷èñëåíèÿ dist edit (ñ ïðèìåíåíèåì äèíàìè÷åñêîãî ïðîãðàììèðîâà-
íèÿ) ìåæäó ñòðîêàìè äëèíû D1, D2 êâàäðàòè÷íàÿ, ò.å. ñîñòàâëÿåò O D D( )1 2 , â îòëè-
÷èå îò ëèíåéíîé ñëîæíîñòè O D( ) âû÷èñëåíèÿ ìíîãèõ òèïîâ ðàññòîÿíèé ìåæäó âåê-
òîðàìè (dist Ham , dist Man è äð.). Áîëåå òîãî, â [10] ïîêàçàíî, ÷òî åñëè ñïðàâåäëèâà
strong exponential time hypothesis (SETH), òî dist edit íåâîçìîæíî âû÷èñëèòü çà âðåìÿ
O D( )2�� äëÿ ëþáîãî ôèêñèðîâàííîãî � � 0 (ò.å. çà «ñóùåñòâåííî ñóáêâàäðàòè÷íîå»
âðåìÿ). Ïîýòîìó äëÿ ñòðîê ñ dist edit îñîáåííî àêòóàëüíî óñêîðåíèå ïîèñêà ïî ñõîä-
ñòâó çà ñ÷åò îáåñïå÷åíèÿ ñóáëèíåéíîñòè ïîèñêà ñ ïîìîùüþ ÈÑ.
1.2. Çàïðîñû òî÷íîãî ïîèñêà ïî ñõîäñòâó. Äèàïàçîííûé çàïðîñ (îáîçíà÷èì
åãî rNN) âîçâðàùàåò îáúåêòû áàçû, ðàññòîÿíèÿ êîòîðûõ îò îáúåêòà-çàïðîñà (ïî
ìåðå ðàññòîÿíèÿ, çàäàííîé â çàïðîñå) íå ïðåâûøàþò ðàäèóñà çàïðîñà r. Ïðè íå-
êîòîðûõ r ðåçóëüòàòîì äèàïàçîííîãî çàïðîñà ìîæåò áûòü ïóñòîå ìíîæåñòâî îáú-
åêòîâ èëè âñå îáúåêòû êîíêðåòíîé áàçû (êîëè÷åñòâî occ îáúåêòîâ áàçû, êîòîðûå
ÿâëÿþòñÿ îòâåòîì íà çàïðîñ, ñîîòâåòñòâåííî ðàâíî 0 èëè N ).  ïîñëåäíåì ñëó÷àå
óñêîðåíèå âûïîëíåíèÿ çàïðîñà rNN ïî ñðàâíåíèþ ñ ëèíåéíûì ïîèñêîì íåâîç-
ìîæíî â ïðèíöèïå. Ëþáîé îáúåêò, ÿâëÿþùèéñÿ îòâåòîì íà äèàïàçîííûé çàïðîñ,
íàçûâàþò r-áëèæíèì ñîñåäîì. Çàïðîñ rNN1 âîçâðàùàåò r-áëèæíåãî ñîñåäà, åñëè
îí åñòü â áàçå.
Çàïðîñ áëèæàéøåãî ñîñåäà (îáîçíà÷èì åãî NN) âîçâðàùàåò îáúåêò áàçû,
áëèæàéøèé ê îáúåêòó-çàïðîñó. Îáîçíà÷èì kNN çàïðîñ k áëèæàéøèõ ñîñåäåé.
Çàïðîñ kNN (êàê òî÷íîãî, òàê è ïðèáëèæåííîãî ïîèñêà, ñì. ïîäðàçä. 1.3) ìîæíî
âûïîëíèòü ïîñëåäîâàòåëüíîñòüþ çàïðîñîâ rNN1 ñ ðàçëè÷íûìè ðàäèóñàìè, ÷òî
òðåáóåò ïîñòðîåíèÿ ÈÑ äëÿ ýòèõ ðàäèóñîâ [11]. ×òîáû èçáåæàòü óâåëè÷åíèÿ çà-
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5 181
òðàò ïàìÿòè, äëÿ ïîèñêà áëèæàéøåãî ñîñåäà ÷àñòî èñïîëüçóþò äðóãèå ÈÑ áåç
òåîðåòè÷åñêèõ ãàðàíòèé âðåìåíè ïîèñêà.
Ðåçóëüòàòû âûïîëíåíèÿ çàïðîñà all-pair similarity search (APSS), ò.å. ïîèñê
âñåõ ïàð îáúåêòîâ áàçû ñ dist � r (òàêæå íàçûâàåìûé çàäà÷åé similarity join), ìîæ-
íî ïîëó÷èòü, èñïîëüçóÿ â êà÷åñòâå îáúåêòîâ-çàïðîñîâ äëÿ rNN âñå îáúåêòû áàçû.
1.3. Ïðèáëèæåííûé ïîèñê ïî ñõîäñòâó è åãî çàïðîñû. Ê ñîæàëåíèþ, áûñ-
òðîå âûïîëíåíèå çàïðîñîâ òî÷íîãî ïîèñêà íå ãàðàíòèðóåòñÿ è íå íàáëþäàåòñÿ íà
ïðàêòèêå. Àíàëèç âñåõ èçâåñòíûõ àëãîðèòìîâ òî÷íîãî âûïîëíåíèÿ çàïðîñà NN
ñ ñóáëèíåéíûì îò N âðåìåíåì äëÿ îáúåêòîâ ñ âåêòîðíûìè ïðåäñòàâëåíèÿìè ïî-
êàçûâàåò, ÷òî çàòðàòû âðåìåíè èëè ïàìÿòè ðàñòóò ýêñïîíåíöèàëüíî îò ðàçìåð-
íîñòè âåêòîðîâ D [11]. Ñîãëàñíî ïðåäïîëîæåíèþ «ïðîêëÿòèÿ ðàçìåðíîñòè» [11]
òàêàÿ çàâèñèìîñòü íåèçáåæíà ïðè òî÷íîì ïîèñêå ïî ñõîäñòâó äëÿ äàííûõ õóäøå-
ãî ñëó÷àÿ (ò.å. äëÿ îáúåêòà-çàïðîñà è îáúåêòîâ áàçû, êîòîðûå äàþò íàèáîëüøåå
âðåìÿ âûïîëíåíèÿ çàïðîñà).  ñëó÷àå íåâåêòîðíûõ äàííûõ, ó êîòîðûõ D — âíóò-
ðåííÿÿ ðàçìåðíîñòü [3], òàêæå íàáëþäàåòñÿ ïðîêëÿòèå ðàçìåðíîñòè.
Çàïðîñû ïðèáëèæåííîãî ïîèñêà ïî ñõîäñòâó âîçâðàùàþò ðåçóëüòàòû, êîòî-
ðûå ìîãóò îòëè÷àòüñÿ îò ðåçóëüòàòîâ çàïðîñîâ òî÷íîãî ïîèñêà ïî ñõîäñòâó.
Ïðèáëèæåííûé ïîèñê ïî ñõîäñòâó âîñòðåáîâàí íà ïðàêòèêå, ïîñêîëüêó äëÿ ìíî-
ãèõ ïðèìåíåíèé äîñòàòî÷íî ïîëó÷àòü ïðèáëèæåííûå ðåçóëüòàòû, íî áûñòðî.
Ïðèâåäåì ðàñïðîñòðàíåííûå òèïû çàïðîñîâ ïðèáëèæåííîãî ïîèñêà ïî ñõîä-
ñòâó [12, 11].
Îáîçíà÷èì ( , )c � -rNN1 çàïðîñ âåðîÿòíîñòíîãî ñ-ïðèáëèæåííîãî r-áëèæíåãî
ñîñåäà (randomized c-approximate r-near neighbor). Îí ñ âåðîÿòíîñòüþ, íå ìåíüøåé
1� �, âîçâðàùàåò ëþáîé îáúåêò áàçû ñ ðàññòîÿíèåì îò îáúåêòà-çàïðîñà, íå ïðåâû-
øàþùèì cr (c �1), åñëè ñóùåñòâóåò îáúåêò áàçû ñ ðàññòîÿíèåì îò îáúåêòà-çàïðî-
ñà, íå á�ëüøèì r. Åñëè òàêîãî îáúåêòà íå ñóùåñòâóåò, òî âîçâðàùàåòñÿ îáúåêò
ñ ðàññòîÿíèåì, íå ïðåâûøàþùèì cr, èëè îòâåò «íåò».
Çàïðîñ c-ïðèáëèæåííîãî áëèæàéøåãî ñîñåäà (approximate nearest neighbor,
îáîçíà÷èì åãî c-NN) âîçâðàùàåò îáúåêò áàçû, ðàññòîÿíèå êîòîðîãî äî îáúåê-
òà-çàïðîñà íå áîëåå ÷åì â c �1 ðàç ïðåâûøàåò ðàññòîÿíèå äî òî÷íîãî áëèæàéøåãî
ñîñåäà. Âåðîÿòíîñòíûé âàðèàíò òàêîãî çàïðîñà îáîçíà÷èì ( , )c � -NN.
1.4. Ìåðû êà÷åñòâà ïîèñêà ïî ñõîäñòâó. Äëÿ àëãîðèòìîâ ïðèáëèæåííîãî ïî-
èñêà ñ êîëè÷åñòâåííûìè ãàðàíòèÿìè êà÷åñòâà ðåçóëüòàòîâ ðàññìàòðèâàþò äâà òèïà
îòëè÷èé èõ ðåçóëüòàòîâ îò ðåçóëüòàòîâ òî÷íîãî ïîèñêà.  ñëó÷àå äåòåðìèíèðîâàí-
íûõ ïðèáëèæåííûõ àëãîðèòìîâ ðàññòîÿíèå äî íàéäåííûõ îáúåêòîâ íå áîëåå ÷åì íà
çàäàííûé ìíîæèòåëü ïðåâûøàåò ðàññòîÿíèå äî îáúåêòîâ, êîòîðûå ÿâëÿþòñÿ òî÷íûì
îòâåòîì íà çàïðîñ.  ñëó÷àå ðàíäîìèçèðîâàííûõ àëãîðèòìîâ (òî÷íûõ èëè ïðèáëè-
æåííûõ) äëÿ ïîèñêà ïî ñõîäñòâó äîïóñêàþòñÿ false negatives (ò.å. àëãîðèòì ìîæåò íå
âîçâðàòèòü îáúåêòû, êîòîðûå ÿâëÿþòñÿ îòâåòîì íà çàïðîñ). Âåðîÿòíîñòíûå ïðèáëè-
æåííûå çàïðîñû (ñì. ïîäðàçä. 1.3) ìîãóò èìåòü îáà îòëè÷èÿ. Ðàíäîìèçèðîâàííûå
àëãîðèòìû Las Vegas è Monte Carlo ðàññìîòðåíû â îáçîðå [5].
Íà ïðàêòèêå ïîëüçîâàòåëåé ÷àñòî èíòåðåñóþò íå àñèìïòîòè÷åñêàÿ âû÷èñëè-
òåëüíàÿ ñëîæíîñòü àëãîðèòìîâ (èëè ÈÑ) è èõ òåîðåòè÷åñêèå ãàðàíòèè êà÷åñòâà,
à âðåìÿ âûïîëíåíèÿ çàïðîñîâ è êà÷åñòâî ðåçóëüòàòîâ â ýêñïåðèìåíòàõ íà êîíêðåò-
íûõ áàçàõ. Äëÿ òî÷íîãî ïîèñêà ëó÷øåé ÿâëÿåòñÿ ÈÑ, îáåñïå÷èâàþùàÿ íàèìåíüøèå
çàòðàòû âðåìåíè. Äëÿ ïðèáëèæåííîãî ïîèñêà âûáîð ïàðàìåòðîâ ÈÑ îáû÷íî ïî-
çâîëÿåò äîñòè÷ü íåêîòîðîãî êîìïðîìèññà ìåæäó êà÷åñòâîì ðåçóëüòàòîâ ïîèñêà
(ñòåïåíüþ èõ îòëè÷èÿ îò ðåçóëüòàòîâ òî÷íîãî ïîèñêà) è âðåìåíåì ïîèñêà. Ïîýòîìó
ÈÑ äëÿ ïðèáëèæåííîãî ïîèñêà ñðàâíèâàþò ïî (óñðåäíåííîìó) âðåìåíè âûïîëíå-
íèÿ çàïðîñà ïðè ôèêñèðîâàííîì êà÷åñòâå ïîèñêà èëè ïî çíà÷åíèþ ìåðû êà÷åñòâà
ïîèñêà ïðè îäèíàêîâîì âðåìåíè ïîèñêà. Âàæíîé õàðàêòåðèñòèêîé òàêæå ÿâëÿþòñÿ
çàòðàòû ïàìÿòè ÈÑ (çàòðàòû, êâàäðàòè÷íûå îò N , íåïðèåìëåìû).
182 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5
×àñòî ïðèìåíÿþò ìåðû êà÷åñòâà âûïîëíåíèÿ êîíêðåòíîãî çàïðîñà, èçâåñ-
òíûå (ñì. ññûëêè â [3–5]) êàê ïîëíîòà (recall), ðàâíàÿ n n1 2/ , è òî÷íîñòü
(precision), ðàâíàÿ n n1 3/ , ãäå n1 — êîëè÷åñòâî âîçâðàùåííûõ îáúåêòîâ, ñîâïàâ-
øèõ ñ ðåëåâàíòíûìè çàïðîñó îáúåêòàìè â áàçå, n2 — êîëè÷åñòâî ðåëåâàíòíûõ
çàïðîñó îáúåêòîâ â áàçå, n3 — êîëè÷åñòâî âîçâðàùåííûõ îáúåêòîâ áàçû. Äëÿ çà-
ïðîñà kNN n n k2 3� � , ïîýòîìó òî÷íîñòü ðàâíà ïîëíîòå.
 êà÷åñòâå ðåëåâàíòíûõ îáúåêòîâ äëÿ ïðèáëèæåííîãî ïîèñêà ìîæíî èñïîëü-
çîâàòü îáúåêòû, âîçâðàùàåìûå çàïðîñàìè òî÷íîãî ïîèñêà. Ðåçóëüòàòû âûïîëíå-
íèÿ çàïðîñîâ òî÷íîãî èëè ïðèáëèæåííîãî ïîèñêà ìîæíî òàêæå ñðàâíèâàòü ñ ðå-
çóëüòàòàìè, óêàçàííûìè ýêñïåðòîì â êà÷åñòâå ýòàëîííûõ.
Ïðè âûïîëíåíèè ìíîæåñòâà çàïðîñîâ ïîëó÷åííûå äëÿ èíäèâèäóàëüíûõ çà-
ïðîñîâ çíà÷åíèÿ ìåð êà÷åñòâà óñðåäíÿþò. Òàê, äëÿ çàïðîñà NN ïîëíîòó (ðàâíóþ
òî÷íîñòè) èçìåðÿþò êàê ïðîöåíò çàïðîñîâ, äëÿ êîòîðûõ áûë âîçâðàùåí
ýòàëîííûé áëèæàéøèé ñîñåä [3–5].
1.5. Ñòðàòåãèÿ ôèëüòðàöèè è óòî÷íåíèÿ. Äëÿ óñêîðåíèÿ ïîèñêà ïî áàçå
ñòðîÿò ÈÑ è çàòåì èñïîëüçóþò åå ïðè âûïîëíåíèè çàïðîñîâ. Âî ìíîãèõ ÈÑ ïðè
âûïîëíåíèè çàïðîñà ïðèìåíÿþò ïðîöåäóðû, êîòîðûå ìîæíî ñ÷èòàòü âàðèàíòàìè
äâóõýòàïíîé ñòðàòåãèè ôèëüòðàöèè è óòî÷íåíèÿ F&R. Íà ïåðâîì ýòàïå îñóùå-
ñòâëÿåòñÿ áûñòðûé îòáîð îáúåêòîâ-êàíäèäàòîâ. Ðåçóëüòàòû ïåðâîãî ýòàïà óòî÷-
íÿþòñÿ íà âòîðîì ýòàïå (îáû÷íî ñ èñïîëüçîâàíèåì ëèíåéíîãî ïîèñêà ñðåäè îáú-
åêòîâ-êàíäèäàòîâ ïî ìåðå ðàññòîÿíèÿ/ñõîäñòâà, çàäàííîé â çàïðîñå). Ñòðàòåãèþ
F&R èíîãäà ïðèìåíÿþò ìíîãîêðàòíî ïðè âûïîëíåíèè îäíîãî çàïðîñà äëÿ ðàç-
ëè÷íûõ ïîäìíîæåñòâ îáúåêòîâ áàçû è/èëè òèïîâ ôèëüòðîâ.
Îòìåòèì, ÷òî äëÿ çàïðîñà rNN âòîðîé ýòàï óñòðàíÿåò false positives (îáúåê-
òû-êàíäèäàòû, íå ÿâëÿþùèåñÿ îòâåòîì íà çàïðîñ). Åñëè ñóììàðíîå êîëè÷åñòâî
îáúåêòîâ-êàíäèäàòîâ ìåíüøå N è èõ îòáîð âûïîëíÿåòñÿ äîñòàòî÷íî áûñòðî,
ìîæíî ïîëó÷èòü óñêîðåíèå âûïîëíåíèÿ çàïðîñà îòíîñèòåëüíî ëèíåéíîãî ïîèñêà.
Äëÿ òî÷íîãî ïîèñêà ïðè âûïîëíåíèè çàïðîñà êàíäèäàòû âûáèðàþòñÿ òàê, ÷òî
îíè ãàðàíòèðîâàííî ñîäåðæàò îòâåò íà çàïðîñ.
1.6. Èçâëå÷åíèå ïðèçíàêîâ è âëîæåíèÿ â âåêòîðíûå ïðîñòðàíñòâà. Íà
ýòàïå ôèëüòðàöèè ýôôåêòèâíîå èñêëþ÷åíèå (èëè îòáîð) êàíäèäàòîâ ÷àñòî âû-
ïîëíÿþò íà îñíîâå ïðèçíàêîâ, âûäåëåííûõ èç èñõîäíûõ ïðåäñòàâëåíèé. Òàê,
ïðåäñòàâëåíèÿ îáúåêòîâ äåëÿò íà ïåðåñåêàþùèåñÿ èëè íåïåðåñåêàþùèåñÿ ÷àñòè,
à ïðèçíàêîì ÿâëÿåòñÿ èíäèêàòîð íàëè÷èÿ è îòñóòñòâèÿ â äàííîé ÷àñòè îïðåäå-
ëåííûõ ýëåìåíòîâ èñõîäíîãî ïðåäñòàâëåíèÿ.
Íàëè÷èå ó äâóõ îáúåêòîâ íåêîòîðîãî êîëè÷åñòâà ñîâïàäàþùèõ ïðèçíàêîâ
ñâÿçûâàþò ñ âåëè÷èíîé íåêîòîðîé ìåðû ñõîäñòâà ìåæäó èñõîäíûìè ïðåäñòàâëå-
íèÿìè ýòèõ îáúåêòîâ, ïî êîòîðîé âûïîëíÿåòñÿ ïîèñê ïî ñõîäñòâó. Ïðè âûïîëíå-
íèè çàïðîñà áûñòðî íàõîäÿò îáúåêòû-êàíäèäàòû èç áàçû, ñîäåðæàùèå òðåáóåìîå
êîëè÷åñòâî ïðèçíàêîâ, ñîâïàäàþùèõ ñ ïðèçíàêàìè îáúåêòà-çàïðîñà. Äëÿ ýòîãî
èñïîëüçóþò ÈÑ íà îñíîâå îáðàòíîãî èíäåêñèðîâàíèÿ (ïîäðàçä. 1.7).
Èçâëå÷åíèå ïðèçíàêîâ èç èñõîäíûõ ïðåäñòàâëåíèé îáúåêòîâ ìîæíî ðàññìàò-
ðèâàòü êàê ôîðìèðîâàíèå âåêòîðîâ ñ êîìïîíåíòàìè, ñîîòâåòñòâóþùèìè ïðèçíà-
êàì. Ìåðû ðàññòîÿíèÿ/ñõîäñòâà ìåæäó ïîëó÷åííûìè âåêòîðàìè ïðèçíàêîâ îáû÷-
íî âû÷èñëÿþòñÿ çíà÷èòåëüíî ïðîùå, ÷åì ìåðû ñõîäñòâà èñõîäíûõ ïðåäñòàâëå-
íèé. Ïîýòîìó ïðèìåíåíèå âåêòîðîâ ïðèçíàêîâ ïîçâîëÿåò â ðÿäå ñëó÷àåâ áûñòðî
ïîëó÷àòü ãðàíèöû èñõîäíûõ çíà÷åíèé ðàññòîÿíèé è âûáèðàòü ïî íèì îáúåê-
òû-êàíäèäàòû íà ïåðâîì ýòàïå ôèëüòðàöèè â ñòðàòåãèè F&R. Äðóãîé ñâÿçàííûé
ïîäõîä — âëîæåíèå â âåêòîðíîå ïðîñòðàíñòâî, ò.å. ïðåîáðàçîâàíèå èñõîäíûõ
ïðåäñòàâëåíèé îáúåêòîâ â òàêèå âåêòîðû, ðàññòîÿíèå ìåæäó êîòîðûìè àïïðîêñè-
ìèðóåò èñõîäíîå ñ íåêîòîðûì èñêàæåíèåì [1, 2]. Äëÿ ïîèñêà ïî ñõîäñòâó
âîñòðåáîâàíû çàáûâ÷èâûå âëîæåíèÿ, ò.å. ïîçâîëÿþùèå ïðåîáðàçîâûâàòü
îáúåêòû-çàïðîñû íå èç áàçû áåç èçìåíåíèÿ ïðåäñòàâëåíèé äðóãèõ îáúåêòîâ.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5 183
Äëÿ îáúåêòîâ ñ çàäàííûì òèïîì ïðåäñòàâëåíèÿ è ìåðîé ñõîäñòâà ïðèìåíÿþò
ñïåöèàëèçàöèè ýòîãî ïîäõîäà — â äàííîì îáçîðå äëÿ èñõîäíûõ ñòðîê ñ dist edit
è äëÿ ïîëó÷àåìûõ âåùåñòâåííûõ è áèíàðíûõ âåêòîðîâ â îñíîâíîì ñ dist Man . Äëÿ
ñòðîê â êà÷åñòâå ïðèçíàêîâ èñïîëüçóþò, íàïðèìåð n-ãðàììû, ò.å. ïîñëåäîâàòåëü-
íîñòè n ñìåæíûõ ñèìâîëîâ, à â êà÷åñòâå êîìïîíåíòîâ âåêòîðà âëîæåíèÿ —
÷àñòîòó âñòðå÷àåìîñòè n-ãðàìì.
1.7. Èíäåêñíûå ñòðóêòóðû è îáðàòíîå èíäåêñèðîâàíèå. Ìíîãèå ÈÑ ïðè
êîíñòðóèðîâàíèè ðàçáèâàþò ìíîæåñòâî îáúåêòîâ áàçû íà ïîäìíîæåñòâà òàê,
÷òîáû ïðè âûïîëíåíèè çàïðîñà ðàññìàòðèâàòü íå âñå, à òîëüêî ÷àñòü ïîäìíî-
æåñòâ, è òàêèì îáðàçîì óñêîðÿþò âðåìÿ âûïîëíåíèÿ çàïðîñà îòíîñèòåëüíî ëè-
íåéíîãî ïîèñêà [3–6]. ÈÑ íà îñíîâå õýøèðîâàíèÿ, äåðåâüåâ, ãðàôîâ ñîñåäñòâà
è äð. ðàññìîòðåíû â [3–6] â îñíîâíîì äëÿ âåêòîðíûõ ïðåäñòàâëåíèé îáúåê-
òîâ [4–6], à òàêæå äëÿ îáúåêòîâ, ó êîòîðûõ èçâåñòíû âåëè÷èíû ðàññòîÿíèé ìåæ-
äó íèìè, íî íå èõ ïðåäñòàâëåíèÿ [6].
Äëÿ áûñòðîé ôèëüòðàöèè íà îñíîâå ñîâïàäåíèÿ ïðèçíàêîâ îáúåêòîâ (ñì. ïîä-
ðàçä. 1.6) ïðèìåíÿþò ÈÑ äëÿ ïîèñêà ïî ìåðàì ñõîäñòâà ìíîæåñòâ [13, 4, 14]. Ðàñ-
ïðîñòðàíåíû ÈÑ íà îñíîâå îáðàòíûõ ñïèñêîâ è îáðàòíîãî èíäåêñèðîâàíèÿ [4].
 íèõ äëÿ êàæäîãî ïðèçíàêà çàïîìèíàþò îáúåêòû áàçû, â êîòîðûõ èìååòñÿ ýòîò
ïðèçíàê, è ÷àñòîòó åãî âñòðå÷àåìîñòè â êàæäîì îáúåêòå. Ïðè âûïîëíåíèè çàïðî-
ñà îáðàáàòûâàþò òîëüêî ïðèçíàêè, èìåþùèåñÿ â îáúåêòå-çàïðîñå. Åñëè êîëè÷åñ-
òâî ïîñåùåííûõ îáúåêòîâ ìåíüøå N , ïîëó÷àþò ñóáëèíåéíîå âðåìÿ ïîèñêà
(ëèøü ýòè îáúåêòû ïîäëåæàò ðàíæèðîâàíèþ). Ïîýòîìó îáðàòíûé èíäåêñ îñîáåí-
íî ýôôåêòèâåí äëÿ âåêòîðîâ ñ ìàëûì êîëè÷åñòâîì íåíóëåâûõ êîìïîíåíòîâ ïðè
ìàëîì êîëè÷åñòâå ïîñåùåííûõ îáúåêòîâ. Îäíàêî â õóäøåì ñëó÷àå ñóáëèíåéíîå
âðåìÿ ïîèñêà íå ãàðàíòèðóåòñÿ.
×àñòî â ÈÑ ïîñëåäîâàòåëüíî èñïîëüçóþò íåñêîëüêî ôèëüòðîâ ñ ðàçëè÷íîé
âû÷èñëèòåëüíîé ñëîæíîñòüþ è ýôôåêòèâíîñòüþ èñêëþ÷åíèÿ, ÷òî ñîêðàùàåò
êîëè÷åñòâî êàíäèäàòîâ.
Êàê óïîìèíàëîñü â ïîäðàçä. 1.3, ÈÑ äëÿ òî÷íîãî ïîèñêà ñ ãàðàíòèÿìè áûñ-
òðîãî ïîèñêà â õóäøåì ñëó÷àå òðåáóþò î÷åíü áîëüøèõ çàòðàò ïàìÿòè. Ïîýòîìó
èõ ìîæíî ïðàêòè÷åñêè ðåàëèçîâàòü òîëüêî äëÿ ÷àñòíûõ ñëó÷àåâ îáúåêòîâ ñ ìà-
ëûì êîëè÷åñòâîì ýëåìåíòîâ ïðåäñòàâëåíèÿ è/èëè ñ ìàëûì ðàäèóñîì çàïðîñà.
Ïðàêòè÷åñêèå ÈÑ äëÿ òî÷íîãî ïîèñêà èñïîëüçóþò ýâðèñòèêè è íå ãàðàíòèðóþò
ñóáëèíåéíîãî âðåìåíè ïîèñêà â õóäøåì ñëó÷àå.
Äëÿ ïðèáëèæåííîãî ïîèñêà ñòðîê ïî dist edit ñ ñóáëèíåéíûì âðåìåíåì â õóä-
øåì ñëó÷àå ïðåäëîæåíû ÈÑ íà îñíîâå âëîæåíèé (ïîäðàçä. 3.2, 5.1). Îíè èñïîëü-
çóþò âëîæåíèÿ ñòðîê â âåêòîðíûå ïðîñòðàíñòâà ñ dist Man , dist Ham è ìåòðèêàìè
ïðîèçâåäåíèÿ (product metrics). Çàòåì ïðèìåíÿþò ÈÑ, ñïåöèàëèçèðîâàííûå äëÿ
ïîèñêà ïî ïîëó÷åííûì âåêòîðàì. Ðåçóëüòàò ïîèñêà îáúåêòîâ-âåêòîðîâ äàåò ñîîò-
âåòñòâóþùèå èì îáúåêòû-ñòðîêè â êà÷åñòâå êàíäèäàòîâ. Ýòî â îñíîâíîì «òåîðå-
òè÷åñêèå» ÈÑ (ò.å. áåç èçâåñòíûõ ïðàêòè÷åñêèõ ðåàëèçàöèé), íî íåêîòîðûå èç
íèõ ÿâëÿþòñÿ «ïðàêòè÷åñêèìè» (ò.å. èõ ìîæíî ðåàëèçîâàòü, íàïðèìåð, ÈÑ íà
îñíîâå LSH èç ïîäðàçä. 3.2).
1.8. Ñòðóêòóðà îáçîðà. Âîñòðåáîâàííîé â ïðèìåíåíèÿõ (è áûñòðîé) ðàçíî-
âèäíîñòüþ ïîèñêà ïî dist edit ÿâëÿåòñÿ âûïîëíåíèå òî÷íîãî çàïðîñà rNN ñ ðàäèó-
ñîì r �1 (ðàçä. 2). ÈÑ ñ òåîðåòè÷åñêèìè ãàðàíòèÿìè ñóáëèíåéíîãî ïîèñêà äëÿ
äàííûõ õóäøåãî ñëó÷àÿ (ïîäðàçä. 2.1) èñïîëüçóþò èäåè, àíàëîãè÷íûå òåîðåòè-
÷åñêèì ÈÑ äëÿ ïîèñêà ïî dist Ham ñ r �1 [4]. Ïðàêòè÷åñêèå ÈÑ (ïîäðàçä. 2.2) òàê-
æå îñíîâàíû íà ýòèõ èäåÿõ, íî äîïîëíèòåëüíî ïðèìåíÿþò ýâðèñòèêè, ÷òî ïðèâî-
äèò ê ïîòåðå òåîðåòè÷åñêèõ ãàðàíòèé.
ÈÑ äëÿ âûïîëíåíèÿ çàïðîñà rNN ñ r �1 ðàññìîòðåíû â ðàçä. 3 è 4. ÈÑ äëÿ
òî÷íîãî ïîèñêà ñ r �1 è ñ òåîðåòè÷åñêèìè ãàðàíòèÿìè äëÿ äàííûõ õóäøåãî ñëó-
÷àÿ, îñíîâàííûå íà k-errata tree (ïîäðàçä. 3.1), èìåþò ýêñïîíåíöèàëüíûå îò r çà-
184 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5
òðàòû ïàìÿòè è/èëè âðåìÿ âûïîëíåíèÿ çàïðîñà. ÈÑ íà îñíîâå ëîêàëüíî-÷óâñòâè-
òåëüíîãî õýøèðîâàíèÿ ñ ãàðàíòèåé ñóáëèíåéíîãî îò N âðåìåíè (ïîäðàçä. 3.2) èñ-
ïîëüçóþò âëîæåíèÿ ñòðîê â âåêòîðû ñ ðàçëè÷íûìè ðàññòîÿíèÿìè è ïðèìåíÿþò
ÈÑ LSH äëÿ áûñòðîãî ïîèñêà âåêòîðîâ.
Ïðàêòè÷åñêèå ÈÑ äëÿ âûïîëíåíèÿ òî÷íîãî çàïðîñà rNN (ðàçä. 4) âêëþ÷àþò
ýâðèñòèêè è íå îáåñïå÷èâàþò ãàðàíòèé ñóáëèíåéíîãî âðåìåíè ïîèñêà. Îíè ïðè-
ìåíÿþò ïîäõîäû äëÿ òî÷íîãî ïîèñêà ïî ìåðàì ñõîäñòâà ìíîæåñòâ. Ýëåìåíòàìè
ìíîæåñòâà (ïðèçíàêàìè, èçâëå÷åííûìè èç ñòðîêè) ÷àñòî ÿâëÿþòñÿ n-ãðàììû.
 ðàçä. 5 ðàññìîòðåíû ÈÑ ðàçëè÷íûõ òèïîâ äëÿ âûïîëíåíèÿ çàïðîñîâ áëè-
æàéøåãî ñîñåäà ïî dist edit : çàïðîñà ( , )c � -NN c òåîðåòè÷åñêèìè ãàðàíòèÿìè, íî
áåç ïðàêòè÷åñêîé ðåàëèçàöèè, íà îñíîâå âëîæåíèÿ ñòðîê â âåêòîðû ñ ðàçëè÷íûìè
ðàññòîÿíèÿìè è ïðàêòè÷åñêèå ÈÑ äëÿ âûïîëíåíèÿ çàïðîñîâ kNN, íî áåç
òåîðåòè÷åñêèõ ãàðàíòèé.
2. ÒÎ×ÍÛÉ ÏÎÈÑÊ Ñ ÅÄÈÍÈ×ÍÛÌ ÐÀÄÈÓÑÎÌ ÇÀÏÐÎÑÀ
Ïîèñê ïî dist edit ñòðîê ñ åäèíè÷íûì ðàäèóñîì çàïðîñà ïðèìåíÿåòñÿ [15, 16] äëÿ
ïðîâåðêè è êîððåêöèè ïðàâîïèñàíèÿ (íàïðèìåð, ïîèñêîâûõ çàïðîñîâ), ïðîâåðêè
ïàðîëåé íà íàäåæíîñòü è êàê ýòàï ðåøåíèÿ çàäà÷è ïîèñêà ñ á�ëüøèì ðàäèóñîì
(ðàçä. 3, 4) è äð.
2.1. Ïîèñê ñ òåîðåòè÷åñêèìè ãàðàíòèÿìè. Íåêîòîðûå àëãîðèòìû äëÿ òî÷-
íîãî ïîèñêà áèíàðíûõ âåêòîðîâ ïî dist Ham èç [4, ïîäðàçä. 2.1.1] ìîæíî èñïîëü-
çîâàòü äëÿ áîëåå îáùåé çàäà÷è ïîèñêà ñòðîê ñ íåáèíàðíûìè ñèìâîëàìè àëôàâèòà
ïî dist edit . Àëãîðèòìû ñ òåîðåòè÷åñêèìè ãàðàíòèÿìè, ïðåäëîæåííûå â [17–19],
ðàçðàáîòàíû íåïîñðåäñòâåííî äëÿ dist edit , íî ìîãóò ðåøàòü çàäà÷ó ïîèñêà è äëÿ
áèíàðíûõ âåêòîðîâ ñ dist Ham .
ÈÑ [17] íà îñíîâå ñî÷åòàíèÿ ïðåôèêñíûõ äåðåâüåâ (ïîäðàçä. 4.5), ìèíèìàëüíûõ
èäåàëüíûõ õýø-ôóíêöèé (ò.å. áåç êîëëèçèé [20]) è ñèãíàòóð Êàðïà–Ðàáèíà [21] âû-
ïîëíÿåò çàïðîñ rNN ñ r �1 çà âðåìÿ O D( )�occ â õóäøåì ñëó÷àå, ãäå D — ÷èñëî
ñèìâîëîâ â ñòðîêå. Çàòðàòû ïàìÿòè ñîñòàâëÿþò O ND( log | | )� áèòîâ, ãäå | |� — ðàç-
ìåð àëôàâèòà ñèìâîëîâ.
 [18] ïðåäëîæåíû âàðèàíòû ÈÑ (âêëþ÷àÿ ðàíäîìèçèðîâàííûå) ñ óìåíüøåí-
íûìè çà ñ÷åò ñæàòèÿ çàòðàòàìè ïàìÿòè. Äëÿ ñòðîê èç êîíå÷íîãî àëôàâèòà ïîñòîÿí-
íîãî ðàçìåðà ïîëó÷åíî [19] îïòèìàëüíîå âðåìÿ çàïðîñà O D B( / )�occ ïðè íåáîëü-
øèõ äîïîëíèòåëüíûõ çàòðàòàõ ïàìÿòè (B — ðàçìåð ìàøèííîãî ñëîâà â áèòàõ).
2.2. Ïîèñê áåç òåîðåòè÷åñêèõ ãàðàíòèé. Ïðàêòè÷åñêèå ðåøåíèÿ äëÿ ñèì-
âîëüíûõ ñòðîê è dist edit ðàçðàáîòàíû â [15, 22, 23, 16] (ñì. òàêæå ññûëêè ê íèì).
ÈÑ [15] îñíîâàíà íà ôèëüòðå Áëóìà [24]. Äëÿ ïîèñêà ñëîâ (ñòðîê) ñ r �1 ïî
dist edit ïðè êîíñòðóèðîâàíèè ÈÑ êàæäîå ñëîâî áàçû ïðåîáðàçóþò â 2 1D � ñòðîêó,
ãäå D �1 ñòðîêà ñîäåðæèò âñòàâêè ñïåöñèìâîëà â ïîçèöèÿõ îò 0 äî D , à D ñòðîê —
çàìåíó íà íåãî áóêâû â ïîçèöèè îò 0 äî D. Èç N ñëîâ áàçû êîíñòðóèðóþò
N D( )2 1� ñëîâ, õýøèðóþò k õýø-ôóíêöèÿìè è ïîìå÷àþò â õýø-òàáëèöå ñîîòâåò-
ñòâóþùèå ÿ÷åéêè. Ìîäèôèöèðîâàííûå ñòðîêè çàïîìèíàòü íå òðåáóåòñÿ. ×òîáû
ïî ñëîâó-çàïðîñó îïðåäåëèòü, èìååòñÿ ëè â áàçå ñëîâî, îòëè÷àþùååñÿ îò íåãî îä-
íîé áóêâîé (èëè ñîâïàäàþùåå), êîíñòðóèðóþò 2 1D � ìîäèôèêàöèþ ñëîâà-çàïðî-
ñà è âûïîëíÿþò 2 1D � çàïðîñ íà ñîâïàäåíèå. Äëÿ óñêîðåíèÿ ýòîé ÈÑ ãåíåðèðóþò
õýø-çíà÷åíèÿ òàê, ÷òîáû îíè îêàçàëèñü íà îäíîé ñòðàíèöå êîìïüþòåðíîé ïàìÿ-
òè. Äëÿ óìåíüøåíèÿ êîëè÷åñòâà ìîäèôèêàöèé [22, 23] â ÈÑ çàïîìèíàþò èñõîä-
íûå ñòðîêè áàçû, à òàêæå ñòðîêè, ïîëó÷åííûå óäàëåíèåì êàæäîãî èõ ñèìâîëà
(äëÿ êàæäîé òàêîé ìîäèôèêàöèè çàïîìèíàþò óêàçàòåëü íà èñõîäíóþ ñòðîêó).
Çàïðîñ âûïîëíÿåòñÿ ïîèñêîì ïî ñîâïàäåíèþ äëÿ âñåõ D ìîäèôèêàöèé ñòðîêè-çà-
ïðîñà, ïîëó÷åííûõ óäàëåíèåì îäíîãî ñèìâîëà. Îáîáùåíèå íà á�ëüøèå ðàäèóñû
çàïðîñà ðàññìîòðåíî â ïîäðàçä. 4.4.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5 185
 ÈÑ [16] ïðåäëîæåíû èçìåíåíèÿ òåîðåòè÷åñêîé ÈÑ [17], ïðåäíàçíà÷åííûå
äëÿ óëó÷øåíèÿ ïðàêòè÷åñêèõ õàðàêòåðèñòèê. Ýâðèñòèêè ïðè ýòîì íå èñïîëüçîâà-
ëèñü, ïîñêîëüêó îíè ìîãóò çíà÷èòåëüíî çàìåäëèòü ÈÑ äëÿ äàííûõ õóäøåãî ñëó-
÷àÿ. Âìåñòî èäåàëüíîãî õýøèðîâàíèÿ ïðèìåíÿþò áîëåå ýôôåêòèâíîå ëèíåéíîå
çîíäèðîâàíèå (ïðè êîëëèçèè õýø-çíà÷åíèé èùåòñÿ áëèæàéøàÿ ñëåäóþùàÿ ñâî-
áîäíàÿ ÿ÷åéêà è õýø ïîìåùàåòñÿ â íåå, ïðè ïîèñêå èùåòñÿ ñîâïàäåíèå õýøåé
â ïîñëåäîâàòåëüíîñòè ÿ÷ååê èëè ïóñòàÿ ÿ÷åéêà, åñëè îáúåêòà â òàáëèöå íåò). Çàò-
ðàòû ïàìÿòè íà õýø-òàáëèöû ìèíèìèçèðóþò çà ñ÷åò èñêëþ÷åíèÿ ïóñòûõ ÿ÷ååê.
Ïðåôèêñíûõ äåðåâüåâ è ñèãíàòóð Êàðïà–Ðàáèíà íå èñïîëüçóþò, âìåñòî ýòîãî âû-
ïîëíÿåòñÿ íåïîñðåäñòâåííîå ñðàâíåíèå ñòðîê. Çàòðàòû ïàìÿòè ñîñòàâëÿþò
O ND( log | | )� áèòîâ, âðåìÿ âûïîëíåíèÿ çàïðîñà O D D B( ( log | | ) / )
� (â ìîäå-
ëè RAM ñ äëèíîé ñëîâà B DN� � (log ( )), ò.å. ñî âñåìè îïåðàöèÿìè, âûïîëíÿå-
ìûìè çà ïîñòîÿííîå âðåìÿ). Ýòè õàðàêòåðèñòèêè ïîëó÷åíû äëÿ âåëè÷èíû èõ ìà-
òåìàòè÷åñêîãî îæèäàíèÿ ïî ðåàëèçàöèÿì ñëó÷àéíûõ ÷èñåë, èñïîëüçóåìûõ
â àëãîðèòìå. Ðåàëèçîâàí òàêæå àëãîðèòì äëÿ r � 2 ñ ñóïåðëèíåéíûìè çàòðàòàìè
ïàìÿòè, êîòîðûé íà ïðàêòèêå â äåñÿòêè ðàç áîëåå ìåäëåííûé, ÷åì ÈÑ äëÿ r �1.
Äëÿ ýòèõ çíà÷åíèé r ÈÑ èç [16] áûñòðåå, ÷åì ÈÑ èç [25] è FastSS (ïîäðàçä. 4.4).
3. ÏÎÈÑÊ ÄËß ÍÅÅÄÈÍÈ×ÍÎÃÎ ÐÀÄÈÓÑÀ ÇÀÏÐÎÑÀ
Ñ ÒÅÎÐÅÒÈ×ÅÑÊÈÌÈ ÃÀÐÀÍÒÈßÌÈ
Ðàññìîòðèì ÈÑ ñ òåîðåòè÷åñêèìè ãàðàíòèÿìè äëÿ âûïîëíåíèÿ òî÷íûõ äèàïà-
çîííûõ çàïðîñîâ (ïîäðàçä. 3.1) è ïðèáëèæåííûõ äèàïàçîííûõ çàïðîñîâ íà îñíî-
âå LSH (ïîäðàçä. 3.2). ÈÑ äëÿ âûïîëíåíèÿ çàïðîñîâ ïîèñêà ïðèáëèæåííîãî
áëèæàéøåãî ñîñåäà ñ òåîðåòè÷åñêèìè ãàðàíòèÿìè ïðèâåäåíà â ïîäðàçä. 5.1.
3.1. Òî÷íûé ïîèñê ñ òåîðåòè÷åñêèìè ãàðàíòèÿìè. Äëÿ âûïîëíåíèÿ çàïðîñà
rNN ñ ôèêñèðîâàííûì ðàäèóñîì çàïðîñà r �1 ïî dist edit ñ ãàðàíòèÿìè õóäøåãî ñëó-
÷àÿ èñïîëüçóåòñÿ ÈÑ k-errata tree [26], ïðåäëîæåííàÿ äëÿ ïîèñêà ïî dist Ham . Ïðè êî-
íñòðóèðîâàíèè ÈÑ ïðèìåíÿåòñÿ ñæàòîå ïðåôèêñíîå äåðåâî (compressed prefix tree
èëè trie) äëÿ ñòðîê áàçû è ðåêóðñèâíî ñîçäàþòñÿ ïîääåðåâüÿ çàìåíû, âñòàâêè è óäà-
ëåíèÿ. Ïðè âûïîëíåíèè çàïðîñà èññëåäóþòñÿ âñå ïóòè, ïîêà íå ïîëó÷àþò r îøèáîê
îòíîñèòåëüíî ñòðîêè-çàïðîñà (íà êàæäîì ïóòè ðàññìàòðèâàþòñÿ ðàçëè÷íûå âîçìîæ-
íûå êîìáèíàöèè îïåðàöèé ðåäàêòèðîâàíèÿ). Ïî ñðàâíåíèþ ñ àíàëîãè÷íîé ÈÑ äëÿ
dist Ham [26] â ñëó÷àå dist edit âðåìÿ âûïîëíåíèÿ çàïðîñà âêëþ÷àåò âìåñòî occ ñëàãàå-
ìîå occ �3r è óâåëè÷èâàþòñÿ ñîîòâåòñòâóþùèå êîíñòàíòû, ÷òî äàåò âðåìÿ
O D c N r DNr r( occ 3� � �(( log ) / ) log log( ) ). Ýêñïîíåíöèàëüíûå îò r çàòðàòû ïà-
ìÿòè íå ïîçâîëÿþò ïðèìåíÿòü ýòó ÈÑ íà ïðàêòèêå äëÿ r �1 [7]. ÈÑ ýòîãî òèïà ñ ëè-
íåéíûìè çàòðàòàìè ïàìÿòè [27] òàêæå íå èñïîëüçóåòñÿ íà ïðàêòèêå âñëåäñòâèå
ýêñïîíåíöèàëüíûõ çàâèñèìîñòåé îò r âðåìåíè âûïîëíåíèÿ çàïðîñà.
3.2. Ïðèáëèæåííûé ïîèñê íà îñíîâå ëîêàëüíî-÷óâñòâèòåëüíîãî õýøè-
ðîâàíèÿ.  ëîêàëüíî-÷óâñòâèòåëüíîì õýøèðîâàíèè (LSH), â îòëè÷èå îò îáû÷íî-
ãî, LSH-ôóíêöèè ãåíåðèðóþò õýø-çíà÷åíèÿ òàê, ÷òî âåðîÿòíîñòü èõ ñîâïàäåíèÿ
ó ñõîäíûõ îáúåêòîâ âûøå, ÷åì ó íåñõîäíûõ [12, 2, 5]. Îáúåêòû ñ îäèíàêîâûì õý-
øåì îáðàçóþò êîðçèíó. Â ÈÑ íà îñíîâå LSH ïðè ïîñòóïëåíèè îáúåêòà-çàïðîñà
ãåíåðèðóþò åãî LSH-õýø, èçâëåêàþò èç ñîîòâåòñòâóþùåé êîðçèíû îáúåêòû áàçû
è èñïîëüçóþò èõ â êà÷åñòâå êàíäèäàòîâ äëÿ óòî÷íåíèÿ ïî èñõîäíîìó ðàññòîÿ-
íèþ. Õýø-çíà÷åíèÿ ñõîäíûõ îáúåêòîâ, ñãåíåðèðîâàííûå îäíîé LSH-ôóíêöèåé,
ìîãóò îêàçàòüñÿ ðàçëè÷íûìè. Ïîýòîìó äëÿ ïîâûøåíèÿ âåðîÿòíîñòè íàõîæäåíèÿ
áëèçêèõ ê çàïðîñó îáúåêòîâ-êàíäèäàòîâ îáúåäèíÿþò ñïèñêè êàíäèäàòîâ èç êîð-
çèí íåñêîëüêèõ íåçàâèñèìûõ LSH-ôóíêöèé. ÈÑ íà îñíîâå LSH — îäíè èç íå-
ìíîãèõ ïðàêòè÷åñêè ðåàëèçîâàííûõ ÈÑ äëÿ ïðèáëèæåííîãî âåðîÿòíîñòíîãî ïî-
èñêà ïî ñõîäñòâó ñ ãàðàíòèÿìè ñóáëèíåéíîãî âðåìåíè â õóäøåì ñëó÷àå.
186 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5
ÈÑ íà îñíîâå LSH äëÿ ïðèáëèæåííîãî ïîèñêà ïî dist edit âïåðâûå ðåàëèçîâàíà
â [28, 29]. Ñòðîêè âêëàäûâàëèñü â ïðîñòðàíñòâî L1 (ò.å. â âåêòîðû ñ dist Man ) èçâëå-
÷åíèåì n-ãðàìì ðàçëè÷íîé äëèíû è ôîðìèðîâàíèåì âåêòîðîâ ÷àñòîòû èõ âñòðå÷àå-
ìîñòè â ñòðîêå (êîìïîíåíò âåêòîðà ñîîòâåòñòâóåò n-ãðàììå). Çàòåì ïðèìåíÿëîñü
LSH-õýøèðîâàíèå íà îñíîâå ñëó÷àéíîãî ïðîåöèðîâàíèÿ ñ ýëåìåíòàìè ñëó÷àéíûõ
ìàòðèö èç óñòîé÷èâîãî ðàñïðåäåëåíèÿ Êîøè (ñì. [30, 31] è îáçîðû [2, 5]). Äëÿ âû-
ïîëíåíèÿ çàïðîñà ïðèáëèæåííîãî áëèæàéøåãî ñîñåäà èñïîëüçîâàëàñü ÈÑ
LSH-forest [32, 33].
Äëÿ ïðèáëèæåííîãî ðåøåíèÿ çàäà÷è APSS â EmbedJoin [34] ïðèìåíÿþò ïðè-
áëèæåííîå âëîæåíèå CGK [35] ñòðîê ñ dist edit â ïðîñòðàíñòâî áèíàðíûõ âåêòîðîâ
ñ dist Ham . Íà ïðàêòèêå ðàçìåðíîñòü âëîæåíèÿ âûáèðàþò êàê óòðîåííóþ ñðåäíþþ
äëèíó ñòðîêè â áàçå (áîëåå äëèííûå ñòðîêè óêîðà÷èâàþò). Çàòåì ïî ñýìïëèðîâàí-
íûì áèíàðíûì âåêòîðàì (SamplingLSH [2, 5]) ñòðîÿò ÈÑ LSH èç L òàáëèö äëÿ ïî-
èñêà ïî dist Ham . Ïðèìåíåíèå íåñêîëüêèõ ÈÑ ñ ðàçëè÷íûìè ðåàëèçàöèÿìè âëîæå-
íèÿ CGK óëó÷øàåò ðåçóëüòàòû. Äëÿ ñòðîê-êàíäèäàòîâ âûïîëíÿþò ôèëüòðàöèþ ïî
äëèíå (ïîäðàçä. 4.1), à äëÿ îñòàâøèõñÿ êàíäèäàòîâ òî÷íî âû÷èñëÿþò dist edit .
Áèîëîãè÷åñêèì áàçàì ãåíîìà è áåëêîâ ñâîéñòâåííî íàëè÷èå ñõîäíûõ ñòðîê
ñ äëèííûì ïðåôèêñîì âñòàâîê â îäíîé èç íèõ. Ïðè áîëüøèõ çíà÷åíèÿõ ïîðîãà r
òàêàÿ ñòðóêòóðà áàç ïðèâîäèò ê òîìó, ÷òî á�ëüøàÿ ÷àñòü âåëè÷èíû ðàññòîÿíèÿ
ðåäàêòèðîâàíèÿ ìîæåò áûòü îáóñëîâëåíà ïðåôèêñàìè âñòàâîê. Ýòî óâåëè÷èâàåò
êîëè÷åñòâî false negatives â EmbedJoin. Äëÿ áàç òàêîãî òèïà èñïîëüçóþò ñóôôèê-
ñû èñõîäíûõ ñòðîê, íà÷èíàþùèåñÿ ñ ïîçèöèé, îòñòîÿùèõ îò íà÷àëà ñ íåêîòîðûì
øàãîì. Êðîìå òîãî, ÷òîáû óìåíüøèòü êîëè÷åñòâî êàíäèäàòîâ, â èõ ìíîæåñòâî
âêëþ÷àþò òîëüêî ñòðîêè áàçû ñ íåîäíîêðàòíîé êîëëèçèåé LSH-õýøåé ñ LSH-õý-
øàìè ñòðîêè-çàïðîñà. Ìåòîä õîðîøî ìàñøòàáèðóåòñÿ ñ äëèíîé ñòðîêè è âåëè÷è-
íîé ïîðîãà íà ðàññòîÿíèÿ è ïî ñêîðîñòè çíà÷èòåëüíî ïðåâîñõîäèò PassJoin [36],
EDJoin [37], AdaptJoin [38], QChunk [39] (ðàçä. 4), íåìíîãî óñòóïàÿ èì â òî÷íîñ-
òè. Äëÿ ñòðîê ìàëîé äëèíû àëãîðèòì íå äàåò ïðåèìóùåñòâ.
4. ÏÐÀÊÒÈ×ÅÑÊÈÉ ÒÎ×ÍÛÉ ÏÎÈÑÊ Ñ ÍÅÅÄÈÍÈ×ÍÛÌ ÐÀÄÈÓÑÎÌ ÇÀÏÐÎÑÀ
Ðàññìîòðèì ÈÑ äëÿ âûïîëíåíèÿ òî÷íîãî äèàïàçîííîãî çàïðîñà rNN ñ r �1.
Ýòè ÈÑ ðåàëèçîâàíû íà ïðàêòèêå, íî èñïîëüçóþò ýâðèñòèêè è ïîýòîìó íå ãà-
ðàíòèðóþò ñóáëèíåéíîãî âðåìåíè âûïîëíåíèÿ çàïðîñà äëÿ äàííûõ õóäøåãî
ñëó÷àÿ. ×àñòî ÈÑ êîíñòðóèðóþò äëÿ âûïîëíåíèÿ çàïðîñà ñ ôèêñèðîâàííûì
çíà÷åíèåì r �1. Äëÿ ïîèñêà ïðèìåíÿþò ñòðàòåãèþ F&R ñ êîìáèíàöèåé ðàçëè÷-
íûõ ôèëüòðîâ, àíàëîãè÷íûõ ïðèìåíÿåìûì äëÿ ïîèñêà ìíîæåñòâ èëè áèíàð-
íûõ âåêòîðîâ [13, 4], íî ñïåöèàëèçèðîâàííûõ äëÿ ñòðîê.
 öåëÿõ áûñòðîé ôèëüòðàöèè èç ñòðîê îáû÷íî èçâëåêàþò ïðèçíàêè, òàêèå
êàê íåïåðåñåêàþùèåñÿ èëè ïåðåñåêàþùèåñÿ n-ãðàììû áåç ó÷åòà èëè ñ ó÷åòîì èõ
ïîëîæåíèÿ â ñòðîêå. Èñïîëüçóþò òàêæå äðóãèå ïðèçíàêè, êîòîðûå ìîæíî îõàðàê-
òåðèçîâàòü êàê ãëîáàëüíûå, íàïðèìåð äëèíà ñòðîêè. Äëÿ ñòðîê, áëèçêèõ ïî
dist edit , íåîáõîäèìî ñîâïàäåíèå îïðåäåëåííîãî êîëè÷åñòâà ïðèçíàêîâ ëèáî äîë-
æíû îêàçàòüñÿ ïîõîæèìè ãëîáàëüíûå ïðèçíàêè. ×òîáû áûñòðî íàéòè òàêèå ñòðî-
êè-êàíäèäàòû (è èñêëþ÷èòü îñòàëüíûå), ïðèìåíÿþò îáðàòíîå èíäåêñèðîâàíèå.
Êàê è äëÿ áèíàðíûõ âåêòîðîâ [4], äëÿ äëèííûõ ñòðîê èñïîëüçóþò ðàçáèåíèå íà
íåïåðåñåêàþùèåñÿ ÷àñòè è ñòðîÿò ÈÑ äëÿ ÷àñòåé; êàíäèäàòàìè ÿâëÿþòñÿ ñòðîêè,
èçâëå÷åííûå èç âñåõ ÈÑ äëÿ ÷àñòåé.
Äëÿ ñòðîê èñïîëüçóþò ðàçëè÷íûå òèïû ñïåöèàëèçèðîâàííîé ôèëüòðàöèè: ïî
êîëè÷åñòâó ñîâïàâøèõ ïðèçíàêîâ, äëèíå ñòðîê è ïîëîæåíèþ ïðèçíàêîâ â ñòðîêå
(ïîäðàçä. 4.1). Èíîãäà óäîáíî ïðåäñòàâëÿòü ïðèçíàêè â âèäå âåêòîðîâ è ïðèìå-
íÿòü ôèëüòðàöèþ íà îñíîâå ðàññòîÿíèé ìåæäó âåêòîðàìè (ïîäðàçä. 4.2). Çàòðàòû
ïàìÿòè íà ÈÑ óìåíüøàþò îòáîðîì ïîäìíîæåñòâà èçâëå÷åííûõ ïðèçíàêîâ (ïîä-
ðàçä. 4.3). Êàê è äëÿ dist Ham , èñïîëüçóþò ìîäèôèêàöèþ ñòðîê è ïîèñê ïî ñîâïà-
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5 187
äåíèþ (ïîäðàçä. 4.4).  öåëÿõ ýêîíîìèè âû÷èñëåíèé äëÿ ñòðîê ñ îáùèìè ïðå-
ôèêñàìè ïðèìåíÿþò ïðåôèêñíûå äåðåâüÿ (ïîäðàçä. 4.5). Ñîêðàùåíèÿ êîëè÷åñòâà
ïðèçíàêîâ äëÿ ôèëüòðàöèè äîáèâàþòñÿ ðàçáèåíèåì ñòðîê íà íåïåðåñåêàþùèåñÿ
÷àñòè (ïîäðàçä. 4.6).
4.1. Ôèëüòðàöèÿ ñòðîê ïî ñîâïàäåíèþ è ïîëîæåíèþ n-ãðàìì. Äëÿ ñòðîê
a, b, ïðåîáðàçîâàííûõ â n-ãðàììû, åñëè dist edit ( , )a b r� , òî êîëè÷åñòâî ñîâïàâ-
øèõ n-ãðàìì áîëüøå èëè ðàâíî T a b n rn� � � �max (| | , | | ) 1 [40]. Ïîëîæåíèå
n-ãðàìì íå ó÷èòûâàåòñÿ. Èíîãäà ñòðîêè íàðàùèâàþò êîíêàòåíàöèåé n �1 «ïðå-
ôèêñíîãî» è n �1 «ñóôôèêñíîãî» ñïåöñèìâîëà (íå èç àëôàâèòà), òîãäà âûðàæå-
íèå äëÿ T èçìåíÿåòñÿ [41].
Òàêèì îáðàçîì, äëÿ ñòðîêè-çàïðîñà x óñëîâèÿì çàïðîñà rNN ïî dist edit óäîâ-
ëåòâîðÿþò ñòðîêè áàçû y, êîëè÷åñòâî ñîâïàâøèõ n-ãðàìì â êîòîðûõ íå ìåíüøå
| |x n rn� � �1 (åñëè íå ó÷èòûâàåòñÿ äëèíà ñòðîê y). Çäåñü | |x n� �1 — êîëè÷åñòâî
n-ãðàìì â ñòðîêå, rn — êîëè÷åñòâî n-ãðàìì, èçìåíåííûõ r îïåðàöèÿìè ðåäàêòè-
ðîâàíèÿ. Òàêèå ñòðîêè ñòàíîâÿòñÿ êàíäèäàòàìè, äëÿ êîòîðûõ ïðîâåðÿåòñÿ òî÷íîå
âûïîëíåíèå óñëîâèÿ dist edit � r. Äëÿ áûñòðîãî íàõîæäåíèÿ ñòðîê-êàíäèäàòîâ,
èìåþùèõ ïðåâûøàþùåå ïîðîã êîëè÷åñòâî n-ãðàìì, îáùèõ ñî ñòðîêîé-çàïðîñîì,
ïðèìåíÿþò îáðàòíîå èíäåêñèðîâàíèå (ñì. ïîäðàçä. 1.7).
×òîáû èçáåæàòü ðàáîòû êàê ñ î÷åíü ÷àñòî, òàê è ñ î÷åíü ðåäêî âñòðå÷àþùè-
ìèñÿ n-ãðàììàìè, èñïîëüçóþò èõ ðàçëè÷íóþ äëèíó [42, 43]. Òàêèå n-ãðàììû ïî-
çâîëÿþò ïîâûñèòü ýôôåêòèâíîñòü èñêëþ÷åíèÿ êàíäèäàòîâ. Îòìåòèì, ÷òî ïðèìå-
íåíèå n-ãðàìì ðàçëè÷íîé äëèíû äëÿ óìåíüøåíèÿ èñêàæåíèÿ ïðè âëîæåíèè
dist edit â dist Man ðàññìîòðåíî â [28].
Ôèëüòðàöèÿ ïî ñîâïàäåíèþ n-ãðàìì èñïîëüçóåò îòâåò íà âîïðîñ: «êàêîå ìàêñè-
ìàëüíîå êîëè÷åñòâî n-ãðàìì ïîðòÿò r îïåðàöèé ðåäàêòèðîâàíèÿ?». Ôèëüòðàöèÿ çà
ñ÷åò ó÷åòà íåñîâïàäàþùèõ n-ãðàìì â EdJoin [37] îòâå÷àåò íà âîïðîñ: «êàêîå ìèíè-
ìàëüíîå êîëè÷åñòâî îïåðàöèé ðåäàêòèðîâàíèÿ ìîæåò ïðèâåñòè ê íàáëþäàåìûì íå-
ñîâïàäàþùèì n-ãðàììàì?». Íà îñíîâå àíàëèçà ïîëîæåíèÿ íåñîâïàäàþùèõ n-ãðàìì
(ÿâëÿþòñÿ ëè îíè íåïåðåñåêàþùèìèñÿ èëè ÷àñòè÷íî ïåðåñåêàþùèìèñÿ) ïðåäëîæåí
æàäíûé àëãîðèòì, êîòîðûé äàåò íèæíþþ ãðàíèöó dist edit (êàê äëÿ âñåãî ìíîæåñòâà
íåñîâïàäàþùèõ n-ãðàìì, òàê è äëÿ ëþáîãî åãî ïîäìíîæåñòâà). Ýòà ãðàíèöà ìîæåò
èñïîëüçîâàòüñÿ è íà ýòàïå ôèëüòðàöèè, è íà ýòàïå óòî÷íåíèÿ. Ôèëüòð ïî ñîäåðæà-
íèþ íåñîîòâåòñòâóþùèõ n-ãðàìì â EdJoin ðàáîòàåò ñ ðàññòîÿíèÿìè âåêòîðîâ
n-ãðàìì (ïîäðàçä. 4.2) è ïðèìåíÿåòñÿ íà ýòàïå óòî÷íåíèÿ.
Ôèëüòð ïî äëèíå ñòðîêè [41] ó÷èòûâàåò, ÷òî ïðè dist edit � r ðàçíîñòü äëèí
ñòðîê íå ìîæåò ïðåâûøàòü r. Ïîçèöèîííûé ôèëüòð [41] (ôèëüòð ïî ïîëîæåíèþ
n-ãðàìì) îñíîâàí íà òîì, ÷òî ïðè dist edit � r n-ãðàììà â îäíîé ñòðîêå íå ìîæåò
ñîîòâåòñòâîâàòü n-ãðàììå â äðóãîé ñòðîêå, êîòîðàÿ îòñòîèò áîëåå ÷åì íà r ïîçè-
öèé. Çäåñü äëÿ ñòðîêè ãåíåðèðóþòñÿ è çàïîìèíàþòñÿ n-ãðàììû ñ èõ ïîëîæåíèåì.
Îòìåòèì, ÷òî ïðèìåíåíèå ðàçëè÷íûõ ôèëüòðîâ äî ñëèÿíèÿ îáðàòíûõ ñïèñêîâ
îáúåêòîâ èç îáðàòíîãî èíäåêñà íå âñåãäà óñêîðÿåò ïîëó÷åíèå êàíäèäàòîâ, òàê êàê
ìîæåò ñîçäàâàòü áîëüøîå êîëè÷åñòâî êîðîòêèõ ñïèñêîâ, ðàáîòà ñ êîòîðûìè íå-
ýôôåêòèâíà. Íåäîñòàòêîì n-ãðàììíîé ôèëüòðàöèè ÿâëÿåòñÿ íåîáõîäèìîñòü âû-
ïîëíåíèÿ óñëîâèÿ | | ( )a r n
�1 , ÷òî íå ïîçâîëÿåò ðàáîòàòü ñ êîðîòêèìè ñòðîêàìè
è áîëüøèìè ðàäèóñàìè çàïðîñà r, à òàêæå ïðèìåíÿòü äëÿ ñîêðàùåíèÿ ìíîæåñòâà
îáúåêòîâ-êàíäèäàòîâ äëèííûå, áîëåå ñåëåêòèâíûå n-ãðàììû.
4.2. Ïðåîáðàçîâàíèå ñòðîê â âåêòîðû è ôèëüòðàöèÿ ïî ñîäåðæàíèþ. Ïóñòü äëÿ
êàæäîé ñòðîêè ïîñòðîåí âåêòîð ÷àñòîòû âñòðå÷àåìîñòè ñèìâîëîâ (ðàçìåðíîñòü âåêòî-
ðîâ ðàâíà ðàçìåðó àëôàâèòà ñèìâîëîâ). Íèæíåé ãðàíèöåé dist edit ÿâëÿåòñÿ ÷àñòîòíîå
ðàññòîÿíèå dist freq ìåæäó âåêòîðàìè a , b ÷àñòîòû âñòðå÷àåìîñòè ñèìâîëîâ â ñòðîêàõ
[44, 7]: dist dist dist distfreq Man Man( , ) / (| ( , ) ( , ) |a b a 0 b 0� � �1 2 Man ( , ))a b .
188 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5
Ñòðîêó âêëþ÷àþò â ñïèñîê êàíäèäàòîâ, åñëè dist freq � r, òàê êàê dist freq �
� dist edit . Ñòðîêó èñêëþ÷àþò ïðè dist freq � r. Ýòî âûïîëíÿåòñÿ, åñëè, íàïðèìåð,
äëÿ ëþáîãî ñèìâîëà ðàçíîñòü ÷àñòîò ïðåâûøàåò r. Äðóãèì óñëîâèåì èñêëþ÷åíèÿ ÿâ-
ëÿåòñÿ dist Man ( , ) | | | | | |a b � � �2r a b . Äåéñòâèòåëüíî, èç 1 2/ (| ( , )dist Man a 0 �
� � �dist distMan Man( , ) | ( , ))b 0 a b r ñëåäóåò dist distMan Man( , ) | ( , )a b a 0� � �2r
� � � �dist Man ( , ) | | | | | | |b 0 2r a b . Î÷åâèäíî 2 2r a b r� � �| | | | | | , ò.å. ìîæíî èñ-
ïîëüçîâàòü çíà÷åíèå 2r äëÿ ïðîèçâîëüíûõ ñòðîê. Ïîýòîìó âìåñòî çàïðîñà ïî dist edit
ìîæíî âûïîëíÿòü çàïðîñ ïî dist freq ñ òåì æå r, èëè ïî dist Man ñ ìîäèôèöèðîâàí-
íûì ïîðîãîì, â òîì ÷èñëå ñ èñïîëüçîâàíèåì ÈÑ.
 ôèëüòðå ïî ñîäåðæàíèþ EdJoin [37] ðàññìàòðèâàþò îêíî íà ñòðîêàõ (â ðå-
àëèçàöèè ïðèìåíÿþò ñïåöèàëüíóþ ñõåìó äîïîëíåíèÿ ñòðîê ñèìâîëàìè). Äëÿ ëþ-
áîãî îêíà âûïîëíÿåòñÿ dist distMan edit� 2 , ãäå dist Man âû÷èñëåíî ïî âåêòîðàì
÷àñòîò ñèìâîëîâ â îêíå, dist edit îïðåäåëÿåòñÿ ìåæäó ïîäñòðîêàìè â îêíå è íå
ïðåâûøàåò dist edit ìåæäó ïîëíûìè ñòðîêàìè. Ýòî ñëåäóåò èç òîãî, ÷òî ëþáàÿ
îïåðàöèÿ ðåäàêòèðîâàíèÿ óâåëè÷èâàåò âåëè÷èíó dist Man íå áîëåå ÷åì íà 2.
Òàê êàê äëÿ âåêòîðîâ, ïîëó÷åííûõ áèíàðèçàöèåé èñõîäíûõ âåêòîðîâ ÷àñòîò,
dist distHam Man� , òî äëÿ íèõ dist distHam edit� 2 . Íàïðèìåð, ôèëüòð ïî ñîäåðæàíèþ
EdJoin [37] ôîðìèðóåò áèíàðíûé âåêòîð (32 áèòà) h ( )a ñòðîêè a òàê, ÷òî èìåþùå-
ìóñÿ ñèìâîëó ñîîòâåòñòâóåò åäèíè÷íîå çíà÷åíèå. Óñëîâèå dist edit ( , )a b r� ìîæåò
âûïîëíÿòüñÿ òîëüêî â ñëó÷àå, åñëè dist Ham ( ( ), ( ))h ha b r� 2 [40, 7].
Ðàññìîòðèì âåêòîðû ÷àñòîò íå îòäåëüíûõ ñèìâîëîâ, à n-ãðàìì. Äëÿ ñòðîê,
ýëåìåíòàìè êîòîðûõ ÿâëÿþòñÿ n-ãðàììû, âûïîëíÿåòñÿ dist distfreq edit� . Ñîãëàñ-
íî [40] êîëè÷åñòâî n-ãðàìì, êîòîðîå ìîäèôèöèðóåò îäíà îïåðàöèÿ ðåäàêòèðîâà-
íèÿ, íå ïðåâûøàåò n. Ïîýòîìó dist distfreq edit/ n � , ãäå dist freq — ÷àñòîòíîå ðàñ-
ñòîÿíèå ìåæäó âåêòîðàìè ÷àñòîò n-ãðàìì ñòðîê, à dist edit — ìåæäó ñòðîêàìè
ñèìâîëîâ. Ñîîòâåòñòâåííî äëÿ áèíàðíûõ âåêòîðîâ n-ãðàìì ñòðîê-êàíäèäàòîâ âû-
ïîëíÿåòñÿ dist Ham � 2rn.
Äëÿ óìåíüøåíèÿ ðàçìåðíîñòè âåêòîðîâ ïðèìåíÿþò õýøèðîâàíèå. Åñëè
óìåíüøèòü ðàçìåð àëôàâèòà õýøèðîâàíèåì ñèìâîëîâ, òî dist edit ìåæäó ïîëó÷èâ-
øèìèñÿ ñòðîêàìè ÿâëÿåòñÿ íèæíåé ãðàíèöåé èñõîäíîãî dist edit [7]. Ïîýòîìó
dist freq ìåæäó âåêòîðàìè ÷àñòîò ñèìâîëîâ óìåíüøåííîé (çà ñ÷åò õýøèðîâàíèÿ)
ðàçìåðíîñòè òàêæå ÿâëÿåòñÿ íèæíåé ãðàíèöåé èñõîäíîãî dist edit . Â [45] õýøèðî-
âàíèå èíòåðïðåòèðóåòñÿ êàê ðàçáèåíèå ñèìâîëîâ àëôàâèòà íà ïîäìíîæåñòâà.
Ïðèìåíÿþò òàêæå õýøèðîâàíèå n-ãðàìì [46]. Ïåðåä èçâëå÷åíèåì n-ãðàìì
ñòðîêè äîïîëíÿþò â íà÷àëå è â êîíöå n �1 ñïåöñèìâîëîì. Õýø-ôóíêöèÿ ïðåîáðà-
çóåò n-ãðàììó â öåëîå ÷èñëî, êîòîðîå ÿâëÿåòñÿ íîìåðîì êîìïîíåíòà áèíàðíîãî
âåêòîðà. Ïðè õýøèðîâàíèè òàêæå ó÷èòûâàåòñÿ ÷àñòîòà âñòðå÷àåìîñòè n-ãðàììû
(äîáàâëåíèåì ÷èñëà â êîíåö n-ãðàììû êàê äîïîëíèòåëüíîãî ñèìâîëà).  ñëó÷àå
êîëëèçèè çíà÷åíèå áèíàðíîãî êîìïîíåíòà âåêòîðà ìîäèôèöèðóþò îïåðàöèåé OR
èëè XOR. Áèíàðíûå âåêòîðû ñðàâíèâàþò ïî dist Ham . Åñëè dist edit ( , )x y r� , òî
dist Ham ( ( ), ( )) | | | | | |h hx y nr x y� � �2 .
 [46] äëÿ ïîëó÷åííûõ áèíàðíûõ âåêòîðîâ âûïîëíÿëñÿ ëèíåéíûé ïîèñê ïî
dist Ham ñ ïîñëåäóþùèì óòî÷íåíèåì ïî dist edit ñòðîê. Ýôôåêòèâíîñòü èñêëþ÷å-
íèÿ ïî dist Ham ðàñòåò ñ ðàçìåðíîñòüþ áèíàðíîãî âåêòîðà (èñïîëüçîâàëèñü ðàç-
ìåðíîñòè äî 2560). Âî ìíîãèõ ñëó÷àÿõ äîñòàòî÷íî ðàçìåðíîñòè 640. Ïîêàçàíî
óñêîðåíèå âûïîëíåíèÿ çàïðîñîâ ïî ñðàâíåíèþ ñ Flamingo [47], AdaptSearch [38],
Pivotal [48] è äðóãèìè àëãîðèòìàìè ïðè íà ïîðÿäîê ìåíüøèõ çàòðàòàõ ïàìÿòè.
Ñî ñôîðìèðîâàííûìè âåêòîðàìè ìîãóò òàêæå ïðèìåíÿòüñÿ ñîîòâåòñòâóþ-
ùèå ÈÑ ïîèñêà ïî ñõîäñòâó (äðåâîâèäíûå è äðóãèå [5, 6]).
4.3. Ïðåôèêñíàÿ ôèëüòðàöèÿ äëÿ ñòðîê. Ïðåôèêñíàÿ ôèëüòðàöèÿ [8] ïî-
çâîëÿåò ñíèçèòü çàòðàòû ïàìÿòè íà ÈÑ è âðåìÿ ôèëüòðàöèè çà ñ÷åò ðàññìîòðåíèÿ
íå âñåõ, à òîëüêî ÷àñòè n-ãðàìì ñòðîê. Äëÿ ýòîãî â All-Pairs-Ed [49] n-ãðàììû
óïîðÿäî÷èâàþò ñîãëàñíî íåêîòîðîìó ãëîáàëüíîìó ïîðÿäêó, íàïðèìåð ïî óâåëè-
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5 189
÷åíèþ ÷àñòîòû âñòðå÷àåìîñòè. Åñëè îáùåå êîëè÷åñòâî ñîâïàäàþùèõ n-ãðàìì
äâóõ ñòðîê íå ìåíüøå ïîðîãîâîãî T , òî â ïåðâûõ | |a Tn-gramm � �1 n-ãðàììàõ
(ò.å. â ïðåôèêñàõ) äâóõ ñòðîê äîëæíà îêàçàòüñÿ îäèíàêîâàÿ n-ãðàììà (çäåñü
| |an-gramm — êîëè÷åñòâî n-ãðàìì â ñòðîêå a). Ó÷èòûâàÿ, ÷òî êîëè÷åñòâî n-ãðàìì
â ñòðîêå ðàâíî | |a n� �1è âûðàæåíèå äëÿ T a n rn� � � �| | 1 (ñì. ïîäðàçä. 4.1), ïî-
ëó÷àåì äëèíó ïðåôèêñà nr �1.
Ïðèìåíÿÿ ôèëüòð ïî ïîëîæåíèþ, ïðè ïðåôèêñíîé ôèëüòðàöèè ñðàâíèâàþò
n-ãðàììû, ïîëîæåíèÿ êîòîðûõ îòëè÷àþòñÿ íå áîëåå ÷åì íà r ïîçèöèé (ñì. ïîä-
ðàçä. 4.1). Ôèëüòð íåñîâïàäåíèé èç EdJoin (ñì. ïîäðàçä. 4.2) ïîçâîëÿåò óìåíü-
øèòü äëèíó ïðåôèêñà ñ nr �1äî íåêîòîðîé âåëè÷èíû â äèàïàçîíå [ , ]r nr� �1 1 .
Äëÿ ïðåôèêñíîé ôèëüòðàöèè èñïîëüçóåòñÿ ìàëîå êîëè÷åñòâî n-ãðàìì. Ïîýòîìó,
êîãäà ñòðîêè äëèííûå, ýôôåêòèâíîñòü èñêëþ÷åíèÿ äëÿ ìàëîãî êîëè÷åñòâà n-ãðàìì
óìåíüøàåòñÿ. Êðîìå òîãî, äëèíà ïðåôèêñà çàâèñèò îò r. Åñëè êîíñòðóèðîâàòü ÈÑ ïî
äëèííûì ïðåôèêñàì, ðàññ÷èòàííûì íà áîëüøèå r, ðàçìåð ÈÑ óâåëè÷èòñÿ.
4.4. Ïîèñê íà îñíîâå ìîäèôèêàöèè ñòðîê. Îäíèì èç íåäîñòàòêîâ n-ãðàììíîãî
ïîäõîäà (ñì. ïîäðàçä. 4.1, 4.3) ÿâëÿåòñÿ íåâîçìîæíîñòü ðàáîòû ñ êîðîòêèìè ñòðîêà-
ìè. Ïîäõîä ê ïîèñêó ñõîäíûõ ñòðîê ïîñðåäñòâîì âñåõ âîçìîæíûõ ìîäèôèêàöèé
ñòðîê è ïîñëåäóþùåãî ïîèñêà ïî ñîâïàäåíèþ (àíàëîãè÷íî ïîèñêó áèíàðíûõ âåêòî-
ðîâ [4]) îñëîæíÿåòñÿ íåîáõîäèìîñòüþ áîëüøîãî êîëè÷åñòâà ðàçëè÷íûõ ìîäèôèêà-
öèé âñëåäñòâèå êàê ïðèìåíåíèÿ dist edit , òàê è ïåðåáîðà áîëüøîãî êîëè÷åñòâà ñî÷å-
òàíèé ñèìâîëîâ èç àëôàâèòà (îöåíêà O D r r( | | )� äàíà â [50]).
×àñòè÷íîå ðåøåíèå ýòîé ïðîáëåìû ñîñòîèò â èñïîëüçîâàíèè âìåñòî âñåõ
âîçìîæíûõ ìîäèôèêàöèé òîëüêî ìîäèôèêàöèé óäàëåíèåì ([22, 23, 7] è ñì. ïîä-
ðàçä. 2.2). Ïóñòü dist edit � r è óäàëÿåòñÿ îò 0 äî r ñèìâîëîâ äâóõ ñòðîê. Ïîêàçàíî,
÷òî õîòÿ áû îäíà èç ïîëó÷èâøèõñÿ ïàð ñòðîê ñîâïàäåò [51, 25]. Òàêèì îáðàçîì,
êîëè÷åñòâî ìîäèôèêàöèé îäíîé ñòðîêè óìåíüøàåòñÿ äî C
D
i
i r�� , ò.å. äî êîëè-
÷åñòâà ìîäèôèêàöèé çàïðîñà äëÿ áèíàðíûõ âåêòîðîâ [4].
Ïðè êîíñòðóèðîâàíèè ÈÑ FastSS (http://fastss.csg.uzh.ch/ [51]) ãåíåðèðóåò âñå
âîçìîæíûå ìîäèôèêàöèè óäàëåíèåì äî r ñèìâîëîâ âñåõ ñòðîê áàçû è ôîðìèðóåò
îáðàòíûé èíäåêñ ïî ýòèì ìîäèôèêàöèÿì è ñîîòâåòñòâóþùèì èì èñõîäíûì ñòðî-
êàì. Ïðè âûïîëíåíèè çàïðîñà ìîäèôèöèðóþò óäàëåíèÿìè ñòðîêó-çàïðîñ è äëÿ êàæ-
äîé ìîäèôèêàöèè èçâëåêàþò êàíäèäàòîâ, ñ êîòîðûìè âû÷èñëÿþò dist edit . Îòìåòèì,
÷òî åñëè äëÿ êàæäîé ìîäèôèêàöèè ñîõðàíÿòü ïîëîæåíèÿ óäàëåííûõ ñèìâîëîâ, òî
ìîæíî îïðåäåëèòü dist edit ìåæäó îáúåêòîì-çàïðîñîì è îáúåêòîì-êàíäèäàòîì çà âðå-
ìÿ O r( ). Ðàñøèðåíèå íà ðàçëè÷íûå ðàçìåðû ñòðîê è ðàäèóñû çàïðîñà ðàçáèåíèåì
ñòðîê íà ÷àñòè ïðåäëîæåíî â [52, 25] è ïðåâîñõîäèò FastSS ïî ñêîðîñòè.
Ìåòîä ìîäèôèêàöèè ñòðîê ïîñðåäñòâîì óäàëåíèÿ èõ ñèìâîëîâ â îòëè÷èå îò
ïîäõîäà n-ãðàìì (ñì. ïîäðàçä. 4.1, 4.3) ïîçâîëÿåò ðàáîòàòü ñ êîðîòêèìè ñòðîêà-
ìè. Ìîäèôèöèðîâàííûå ñòðîêè äëèííåå n-ãðàìì, ÷òî ïîçâîëÿåò ïðîâîäèòü áîëåå
ýôôåêòèâíóþ ôèëüòðàöèþ êàíäèäàòîâ äëÿ êîðîòêèõ ñòðîê è ìàëûõ çíà÷åíèé r.
Òàê, äëÿ áàç ñ î÷åíü êîðîòêèìè ñòðîêàìè FastSS ïîêàçàë ëó÷øåå áûñòðîäåéñòâèå
îòíîñèòåëüíî âñåõ ñðàâíèâàåìûõ àëãîðèòìîâ [8] (ïîäðàçä. 4.6).
Îäíàêî ïîäõîä ìîäèôèêàöèè óäàëåíèåì òðåáóåò çíà÷èòåëüíûõ çàòðàò ïàìÿ-
òè íà õðàíåíèå âñåõ ìîäèôèöèðîâàííûõ ñòðîê è áîëüøîãî êîëè÷åñòâà ìîäèôè-
êàöèé è çàïðîñîâ ïî íèì ïðè ïîèñêå êàíäèäàòîâ è ïîýòîìó íà ïðàêòèêå ðàáîòàåò
òîëüêî äëÿ êîðîòêèõ ñòðîê.
4.5. Ïîèñê ñòðîê íà îñíîâå ïðåôèêñíûõ äåðåâüåâ. Âñëåäñòâèå ïåðåêðûòèÿ
n-ãðàìì èõ îáðàòíîå èíäåêñèðîâàíèå òðåáóåò îáúåìà ïàìÿòè â íåñêîëüêî ðàç
á�ëüøåãî, ÷åì îáúåì áàçû, è ïëîõî ðàáîòàåò ñ êîðîòêèìè ñòðîêàìè (ñì. ïîä-
ðàçä. 4.1). ÈÑ íà îñíîâå ìîäèôèêàöèè óäàëåíèåì õîðîøî ðàáîòàåò òîëüêî ñ êî-
ðîòêèìè ñòðîêàìè, òàê êàê òðåáóåò åùå á�ëüøèõ çàòðàò ïàìÿòè è çíà÷èòåëüíîãî
êîëè÷åñòâà çàïðîñîâ íà ñîâïàäåíèå (ñì. ïîäðàçä. 4.4). Êðîìå òîãî, ïðè ðàáîòå
190 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5
ñ êàæäûì îáúåêòîì-êàíäèäàòîì âûïîëíÿþòñÿ îïåðàöèè ñëó÷àéíîãî ââîäà-âûâî-
äà, òàê êàê êàíäèäàòû ðàñïîëîæåíû â ñëó÷àéíîì ìåñòå ïàìÿòè, ïîýòîìó äëÿ õðà-
íåíèÿ áàçû íóæíà áûñòðàÿ ïàìÿòü.
Äëÿ ïðåîäîëåíèÿ íåêîòîðûõ èç ýòèõ íåäîñòàòêîâ ïðèìåíÿþò äðåâîâèäíûå
ÈÑ (ñì. îáçîð [6]). Ðàññìîòðèì ÈÑ íà îñíîâå ïðåôèêñíûõ äåðåâüåâ (ÈÑ íà îñíî-
âå B+tree îïèñàíû â ðàçä. 5, îá èñïîëüçîâàíèè äðóãèõ äðåâîâèäíûõ ÈÑ äëÿ
ïîèñêà ñòðîê ñì. ïîäðàçä. 4.2).
Ïîäõîä ê ñîçäàíèþ ïðåôèêñíûõ äåðåâüåâ [53], âêëþ÷àþùèé TrieTraverse [54]
è TriePathStack [55], îñíîâàí íà èäåå, ÷òî ñõîäíûå ñòðîêè èìåþò ñõîäíûå ïðåôèê-
ñû. È äåéñòâèòåëüíî, åñëè äëÿ ïðåôèêñîâ äâóõ ñòðîê óæå âûïîëíÿåòñÿ dist edit � r,
ýòè ñòðîêè ìîæíî èñêëþ÷èòü, òàê êàê ïîñëåäóþùèå ñèìâîëû ìîãóò òîëüêî óâåëè-
÷èòü dist edit .
Èç áàçû ñòðîê ôîðìèðóþò ïðåôèêñíîå äåðåâî. Åãî êîðåíü ñîîòâåòñòâóåò ñïåö-
ñèìâîëó «ïóñòàÿ ñòðîêà». Òàê êàê ìíîãèå ñòðîêè èìåþò îäèíàêîâûå ïðåôèêñû, çà-
òðàòû ïàìÿòè ìîæíî îïòèìèçèðîâàòü, íåñìîòðÿ íà ðàñõîäû ïàìÿòè íà êîíñòðóèðî-
âàíèå äåðåâà, îñîáåííî äëÿ ñæàòûõ âàðèàíòîâ ïðåôèêñíîãî äåðåâà. Ýôôåêòèâíîñòü
ïðè âûïîëíåíèè çàïðîñà äîñòèãàåòñÿ çà ñ÷åò èíêðåìåíòíîãî âû÷èñëåíèÿ dist edit ïðè
îáõîäå äåðåâà, ïîâòîðíîãî èñïîëüçîâàíèÿ ðåçóëüòàòîâ âû÷èñëåíèÿ dist edit äëÿ ñòðîê
ñ îáùèì ïðåôèêñîì, ðàññìîòðåíèÿ òîëüêî òåõ ìîäèôèêàöèé ñòðîêè-çàïðîñà, êîòî-
ðûå ñîîòâåòñòâóþò ñòðîêàì áàçû (àíàëîãè÷íî ÈÑ äëÿ dist Ham [4]).
Ñòðîêè ñ îäèíàêîâûìè ïðåôèêñàìè èìåþò îäèíàêîâûå óçëû-ïðåäêè. Ýòî
ìîæíî èñïîëüçîâàòü äëÿ èñêëþ÷åíèÿ íå îäíîé, à ãðóïï ñòðîê. Àêòèâíûå óçëû
äåðåâà — ýòî óçëû, îòëè÷àþùèåñÿ íà dist edit � r â ïðåôèêñàõ ñòðîê, ñîîòâåòñòâó-
þùèõ óçëàì. Åñëè óçåë íå ÿâëÿåòñÿ àêòèâíûì äëÿ âñåõ ïðåôèêñîâ èñõîäíîé
ñòðîêè, äëÿ åãî ïîòîìêîâ dist edit � r. Ïîýòîìó ïðîñòîé àëãîðèòì ïîèñêà çàêëþ÷à-
åòñÿ â âû÷èñëåíèè ïî ñòðîêå-çàïðîñó ìíîæåñòâà àêòèâíûõ óçëîâ.
Ïðè âûïîëíåíèè çàïðîñà èñïîëüçóåòñÿ èíêðåìåíòíàÿ ïðîöåäóðà
TrieTraverse. Äåðåâî îáõîäÿò, ïîñèìâîëüíî ïðèðàùèâàÿ ñòðîêó-çàïðîñ. Ïî ñòðî-
êå, ñîîòâåòñòâóþùåé ïóòè â ïðåôèêñíîì äåðåâå, è ïî ñòðîêå-çàïðîñó ñòðîèòñÿ
ìàòðèöà äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ äëÿ âû÷èñëåíèÿ dist edit è àêòèâàöèè
óçëîâ. Ïî ïðåôèêñàì (åñëè äëÿ íèõ dist edit � r) èñêëþ÷àþò ìíîæåñòâî ïîääåðåâü-
åâ, êîðíåâûå óçëû êîòîðûõ íå ÿâëÿþòñÿ àêòèâíûìè. Åñëè àêòèâíîìó óçëó ñîîò-
âåòñòâóåò ñòðîêà áàçû, äëÿ íåå dist edit � r è, ñëåäîâàòåëüíî, îíà ïðèíàäëåæèò
ïîäìíîæåñòâó ñòðîê áàçû, êîòîðûå ÿâëÿþòñÿ îòâåòîì íà çàïðîñ. Òàêèì îáðàçîì,
íå òðåáóåòñÿ óòî÷íåíèÿ ïðÿìûì âû÷èñëåíèåì ðàññòîÿíèÿ dist edit îò ñòðîêè-çà-
ïðîñà äî ýòèõ ñòðîê (íåîáõîäèìûå dist edit áûëè óæå âû÷èñëåíû èíêðåìåíòíî ïðè
îáõîäå äåðåâà è àêòèâàöèè óçëîâ).
Ðåçóëüòàòû âûïîëíåíèÿ çàïðîñà APSS (ïîèñê âñåõ ñòðîê áàçû ñ dist edit � r)
ìîæíî ïîëó÷èòü, èñïîëüçóÿ â êà÷åñòâå ñòðîê-çàïðîñîâ âñå ñòðîêè áàçû. Îäíàêî
ïðè ýòîì íå ó÷èòûâàåòñÿ òîò ôàêò, ÷òî â áàçå ñòðîê-çàïðîñîâ ìíîãèå ñòðîêè òàêæå
ìîãóò èìåòü îáùèå ïðåôèêñû. Áîëåå ýôôåêòèâíûé àëãîðèòì TriePathStack [55]
ñòðîèò îáùåå ïðåôèêñíîå äåðåâî äëÿ ñòðîê îáåèõ áàç è îïðåäåëÿåò äëÿ êàæäîãî
óçëà îäíîé áàçû àêòèâíûå óçëû èç äðóãîé áàçû.
Íåäîñòàòêè TriePathStack ïðîÿâëÿþòñÿ ïðè ðàáîòå ñ äëèííûìè íåñõîæèìè
ñòðîêàìè. Êîëè÷åñòâî àêòèâíûõ óçëîâ ñòàíîâèòñÿ áîëüøèì. Íàïðèìåð, åñëè
dist edit � 3, òî âñå óçëû ïðåôèêñíîãî äåðåâà íà ïåðâûõ ÷åòûðåõ óðîâíÿõ àêòèâíû.
Ñèòóàöèÿ óñóãóáëÿåòñÿ äëÿ ñòðîê ñ áîëüøèìè àëôàâèòàìè ñèìâîëîâ. Ðàçëè÷íûå ìå-
òîäû èñêëþ÷åíèÿ [55] ïðèìåíÿþòñÿ ïîñëå ñòàäèè ãåíåðàöèè àêòèâíûõ óçëîâ. Îòñþ-
äà áîëüøèå âû÷èñëèòåëüíûå çàòðàòû è çàòðàòû ïàìÿòè, ÷òî äåëàåò ýòè ïîäõîäû íå-
ýôôåêòèâíûìè äëÿ áîëüøèõ áàç, äëèííûõ ñòðîê è áîëüøèõ ïîðîãîâ íà dist edit .
 PreJoin [56] àêòèâíûå óçëû èñêëþ÷àþò íå ïîñëå èõ ãåíåðàöèè, à èñïîëüçó-
þò ïðàâèëà èñêëþ÷åíèÿ â ïðîöåññå ãåíåðàöèè. Äëÿ ýòîãî ãåíåðèðóþò ìíîæåñòâî
àêòèâíûõ óçëîâ íå òîëüêî óçëîâ-ñûíîâåé, íî îäíîâðåìåííî è óçëîâ-âíóêîâ. Ïî-
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5 191
ðÿäîê îáõîäà íåôèêñèðîâàííûé, â ïåðâóþ î÷åðåäü âûÿâëÿþò è ïîñåùàþò «âàæ-
íûå» ïîääåðåâüÿ. Íîâûé ìåòîä ãåíåðàöèè àêòèâíûõ óçëîâ ïðåäíàçíà÷åí äëÿ
óìåíüøåíèÿ èõ êîëè÷åñòâà. Ïðè ýòîì ìèíèìèçèðóþòñÿ çàòðàòû ïàìÿòè è âû÷èñ-
ëèòåëüíûå çàòðàòû íà èñêëþ÷åíèå óæå àêòèâíûõ óçëîâ.
PreJoinPlus [56] îòëè÷àåòñÿ ïðèìåíåíèåì èäåè [49] ðàçáèåíèÿ ñòðîê íà äâå
÷àñòè. Ïî êðàéíåé ìåðå äëÿ îäíîé èç äâóõ ÷àñòåé äîëæíî âûïîëíÿòüñÿ
dist edit � r / 2.  îòëè÷èå îò îáû÷íîãî ïðåôèêñíîãî äåðåâà ìíîæåñòâî êàíäèäà-
òîâ, ïîëó÷åííûõ äëÿ êàæäîé èç äâóõ ÷àñòåé, íåîáõîäèìî óòî÷íèòü. Ñðàâíåíèå
ñ äåðåâüÿìè TrieTraverse, TriePathStack è n-ãðàììíûì ïîäõîäîì EdJoin
(ñì. ïîäðàçä. 4.1) ïîêàçàëî ïðåèìóùåñòâî PreJoinPlus.
4.6. Ïðèçíàêè è ôèëüòðàöèÿ íà îñíîâå ðàçáèåíèÿ ñòðîê áåç ïåðåñå÷åíèÿ.
Êàê îòìå÷àëîñü â ïîäðàçä. 4.5, îáðàòíûé èíäåêñ äëÿ ïåðåêðûâàþùèõñÿ n-ãðàìì
òðåáóåò â íåñêîëüêî ðàç áîëüøå ïàìÿòè, ÷åì õðàíåíèå áàçû. Ðÿä àëãîðèòìîâ
ôèëüòðàöèè èñïîëüçóþò ðàçáèåíèå ïðåäñòàâëåíèÿ îáúåêòà íà íåïåðåñåêàþùèåñÿ
÷àñòè (ñì., íàïðèìåð, [4, 13, 15]). Åñëè dist edit � r è îäíà ñòðîêà ðàçáèòà íà íåïå-
ðåñåêàþùèåñÿ ÷àñòè (ñåãìåíòû), êîëè÷åñòâî êîòîðûõ r �1, òî ïî êðàéíåé ìåðå
îäíà ÷àñòü ñîâïàäàåò ñ íåêîòîðîé ïîäñòðîêîé äðóãîé ñòðîêè [57, 7].  îòëè÷èå îò
÷àñòåé ïîäñòðîêè ïåðåñåêàþòñÿ. Ïðè ýòîì ïîëîæåíèå íà÷àëüíûõ ñèìâîëîâ ÷àñ-
òåé äâóõ ñòðîê îòëè÷àåòñÿ íå áîëåå ÷åì íà r ïîçèöèé (ôèëüòðàöèÿ ïî ïîëîæå-
íèþ). Îïòèìàëüíîå ðàçáèåíèå ìîæåò îïðåäåëÿòüñÿ ñ ó÷åòîì ñòàòèñòèêè âñòðå÷à-
åìîñòè ÷àñòåé ñòðîê.
Ïîèñê â ñòðîêàõ áàçû ïîäñòðîêè, ñîâïàäàþùåé ñ ÷àñòüþ ñòðîêè-çàïðîñà,
ìîæíî âûïîëíèòü ñ ïîìîùüþ îáðàòíîãî èíäåêñà ïîçèöèîííûõ n-ãðàìì [7]. Êàæ-
äóþ ñòðîêó áàçû äîïîëíÿþò n –1 ñïåöñèìâîëîì (ýòî îáåñïå÷èâàåò íàëè÷èå
n-ãðàìì, íà÷èíàþùèõñÿ ñî âñåõ ñèìâîëîâ ñòðîêè) è ñòðîÿò îáðàòíûé èíäåêñ âñåõ
n-ãðàìì, âêëþ÷àþùèé èíôîðìàöèþ îá èõ ïîëîæåíèè â ñòðîêàõ. Äëÿ âñåõ ñòðîê,
èìåþùèõ îïðåäåëåííóþ äëèíó, ñîçäàþò îòäåëüíûé îáðàòíûé èíäåêñ.
Ïðè âûïîëíåíèè çàïðîñà ñòðîêó-çàïðîñ ðàçáèâàþò íà r �1 ÷àñòü áåç ïåðåñå-
÷åíèÿ. Äëÿ êàæäîé ÷àñòè íàõîäÿò ñòðîêè, ñîäåðæàùèå ýòó ÷àñòü, ïðè÷åì â ïîëî-
æåíèè, îòëè÷àþùåìñÿ íå áîëåå ÷åì íà r. Ïðè äëèíå ÷àñòè n ïîèñê òðèâèàëåí
(äëèíà ÷àñòè ðàâíà äëèíå n-ãðàììû è íàäî âûïîëíèòü ïîèñê ïî ñîâïàäåíèþ).
Ïðè äëèíå ÷àñòè, á�ëüøåé n, ðàññìàòðèâàþò âñå âõîäÿùèå â ÷àñòü n-ãðàììû.
Ïî êàæäîé èç íèõ èçâëåêàþò îáðàòíûå ñïèñêè (èäåíòèôèêàòîðû ñòðîê áàçû)
ñ ó÷åòîì îãðàíè÷åíèÿ íà èõ ïîëîæåíèå. Ñòðîêè, êîòîðûå ñîäåðæàòñÿ âî âñåõ èç-
âëå÷åííûõ îáðàòíûõ ñïèñêàõ, ÿâëÿþòñÿ êàíäèäàòàìè íà òî, ÷òî èõ ïîäñòðîêè ñî-
âïàäóò ñ ÷àñòüþ ñòðîêè-çàïðîñà. Äëÿ âûÿâëåíèÿ ðåàëüíîãî ñîâïàäåíèÿ âûïîëíÿ-
þò ïîñèìâîëüíîå ñðàâíåíèå.
Ïðè äëèíå ÷àñòè, ìåíüøåé n, èçâëåêàþò ñòðîêè áàçû, n-ãðàììû êîòîðûõ
èìåþò ïðåôèêñ, ñîâïàäàþùèé ñ ÷àñòüþ (ñ ó÷åòîì îãðàíè÷åíèÿ íà èõ ïîëîæåíèå
â ñòðîêàõ). Òàêèì îáðàçîì íàõîäÿò ñòðîêè áàçû, ñîâïàäàþùèå ñî âñåìè ÷àñòÿìè
ñòðîêè-çàïðîñà. Ýòè ñòðîêè ÿâëÿþòñÿ êàíäèäàòàìè íà óòî÷íåíèå ïðÿìûì âû÷èñ-
ëåíèåì dist edit èëè òî÷íîé ïðîâåðêîé óñëîâèÿ dist edit � r.
Î÷åâèäíî, àëãîðèòì íå ïðèìåíèì ïðè äëèíå ñòðîêè-çàïðîñà, ìåíüøåé r �1.
Êðîìå òîãî, äëÿ ñòðîê äëèíîé, ìåíüøåé 2 1r � , ïðè r îïåðàöèÿõ óäàëåíèÿ ñòðî-
êè-çàïðîñû áóäóò èìåòü êîëè÷åñòâî ñèìâîëîâ, ìåíüøåå r �1. Ïîýòîìó òðåáóåòñÿ
îòäåëüíàÿ ÈÑ äëÿ ñòðîê äëèíîé, ìåíüøåé 2 1r � , è âûïîëíåíèÿ çàïðîñîâ ñ äëèíîé
ñòðîêè-çàïðîñà, ìåíüøåé r �1. Òàê êàê ñòðîêè êîðîòêèå, â ýòîì ñëó÷àå ìîæíî
ïðèìåíÿòü ÈÑ ñ ìîäèôèêàöèåé çàïðîñà (ñì. ïîäðàçä. 4.4).
Àíàëîãè÷íî [4, ïîäðàçä. 2.2.1] è â ñîîòâåòñòâèè ñ ïðèíöèïîì «pigeonhole» [58]
ñóùåñòâóþò âàðèàíòû ÈÑ ñ íàõîæäåíèåì íå òî÷íî ñîâïàäàþùèõ ÷àñòåé. Òàê,
ïðè ðàçáèåíèè ñòðîêè-çàïðîñà íà m
1 íåïåðåñåêàþùèõñÿ ÷àñòåé ïî êðàéíåé
ìåðå îäíà ÷àñòü áóäåò èìåòü dist edit � � �r m/ äî íåêîòîðîé ïîäñòðîêè âòîðîé
192 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5
ñòðîêè, ïðè÷åì ïîëîæåíèÿ ÷àñòè è ïîäñòðîêè îòëè÷àþòñÿ íå áîëåå ÷åì íà r [59].
Äëÿ òàêîãî ïîèñêà ìîæíî èñïîëüçîâàòü íàïðèìåð ñóôôèêñíîå äåðåâî [7], ìîäè-
ôèêàöèþ ñòðîê ñ ïîñëåäóþùèì ïîèñêîì ïî ñîâïàäåíèþ (ñì. ïîäðàçä. 4.4), ïîèñê
ïî íåïåðåñåêàþùèìñÿ n-ãðàììàì ñòðîêè-çàïðîñà [60].
QChunk (IndexGram è IndexChunk) [39] èçâëåêàþò ðàçëè÷íûå ïðèçíàêè èç
ñòðîê áàçû è ñòðîê çàïðîñà — ïåðåñåêàþùèåñÿ è íåïåðåñåêàþùèåñÿ n-ãðàììû.
Ñòðîêè äîïîëíÿþò ñïåöñèìâîëàìè (n �1 ñïåöñèìâîë äëÿ ñòðîê, èç êîòîðûõ èç-
âëåêàþòñÿ ïåðåñåêàþùèåñÿ n-ãðàììû, à ïðè èçâëå÷åíèè íåïåðåñåêàþùèõñÿ
n-ãðàìì ñïåöñèìâîëû îáåñïå÷èâàþò äëèíó n ïîñëåäíåé èç íèõ). Èäåíòè÷íûå
ïðèçíàêè â ðàçëè÷íûõ ïîëîæåíèÿõ ðàññìàòðèâàþòñÿ êàê ðàçíûå. IndexGram èñ-
ïîëüçóåò n-ãðàììû äëÿ ñòðîê áàçû è íåïåðåñåêàþùèåñÿ n-ãðàììû äëÿ ñòðîêè-çà-
ïðîñà, à IndexChunk íàîáîðîò. Äëÿ IndexGram ìèíèìàëüíîå êîëè÷åñòâî ñîâïàäà-
þùèõ ïðèçíàêîâ (íèæíÿÿ ãðàíèöà) ðàâíî
| | /x n r� , à äëÿ IndexChunk îíî ðàâ-
íî
| | /y n r� , ãäå
| | /x n — êîëè÷åñòâî íåïåðåñåêàþùèõñÿ n-ãðàìì â ñòðîêå x.
Àíàëîãè÷íûå óñëîâèÿ ñóùåñòâóþò äëÿ ïðèçíàêîâ ñ ó÷åòîì ïîëîæåíèÿ,
îòëè÷àþùåãîñÿ íå áîëåå ÷åì íà r.
IndexGram è IndexChunk ìîæíî ïðèìåíÿòü è ê ïðåôèêñàì. Ïðè ýòîì äëèíà
ïðåôèêñà äëÿ íåïåðåñåêàþùèõñÿ n-ãðàìì ðàâíà r �1, à äëÿ ïåðåñåêàþùèõñÿ
n-ãðàìì âûðàæåíèå äëÿ äëèíû ïðåôèêñà áîëåå ñëîæíîå. Âíà÷àëå âûïîëíÿåòñÿ
èçâëå÷åíèå ñòðîê áàçû, ñîäåðæàùèõ ïðèçíàê èç ïðåôèêñà, è èõ ôèëüòðàöèÿ ïî
äëèíå è ïî ïîëîæåíèþ, çàòåì — äîïîëíèòåëüíàÿ ôèëüòðàöèÿ ñ ó÷åòîì îïèñàí-
íûõ ðàíåå íèæíèõ ãðàíèö ñ äàëüíåéøèìè îïòèìèçàöèÿìè.
PassJoin [36] ðàçáèâàþò ñòðîêó íà r �1 ÷àñòü áåç ïåðåñå÷åíèÿ (ñåãìåíò). Åñëè
êàêàÿ-òî ñòðîêà èìååò ñ ýòîé ñòðîêîé dist edit � r, òî ó íåå äîëæíà áûòü ïîäñòðî-
êà, ñîâïàäàþùàÿ ñ ñåãìåíòîì ïåðâîé ñòðîêè. Èñïîëüçóþò ðàçáèåíèå ñòðîê áàçû
íà ïî÷òè ðàâíûå ñåãìåíòû, îòëè÷àþùèåñÿ ïî äëèíå íå áîëåå ÷åì íà 1. Ïî íèì
ñòðîÿò îáðàòíûé èíäåêñ, â êîòîðîì îáðàòíûå ñïèñêè ôîðìèðóþò äëÿ ñòðîê îäè-
íàêîâîé äëèíû. Ïðåäëîæåí òàêæå àëãîðèòì ðàçáèåíèÿ ñòðîêè çàïðîñà íà ïîä-
ñòðîêè, ìèíèìèçèðóþùèé êîëè÷åñòâî ïîäñòðîê, ïî êîòîðûì âûïîëíÿåòñÿ
çàïðîñ, áåç ïîòåðè êàíäèäàòîâ (ò.å. áåç false negatives).
Íà ýòàïå óòî÷íåíèÿ ñïèñêà êàíäèäàòîâ ñòðîêè ðàçáèâàþò íà ÷àñòè (ñîâïàäà-
þùóþ, ëåâóþ, ïðàâóþ) è èñïîëüçóþò ïîðîãè äëÿ èñêëþ÷åíèÿ ñòðîê. Òàê, äëÿ ñî-
îòâåòñòâèÿ çàïðîñó rNN äîëæíî âûïîëíÿòüñÿ dist edit � �i 1 äëÿ ëåâîé ÷àñòè è
dist edit � � �r i1 äëÿ ïðàâîé ÷àñòè, ãäå i — íîìåð ñåãìåíòà ñòðîêè, ïî êîòîðîìó
îíà èçâëå÷åíà èç îáðàòíîãî ñïèñêà. Îòìåòèì, ÷òî âåëè÷èíû ïîðîãîâ äëÿ èñêëþ-
÷åíèÿ ÷àñòåé ìåíüøå âåëè÷èí ïîðîãîâ äëÿ èñêëþ÷åíèÿ öåëûõ ñòðîê, ÷òî ïîòåí-
öèàëüíî ïîçâîëÿåò ïîëó÷èòü áîëåå ýôôåêòèâíîå èñêëþ÷åíèå.  ýêñïåðèìåíòàõ
äëÿ äëèííûõ ñòðîê [8] PassJoin îêàçàëñÿ áûñòðåå ÈÑ Bed-tree, ListMerger,
PartEnum, AllPair, PPJoin, EDJoin, QChunk, VChunk, AdaptJoin, PassJoin, TrieJoin,
FastSS, M-Tree. Äëÿ êîðîòêèõ ñòðîê êîíêóðåíòîñïîñîáåí òàêæå FastSS
(ñì. ïîäðàçä. 4.4), íî ïðè áîëüøèõ çàòðàòàõ ïàìÿòè.
ÈÑ Pivotal [48] òàêæå èñïîëüçóåò êîëè÷åñòâî íåïåðåñåêàþùèõñÿ n-ãðàìì,
ðàâíîå r �1, íî èç ïðåôèêñà äëèíîé nr �1 (ñì. ïîäðàçä. 4.3). Êàê îáû÷íî, n-ãðàì-
ìû ïðåôèêñà îòñîðòèðîâàíû â ãëîáàëüíîì ïîðÿäêå (â Pivotal — ïî ÷àñòîòå
âñòðå÷àåìîñòè). Åñëè ïîñëåäíÿÿ n-ãðàììà ïðåôèêñà ñòðîêè b ïðåäøåñòâóåò ïî-
ñëåäíåé n-ãðàììå ïðåôèêñà ñòðîêè a , òî ñðåäè íåïåðåñåêàþùèõñÿ n-ãðàìì ïðå-
ôèêñà b (ïðè ëþáîì ðàçáèåíèè íà r �1 ÷àñòü) äîëæíà íàéòèñü ïî êðàéíåé ìåðå
îäíà, ñîâïàäàþùàÿ ñ n-ãðàììîé ïðåôèêñà a .
Ïî áàçå, îòñîðòèðîâàííîé ïî äëèíå ñòðîê, ñòðîÿò äâà îáðàòíûõ èíäåêñà: äëÿ
ïðåôèêñíûõ ïîçèöèîííûõ n-ãðàìì ñ ïåðåñå÷åíèåì è áåç íåãî. Äëÿ ðàáîòû ñ ïå-
ðåìåííûì ïîðîãîì r îáðàòíûå èíäåêñû ðåàëèçîâàíû êàê èíêðåìåíòíûå: êàæäûé
ïîñëåäóþùèé îáðàòíûé èíäåêñ ñîîòâåòñòâóåò áîëüøåìó çíà÷åíèþ r è âêëþ÷àåò
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5 193
îáúåêòû, íå âîøåäøèå â ïðåäøåñòâóþùèå îáðàòíûå èíäåêñû. Ïðè âûïîëíåíèè
çàïðîñà èñïîëüçóþò ïðåôèêñíûå n-ãðàììû ñòðîêè-çàïðîñà ñ ïåðåñå÷åíèåì è áåç
íåãî, âûïîëíÿÿ ïîèñê â ñîîòâåòñòâóþùèõ îáðàòíûõ èíäåêñàõ. Ñ êàæäîé n-ãðàì-
ìîé â ÈÑ àññîöèèðîâàíû äëèíû ñòðîê, êîòîðûì îíà ïðèíàäëåæèò, ÷òî ïîçâîëÿåò
âûïîëíÿòü ôèëüòðàöèþ ïî äëèíå (ñì. ïîäðàçä. 4.1).
Íåïåðåñåêàþùèåñÿ n-ãðàììû ìîæíî âûáèðàòü â ïðåôèêñå ðàçëè÷íûìè ñïî-
ñîáàìè. Äëÿ âûáîðà âûñîêîêà÷åñòâåííûõ íåïåðåñåêàþùèõñÿ n-ãðàìì ïðåôèêñà
(ñ êîðîòêèìè îáðàòíûìè ñïèñêàìè è ñîîòâåòñòâåííî ñ áîëüøåé ýôôåêòèâíîñòüþ
èñêëþ÷åíèÿ) èñïîëüçóþò äèíàìè÷åñêîå ïðîãðàììèðîâàíèå. Ýòî ïîçâîëÿåò ýô-
ôåêòèâíî èñêëþ÷àòü ñòðîêè, â êîòîðûõ ñèìâîëû, îòëè÷àþùèåñÿ îò ñòðîêè-çà-
ïðîñà, ðàñïîëîæåíû íåïîñëåäîâàòåëüíî.
×òîáû èñêëþ÷èòü áîëüøîå êîëè÷åñòâî íåñõîäíûõ ñòðîê, â êîòîðûõ ñèìâî-
ëû, îòëè÷àþùèåñÿ îò ñòðîêè-çàïðîñà, ðàñïîëîæåíû ïîñëåäîâàòåëüíî, èñïîëüçó-
þò ôèëüòð ïîñòàíîâêè â ñîîòâåòñòâèå (alignment filter), îñíîâàííûé íà ñëåäóþ-
ùåì óòâåðæäåíèè. Íàéäåì ñóììó ìèíèìàëüíûõ ðàññòîÿíèé ðåäàêòèðîâàíèÿ
ìåæäó êàæäîé èç ìíîæåñòâà íåïåðåñåêàþùèõñÿ n-ãðàìì (èõ r �1) ïðåôèêñà îä-
íîé ñòðîêè (ñ íà÷àëüíûì ïîëîæåíèåì pos i ) è ëþáîé ïîäñòðîêîé âòîðîé ñòðîêè.
Åñëè äëÿ äâóõ ñòðîê dist edit � r, òî ýòà ñóììà íå ïðåâûøàåò r. Ïðè ýòîì ïîçèöè-
îííûé ôèëüòð (ñì. ïîäðàçä. 4.1) ïîçâîëÿåò îãðàíè÷èòü âòîðóþ ñòðîêó ñèìâîëà-
ìè, ðàñïîëîæåííûìè ìåæäó pos i r� è pos i n r� � �1 . Òàê êàê ñëîæíîñòü âû÷èñ-
ëåíèÿ dist edit âåëèêà, â alignment filter èñïîëüçóþò íèæíþþ ãðàíèöó íà îñíîâå
dist Ham ìåæäó áèíàðíûìè âåêòîðàìè ñèìâîëîâ (ñì. ïîäðàçä. 4.2).
Êîìáèíàöèÿ ñ pigeonring [58] óñêîðÿåò Pivotal äî 3.1 è 3.9 ðàç. Âîçìîæíî,
ýòî ñàìàÿ áûñòðàÿ ÈÑ äëÿ ïîèñêà ñòðîê â íàñòîÿùåå âðåìÿ.
5. ÏÎÈÑÊ ÁËÈÆÀÉØÈÕ ÑÎÑÅÄÅÉ
Ïðè ðàáîòå ñî ñòðîêàìè âûïîëíåíèå çàïðîñà kNN îáû÷íî íàçûâàþò top-k
similarity search. Ðàññìîòðèì ÈÑ äëÿ âûïîëíåíèÿ çàïðîñîâ ïîèñêà ïðèáëèæåí-
íîãî áëèæàéøåãî ñîñåäà ñ òåîðåòè÷åñêèìè ãàðàíòèÿìè (ïîäðàçä. 5.1) è ïðàê-
òè÷åñêèå ÈÑ äëÿ òî÷íîãî ïîèñêà, íî áåç òåîðåòè÷åñêèõ ãàðàíòèé ñóáëèíåéíî-
ãî âðåìåíè (ïîäðàçä. 5.2).
5.1. Ïðèáëèæåííûé ïîèñê ñ òåîðåòè÷åñêèìè ãàðàíòèÿìè. Äëÿ âûïîëíå-
íèÿ çàïðîñà ( , )c � -NN ïî dist edit ñ ñóùåñòâåííî ñóáëèíåéíûì âðåìåíåì èñïîëüçó-
þò âëîæåíèÿ ñòðîê, à òàêæå ÈÑ äëÿ ïîëó÷åííûõ âåêòîðîâ. Îòìåòèì, ÷òî ÈÑ,
îïèñàííûå â ýòîì ðàçäåëå, íå ðåàëèçîâàíû íà ïðàêòèêå.
Òàê, â [61] èñïîëüçóþò âëîæåíèå ñòðîê â âåêòîðíîå ïðîñòðàíñòâî ñ dist Man
íà îñíîâå ðàçáèåíèÿ èñõîäíûõ ñòðîê íà íåïåðåñåêàþùèåñÿ ïîäñòðîêè è èõ ñäâè-
ãîâ, äëÿ ýòîãî âëîæåíèÿ ñ âûñîêîé âåðîÿòíîñòüþ âûïîëíÿåòñÿ îãðàíè÷åíèå íà
èñêàæåíèå ðàññòîÿíèé. Çàòåì ïðèìåíÿþò ÈÑ äëÿ âûïîëíåíèÿ âåðîÿòíîñòíûõ
ïðèáëèæåííûõ çàïðîñîâ ïî dist Man (íàïðèìåð, [62] èëè ÈÑ LSH äëÿ dist Man ,
ñì. ññûëêè â [11, 12] è â ïîäðàçä. 3.2).  ðåçóëüòàòå ïîëó÷àþò èòîãîâóþ ÈÑ äëÿ
ïîèñêà ñòðîê ïî dist edit ñ çàòðàòàìè ïàìÿòè ( ) ( )DN O 1 è âðåìåíåì âûïîëíåíèÿ çà-
ïðîñà ( log ) ( )D N O 1 ïðè ìíîæèòåëå àïïðîêñèìàöèè 2
O D D(log log log )
, ãäå D —
äëèíà ñòðîêè.
ÈÑ äëÿ dist edit [63] îñíîâàíà íà ÈÑ äëÿ ïðèáëèæåííîãî ïîèñêà ïî ìåòðèêå
sum-product [11], â êîòîðîé ìåòðèêàìè-êîìïîíåíòàìè ÿâëÿþòñÿ dist edit êîðîòêèõ
÷àñòåé ñòðîê. ÈÑ äëÿ ïîèñêà áëèæàéøåãî ñîñåäà ìîæíî ïîñòðîèòü äëÿ êîðîòêèõ
ñòðîê çàïîìèíàíèåì áëèæàéøåãî ñîñåäà äëÿ âñåõ âîçìîæíûõ çàïðîñîâ [4]. Ýòî
îáåñïå÷èâàåò âðåìÿ âûïîëíåíèÿ çàïðîñà O D( ) ñ ýêñïîíåíöèàëüíûìè çàòðàòàìè ïà-
ìÿòè ( | | ) ( )DN O D�
�
, � � 0, è ïîñòîÿííûì ìíîæèòåëåì àïïðîêñèìàöèè. Ïðè ìíî-
æèòåëå àïïðîêñèìàöèè D � ìîæíî ïîëó÷èòü ïîëèíîìèàëüíûå çàòðàòû ïàìÿòè.
194 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5
Èñïîëüçóþòñÿ äâà ïðåîáðàçîâàíèÿ: ðàçáèåíèå äëèííîé ñòðîêè íà êîðîòêèå, ïîçâîëÿ-
þùåå âû÷èñëèòü èñõîäíîå dist edit , à òàêæå âëîæåíèå sum-product â max-product, êî-
òîðîå âûïîëíÿåòñÿ ñ èñêàæåíèåì è âåðîÿòíîñòüþ, äîñòàòî÷íûìè äëÿ ïîèñêà áëè-
æàéøåãî ñîñåäà ïî sum-product ÷åðåç ÈÑ äëÿ ïîèñêà ïî max-product [64].
Äëÿ ïðèáëèæåííîãî ïîèñêà ïî ìåòðèêå Óëàìà (dist edit íà ñòðîêàõ áåç ïîâòî-
ðÿþùèõñÿ ñèìâîëîâ) ïðèìåíÿþò [65] âëîæåíèå ñòðîê ñ ïîñòîÿííûì èñêàæåíèåì
â âåêòîðû èç iterated product space � �
�( )L
D
L
O D DL
2
2 1
2(log ) ñ ðàññòîÿíèåì ìåæäó âåê-
òîðàìè dist NEG, ,1� ( , )a b . Ýòî çàáûâ÷èâîå âëîæåíèå îòîáðàæàåò ñòðîêè â òùà-
òåëüíî ïîäîáðàííûé íàáîð õàðàêòåðèñòè÷åñêèõ âåêòîðîâ èõ ïîäñòðîê (ò.å. ÷àñ-
òåé ñòðîê ñî ñìåæíûìè ñèìâîëàìè). Èñïîëüçîâàíèå ÈÑ (êîòîðóþ ìîæíî ñ÷èòàòü
îáîáùåíèåì ÈÑ LSH äëÿ dist Man ), ðàçðàáîòàííîé äëÿ ïðèáëèæåííîãî ïîèñêà ïî
ìåòðèêå iterated product space (è âåðîÿòíîñòíîãî ïðèáëèæåííîãî âëîæåíèÿ), ïî-
çâîëèëî ïîëó÷èòü ëó÷øèé èçâåñòíûé àëãîðèòì ïîèñêà ïî ìåòðèêå Óëàìà ñ àï-
ïðîêñèìàöèåé O N(log log ) è ñ âîçìîæíîñòüþ óëó÷øåíèÿ äî O D(log log ) [65].
Êîíêðåòíåå, ýòà òåîðåòè÷åñêàÿ ÈÑ îáåñïå÷èâàåò âðåìÿ âûïîëíåíèÿ çàïðîñà
D NO ( )1 � è çàòðàòû ïàìÿòè ( ) ( )DN O 1 ïðè âåëè÷èíå ìíîæèòåëÿ àïïðîêñèìàöèè
c O N� �( log log )� 3 äëÿ ëþáîãî � � 0. Îòìåòèì, ÷òî âëîæåíèå ìåòðèêè Óëàìà
ñ ïîñòîÿííûì èñêàæåíèåì â áîëåå ïðîñòûå ïðîñòðàíñòâà, íàïðèìåð â L1,
íåâîçìîæíî [65].
ÈÑ äëÿ âûïîëíåíèÿ ïðèáëèæåííûõ çàïðîñîâ kNN ïî dist edit íà îñíîâå âëî-
æåíèÿ â âåêòîðíîå ïðîñòðàíñòâî ñ dist Man [28, 29] è LSH-forest óïîìèíàëàñü
â ïîäðàçä. 3.2.
5.2. Ïðàêòè÷åñêèé òî÷íûé ïîèñê áåç òåîðåòè÷åñêèõ ãàðàíòèé. Äàæå åñëè
ÈÑ ïîçâîëÿåò âûïîëíÿòü çàïðîñû rNN c ïåðåìåííûì r, ðåàëèçàöèÿ çàïðîñîâ kNN
ïîñëåäîâàòåëüíîñòüþ çàïðîñîâ rNN ñ ðàçëè÷íûìè r (ñì. ïîäðàçä. 1.2) î÷åíü òðó-
äîåìêà. Ïîýòîìó ðàçðàáàòûâàþòñÿ äðóãèå ðåøåíèÿ äëÿ çàïðîñîâ kNN, îáû÷íî
áåç òåîðåòè÷åñêèõ ãàðàíòèé.
 ÈÑ AQ [66] ïðåäëîæåí îäèí èç ïåðâûõ àëãîðèòìîâ äëÿ âûïîëíåíèÿ òî÷-
íîãî çàïðîñà kNN ïî dist edit . Ôèëüòðàöèÿ âûïîëíÿåòñÿ ïî ïîðîãîâîìó çíà÷åíèþ
T êîëè÷åñòâà ñîâïàäàþùèõ n-ãðàìì è ïî îòëè÷èþ äëèíû ñòðîê (ñì. ïîä-
ðàçä. 4.1), êîòîðûå èçìåíÿþò â ïðîöåññå âûïîëíåíèÿ çàïðîñà.
Ñòðîêè ðàçíîé äëèíû çàïîìèíàþò â ðàçëè÷íûõ îáðàòíûõ èíäåêñàõ. Ïðè âû-
ïîëíåíèè çàïðîñà óñòàíàâëèâàþò length diff � 0, T �1. Èçâëåêàþò ñòðîêè y, äëÿ
êîòîðûõ | | | | | |y x� � length diff . Äëÿ íèõ ñ èñïîëüçîâàíèåì ïîðîãà T íàõîäÿò ñòðî-
êè-êàíäèäàòû, ðàíæèðóþò èõ ïî dist edit è ïîëó÷àþò k òåêóùèõ áëèæàéøèõ ñîñå-
äåé. Åñëè ðàññòîÿíèå îò îáúåêòà-çàïðîñà äî k-ãî òåêóùåãî áëèæàéøåãî ñîñåäà íå
ïðåâûøàåò length diff �1, áëèæàéøèå k ñòðîê ÿâëÿþòñÿ îòâåòîì íà çàïðîñ. Â ïðî-
òèâíîì ñëó÷àå âû÷èñëÿþò çíà÷åíèå ïîðîãà T , ñîîòâåòñòâóþùåå òåêóùåìó ðàäèó-
ñó çàïðîñà, óâåëè÷èâàþò çíà÷åíèå length diff íà 1 è ïîâòîðÿþò ïðîöåäóðó. Êðîìå
òîãî, â n-ãðàììàõ èçìåíÿþò çíà÷åíèå n (âû÷èñëÿþò èç ôîðìóëû äëÿ òåêóùåãî
çíà÷åíèÿ T). Ïðè ýòîì n óâåëè÷èâàåòñÿ, ÷òî óìåíüøàåò ðàçìåðû îáðàòíûõ ñïèñ-
êîâ è îáùåå âðåìÿ âûïîëíåíèÿ çàïðîñà. Íåäîñòàòêîì ÈÑ AQ ÿâëÿåòñÿ áîëüøèå
çàòðàòû ïàìÿòè íà îáðàòíûå èíäåêñû äëÿ n-ãðàìì ðàçëè÷íîé äëèíû.
ÈÑ Bed-tree [67] ïîñòðîåíà íà îñíîâå Â+tree. Ýòî òðåáóåò óïîðÿäî÷åíèÿ ñòðîê
íà îñíîâå ãëîáàëüíîãî ïîðÿäêà. Íàïðèìåð, òàêîé ïîðÿäîê çàäàåòñÿ ñîðòèðîâêîé
ñòðîê ïî äëèíå, à çàòåì óïîðÿäî÷åíèåì â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå. Ïðè ýòîì
ïîëåçíàÿ èíôîðìàöèÿ ñîäåðæèòñÿ òîëüêî â ïðåôèêñàõ ñòðîê. Áîëüøå èíôîðìàöèè
îáåñïå÷èâàåò ïîðÿäîê n-ãðàìì. Õýø-ôóíêöèÿ îòîáðàæàåò êàæäóþ n-ãðàììó â õýø-
çíà÷åíèå (âîçìîæíû êîëëèçèè). Çàòåì ïîëó÷åííûé õýø-âåêòîð ñòðîêè îòîáðàæàþò
â çíà÷åíèå Z-ïîðÿäêà [68]. Äëÿ óïîðÿäî÷åíèÿ n-ãðàìì â äîïîëíåíèå ê õýø-çíà÷åíèþ
èñïîëüçóåòñÿ èíôîðìàöèÿ îá èõ ïîëîæåíèè (ñì. ïîäðàçä. 4.1).
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5 195
Ïðèìåíåíèå òàêèõ óïîðÿäî÷åíèé ïîçâîëÿåò âû÷èñëèòü íèæíþþ ãðàíèöó
dist edit ìåæäó ñòðîêîé-çàïðîñîì è ñòðîêàìè áàçû â èíòåðâàëå ñòðîê, çàäàííîì
êîíêðåòíûì ïîðÿäêîì, è âûïîëíÿòü çàïðîñû ïîèñêà ïî ñõîäñòâó ñ ïîìîùüþ
Â+tree. Òàê, ïðè âûïîëíåíèè çàïðîñà rNN àëãîðèòì ðåêóðñèâíî ïîñåùàåò óçëû
Â+tree ñ íèæíåé ãðàíèöåé dist edit íå áîëåå r è èñïîëüçóåò ñòðîêè èç ëèñòîâûõ
óçëîâ â êà÷åñòâå êàíäèäàòîâ. Îòìåòèì, ÷òî ïåðåõîä ìîæåò ïðîèñõîäèòü ñðàçó
â íåñêîëüêî óçëîâ. Çàïðîñ kNN âûïîëíÿåòñÿ ïîñðåäñòâîì ìîäèôèêàöèè ïîðîãà
â âåëè÷èíó ðàññòîÿíèÿ äî òåêóùåãî k-ãî áëèæàéøåãî ñîñåäà.
Ê íåäîñòàòêàì Bed-tree îòíîñèòñÿ ìàëàÿ ýôôåêòèâíîñòü ïîèñêà äëÿ êîðîòêèõ
ñòðîê áàçû (ïîèñê âûðîæäàåòñÿ âî ìíîæåñòâî ëèíåéíûõ ïîèñêîâ íà ÷àñòÿõ
Â+tree). Êðîìå òîãî, êàæäîå èçìåíåíèå ïîðîãà ïðè çàïðîñå kNN òðåáóåò âû÷èñ-
ëåíèÿ áîëüøîãî êîëè÷åñòâà ðàññòîÿíèé dist edit äî ñòðîê-êàíäèäàòîâ.
ÈÑ PBI íà îñíîâå B+tree [69] ÿâëÿåòñÿ àíàëîãîì ìåòðè÷åñêîé ÈÑ iDistance
[70], íî äëÿ ñòðîê ñ dist edit . Ïðåäëîæåíû ýâðèñòèêè âûáîðà îïîðíûõ îáúåê-
òîâ-ñòðîê è ïðèñâîåíèÿ èõ îáëàñòÿì äðóãèõ ñòðîê áàçû òàêèì îáðàçîì, ÷òîáû ìè-
íèìèçèðîâàòü êîëè÷åñòâî êàíäèäàòîâ. Õîòÿ PBI ïðåâîñõîäèò ÈÑ Flamingo [47]
è Bed-tree â áîëüøèíñòâå ýêñïåðèìåíòîâ, äëÿ î÷åíü äëèííûõ ñòðîê âñå ýòè àëãî-
ðèòìû ðàáîòàþò ïëîõî.
 ÈÑ Range [71] ïîâûøàþò ýôôåêòèâíîñòü àëãîðèòìà äèíàìè÷åñêîãî ïðîãðàì-
ìèðîâàíèÿ äëÿ âû÷èñëåíèÿ dist edit çà ñ÷åò âû÷èñëåíèÿ íå âñåõ ýëåìåíòîâ ìàòðèöû,
èñïîëüçóåìîé â äèíàìè÷åñêîì ïðîãðàììèðîâàíèè. Äóáëèðîâàíèÿ âû÷èñëåíèé èçáå-
ãàþò ãðóïïèðîâàíèåì ýëåìåíòîâ, ñîîòâåòñòâóþùèõ îáùèì ïîäñòðîêàì.
 õîäå îáðàáîòêè çàïðîñà áûñòðî íàõîäÿò ñòðîêè ñ ìàëûì dist edit äî ñòðî-
êè-çàïðîñà è èñïîëüçóþò ýòè ðàññòîÿíèÿ â êà÷åñòâå ãðàíèö. ×òîáû íå âûïîëíÿòü
ìíîæåñòâî çàïðîñîâ rNN ñ ðàçëè÷íûìè ïîðîãîâûìè çíà÷åíèÿìè r, ïðèìåíÿþò
ïðåôèêñíîå äåðåâî (ñì. ïîäðàçä. 4.5). Íàõîäÿò ïðåôèêñû, ñîâïàäàþùèå ñî ñòðî-
êîé-çàïðîñîì èëè îòëè÷àþùèåñÿ íà íåêîòîðîå çíà÷åíèå dist edit (àêòèâíûå óçëû,
ñì. ïîçäðàçä. 4.5). Çàòåì èç óçëîâ, ñîîòâåòñòâóþùèõ ýòèì ïðåôèêñàì, ïðîäîëæà-
þò îáõîä äåðåâà (ñ òåì æå èëè óâåëè÷èâàþùèìñÿ çíà÷åíèåì dist edit ), ïîêà íå ïî-
ñåòÿò k ëèñòüåâ. Ñòðîêè â íèõ ÿâëÿþòñÿ áëèæàéøèìè ñîñåäÿìè (ò.å. íå òðåáóåòñÿ
èõ óòî÷íåíèÿ âû÷èñëåíèåì äî íèõ ðàññòîÿíèé dist edit ).  ýêñïåðèìåíòàõ
ïîêàçàíî ïðåèìóùåñòâî íàä Flamingo, AQ, Bed-tree.
Range îáåñïå÷èâàåò ýôôåêòèâíîå èñêëþ÷åíèå äëÿ êîðîòêèõ ñòðîê. Äëÿ äëèí-
íûõ ñòðîê êîëè÷åñòâî îáùèõ ïðåôèêñîâ óìåíüøàåòñÿ è ýòî ñíèæàåò ýôôåêòèâíîñòü
ïðîöåäóðû èñêëþ÷åíèÿ. Êðîìå òîãî, ÈÑ íà îñíîâå ïðåôèêñíûõ äåðåâüåâ ñëîæíû
â êîíñòðóèðîâàíèè è ïðåäíàçíà÷åíû òîëüêî äëÿ ðàáîòû ñ áûñòðîé ïàìÿòüþ.
ÈÑ AppGram [72] ïðåäëàãàåò ñòðàòåãèþ ôèëüòðàöèè íà îñíîâå êîëè÷åñòâà
n-ãðàìì íå ñ ïîëíûì, à ñ ïðèáëèæåííûì ñîâïàäåíèåì. Ýòî ïîçâîëÿåò èñïîëüçî-
âàòü áîëåå äëèííûå n-ãðàììû è óìåíüøèòü ÷èñëî false positives. Ïðèìåíÿåòñÿ
äâóõóðîâíåâûé îáðàòíûé èíäåêñ. Âåðõíèé óðîâåíü ðàáîòàåò ñ n-ãðàììàìè, èí-
äåêñèðóþùèìè ñòðîêè, íèæíèé — ñ ÷àñòÿìè n-ãðàìì, èíäåêñèðóþùèìè n-ãðàì-
ìû. Ïðè ïîñòóïëåíèè çàïðîñà ïî åãî n-ãðàììàì íèæíèé îáðàòíûé èíäåêñ íàõî-
äèò ñõîäíûå n-ãðàììû ñ dist edit � t ìåæäó n-ãðàììàìè íà îñíîâå ïîäñ÷åòà ñî-
âïàâøèõ ÷àñòåé n-ãðàìì. Çàòåì ýòè n-ãðàììû èñïîëüçóþò äëÿ ïîëó÷åíèÿ ñïèñêîâ
ñòðîê-êàíäèäàòîâ íà âåðõíåì óðîâíå ïðè âîçðàñòàþùèõ çíà÷åíèÿõ t. Ê ñïèñêàì
ñòðîê-êàíäèäàòîâ ïðèìåíÿþò ôèëüòðû. Åñëè ñòðîêè a, b èìåþò dist edit � r, òî
ó íèõ äîëæíî áûòü íå ìåíåå max (| | , | | ) max ( , ) ( )( )a b n n t n t r� � � � � � �1 1 2 1 òà-
êèõ n-ãðàìì, ðàññòîÿíèå ìåæäó êîòîðûìè dist edit � t . Áîëåå ïëîòíóþ íèæíþþ
ãðàíèöó dist edit äàåò ðàññòîÿíèå íà îñíîâå îïòèìàëüíîãî îòîáðàæåíèÿ ìåæäó
ìóëüòèìíîæåñòâàìè n-ãðàìì [72]. Òåêóùåå çíà÷åíèå r ðàâíî dist edit îò
îáúåêòà-çàïðîñà äî k-ãî òåêóùåãî áëèæàéøåãî ñîñåäà.
Çàòðàòû ïàìÿòè è âðåìÿ êîíñòðóèðîâàíèÿ AppGram áîëüøå, ÷åì ó Bed-tree,
íî ìåíüøå, ÷åì ó Flamingo. Âðåìÿ âûïîëíåíèÿ çàïðîñà ïðè k
2 ìåíüøå, ÷åì
196 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5
ó Flamingo, Bed-tree, Range, à ïðè k �1 Flamingo è Range áûñòðåå. Âðåìÿ óòî÷íå-
íèÿ êàíäèäàòîâ äîìèíèðóåò âî âðåìåíè âûïîëíåíèÿ çàïðîñà.
ÈÑ HS-tree [73] âûïîëíÿåò çàïðîñû rNN è kNN. Ñòðîêè ãðóïïèðóþò ïî äëèíå.
Äëÿ êàæäîé ãðóïïû ñòðîê êîíñòðóèðóþò ïîëíîå áèíàðíîå äåðåâî. Â êàæäîì óçëå
äåðåâà (ïîä)ñòðîêó ðàçáèâàþò íà äâå íåïåðåñåêàþùèåñÿ ÷àñòè (ðàâíîé èëè îòëè÷à-
þùåéñÿ íà åäèíèöó äëèíû), ïðåôèêñ è ñóôôèêñ. Ðàçáèåíèå ïðîâîäÿò ðåêóðñèâíî äî
äîñòèæåíèÿ îäíîãî ñèìâîëà â ñåãìåíòå. Â êàæäîì óçëå õðàíÿò îáðàòíûé èíäåêñ åãî
ñåãìåíòîâ (ñî ñòðîêàìè áàçû, êîòîðûì ïðèíàäëåæàò ñåãìåíòû).
Ïðè âûïîëíåíèè çàïðîñà rNN ôèëüòðó ïî äëèíå óäîâëåòâîðÿþò èíäåêñíûå
ñòðóêòóðû HS-tree äëÿ ñòðîê äëèíîé îò | |x r� äî | |x r� . Íà i-ì óðîâíå (êàê îáû÷-
íî, äåðåâî «ðàñòåò» âíèç, ò.å. ðàñïîëîæåííûé íèæå óðîâåíü èìååò á�ëüøåå çíà-
÷åíèå i) ñòðîêè ðàçáèòû íà 2 i ñåãìåíòîâ. Äëÿ 2 1i r
� ñòðîêà áàçû íå ìîæåò ÿâ-
ëÿòüñÿ îòâåòîì íà çàïðîñ, åñëè ñòðîêà-çàïðîñ íå èìååò îáùåãî ñåãìåíòà ñî ñòðî-
êîé áàçû (èñêëþ÷åíèå ïî ïðèíöèïó pigåonhole [58]). Áîëåå òîãî, â ñòðîêå-çàïðîñå
äîëæíî áûòü íå ìåíåå 2 i r� ñåãìåíòîâ ñòðîêè áàçû, ÷òîáû ïîñëåäíÿÿ ñòàëà îáú-
åêòîì-êàíäèäàòîì. Òàê êàê ñ óâåëè÷åíèåì íîìåðà óðîâíÿ óìåíüøàåòñÿ ðàçìåð
ñåãìåíòà è ýôôåêòèâíîñòü èñêëþ÷åíèÿ, èñïîëüçóþò óðîâåíü
log( )r �1 . Äëÿ äî-
ïîëíèòåëüíîé ôèëüòðàöèè ïðèìåíÿþò ðàçíèöó â ïîëîæåíèè ñåãìåíòîâ è äëèíàõ
ñòðîê (ñì. ïîäðàçä. 4.1).
Äîïîëíèòåëüíî êîëè÷åñòâî êàíäèäàòîâ óìåíüøàþò óñòðàíåíèåì «êîíôëèê-
òîâ», êîòîðûå çàêëþ÷àþòñÿ â òîì, ÷òî ñåãìåíòû ñòðîêè-çàïðîñà äîëæíû áûòü íå-
ïåðåñåêàþùèìèñÿ. Äëÿ ýòîãî èñïîëüçóþò äèíàìè÷åñêîå ïðîãðàììèðîâàíèå [36].
Ïðè óòî÷íåíèè êàíäèäàòîâ âìåñòî âû÷èñëåíèÿ çíà÷åíèÿ dist edit ïðèìåíÿþò ýô-
ôåêòèâíûé àëãîðèòì ñðàâíåíèÿ ñ r íà îñíîâå èíäèâèäóàëüíûõ ïîðîãîâûõ
çíà÷åíèé äëÿ ñåãìåíòîâ.
Ïðè âûïîëíåíèè çàïðîñà kNN äëÿ êàæäîãî óðîâíÿ ïðîâåðÿþò óñëîâèå
2 11i� �
�dist edit , ãäå dist edit
� — ðàññòîÿíèå äî òåêóùåãî k-ãî áëèæàéøåãî ñîñåäà.
Åñëè óñëîâèå âûïîëíÿåòñÿ, ïîèñê ïðåêðàùàþò, ïðè ýòîì íàéäåííûå òåêóùèå áëè-
æàéøèå ñîñåäè ÿâëÿþòñÿ èñòèííûìè.  ïðîòèâíîì ñëó÷àå íàõîäÿò ñòðîêè áàçû, äëÿ
êîòîðûõ êîëè÷åñòâî ñîâïàâøèõ ïîäñòðîê áîëüøå èëè ðàâíî 2 i � �dist edit . Ñòðîêè
ãðóïïèðóþò ïî çíà÷åíèÿì ýòîãî êîëè÷åñòâà è ïîñåùàþò òàêèå ãðóïïû â ïîðÿäêå åãî
óìåíüøåíèÿ. Äëÿ êàæäîé ñòðîêè âû÷èñëÿþò èñòèííîå dist edit è ìîäèôèöèðóþò
ïðèîðèòåòíóþ î÷åðåäü òåêóùèõ áëèæàéøèõ ñîñåäåé è dist edit
� , åñëè âñòðå÷àþòñÿ
ñòðîêè ñ dist distedit edit� � .
Êðîìå òîãî, èñïîëüçóþò ôèëüòðàöèþ ñòðîê c ïîñëåäîâàòåëüíûìè îøèáêàìè,
êîòîðûå îïèñàííàÿ ôèëüòðàöèÿ íå èñêëþ÷àåò. Âìåñòî âû÷èñëåíèÿ dist edit äëÿ
ñòðîê, ïðîøåäøèõ ÷åðåç ôèëüòðàöèþ íà óðîâíå i, ïåðåõîäÿò íà óðîâåíü i �1
è îöåíèâàþò íà íåì áîëåå ïëîòíóþ íèæíþþ ãðàíèöó dist edit . Åñëè êîëè÷åñòâî
ñîâïàâøèõ ïîäñòðîê ìåíüøå 2 1i� ��dist edit , èõ èñêëþ÷àþò.  ïðîòèâíîì ñëó÷àå
ïðîâåðÿþò óðîâåíü i �2. Åñëè ñòðîêà íå èñêëþ÷åíà íà óðîâíå ëèñòüåâ äåðåâà, òî
äî íåå âû÷èñëÿþò dist edit (ñ òàêèìè æå îïòèìèçàöèÿìè, êàê äëÿ çàïðîñà rNN).
 ýêñïåðèìåíòàëüíîì èññëåäîâàíèè âàðèàíòîâ ÈÑ äëÿ áûñòðîé ïàìÿòè ïðè
âûïîëíåíèè çàïðîñà rNN ÈÑ HS-tree îêàçàëàñü áûñòðåå ëó÷øèõ àëãîðèòìîâ
AdaptSearch [38], QChunk ([39], ñì. ïîäðàçä. 4.6), PassJoin ([36], ñì. ïîäðàçä. 4.6),
à ïðè çàïðîñå kNN — áûñòðåå Range è AQ. Â ýêñïåðèìåíòàõ ñ âàðèàíòàìè ÈÑ
äëÿ ìåäëåííîé (âíåøíåé) ïàìÿòè ïðè âûïîëíåíèè çàïðîñà rNN HS-tree îêàçàëîñü
áûñòðåå Bed-tree è PassJoin, à ïðè çàïðîñå kNN áûñòðåå Bed-tree è AppGram [72].
Ïðåèìóùåñòâîì HS-tree ÿâëÿåòñÿ âîçìîæíîñòü èñïîëüçîâàíèÿ âíåøíåé ïà-
ìÿòè, à íåäîñòàòêîì — íåýôôåêòèâíîñòü èñêëþ÷åíèÿ äëÿ áîëüøèõ çíà÷åíèé r.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5 197
ÇÀÊËÞ×ÅÍÈÅ
Èíäåêñíûå ñòðóêòóðû, ïðåäëîæåííûå äëÿ ïîèñêà ñèìâîëüíûõ ñòðîê áàçû, ñõîä-
íûõ ñî ñòðîêîé-çàïðîñîì ïî ðàññòîÿíèþ ðåäàêòèðîâàíèÿ ñòðîê dist edit , ðàáîòàþò
íà òåõ æå ïðèíöèïàõ, ÷òî è ÈÑ äëÿ ïîèñêà ïî ñõîäñòâó âåêòîðíûõ äàííûõ [4–6],
ìíîæåñòâ [4] è äàííûõ, äëÿ êîòîðûõ èçâåñòíû òîëüêî âåëè÷èíû ðàññòîÿ-
íèé/ñõîäñòâ ìåæäó îáúåêòàìè [3]. Â íèõ øèðîêî ïðèìåíÿåòñÿ ñòðàòåãèÿ ôèëüòðà-
öèè è óòî÷íåíèÿ, ïðè ïîìîùè êîòîðîé íà ïåðâîì ýòàïå áûñòðî îòáèðàþò ñòðî-
êè-êàíäèäàòû áàçû, êîòîðûå ìîãóò ÿâëÿòüñÿ îòâåòîì íà çàïðîñ, à çàòåì îêîí÷à-
òåëüíûé îòâåò îïðåäåëÿþò âû÷èñëåíèåì èõ dist edit äî ñòðîêè-çàïðîñà.
Íåêîòîðûå ÈÑ íåïîñðåäñòâåííî ðàáîòàþò ñ èñõîäíûìè ñòðîêàìè.
Òàê, ÈÑ íà îñíîâå ðàññòîÿíèé [3] ïðèãîäíû äëÿ ïîèñêà ïî ñõîäñòâó ëþáûõ
îáúåêòîâ, â òîì ÷èñëå è ñòðîê. Îáû÷íî ïðè êîíñòðóèðîâàíèè òàêèõ ÈÑ èñïîëü-
çóåòñÿ èåðàðõè÷åñêîå ðàçáèåíèå îáúåêòîâ áàçû íà (ïîä)ìíîæåñòâà, à ïðè âûïîë-
íåíèè çàïðîñà ïðèíèìàåòñÿ ðåøåíèå, êàêèå èç ïîäìíîæåñòâ ìîæíî èñêëþ÷èòü,
à êàêèå ïðîäîëæàòü îáðàáàòûâàòü. Ìíîãèå èç ÈÑ ýòîãî êëàññà èñïîëüçóþò ìåòîä
âåòâåé è ãðàíèö (branch and bound, B&B). Â äàííîì îáçîðå ïðèìåíåíèå òàêèõ ÈÑ
äëÿ ïîèñêà ñòðîê íå ðàññìàòðèâàëîñü, òàê êàê ââèäó îòñóòñòâèÿ ñïåöèàëèçàöèè
ïîä ñòðîêè ýòîò ïîäõîä óñòóïàåò ïî ñêîðîñòè äðóãèì [7].
 ÈÑ íà îñíîâå ìîäèôèêàöèè ñòðîê ïðèìåíÿþò íåêîòîðûå ìîäèôèêàöèè
ñòðîêè-çàïðîñà è èùóò ñòðîêè áàçû, ñîâïàäàþùèå ñ ïîëó÷åííûìè ìîäèôèêàöèÿ-
ìè. Äëÿ óìåíüøåíèÿ êîëè÷åñòâà ìîäèôèêàöèé èñïîëüçóþò òàêæå çàïîìèíàíèå
ìîäèôèêàöèé îáúåêòîâ áàçû. Ýòîò ïîäõîä ýôôåêòèâåí òîëüêî äëÿ êîðîòêèõ
ñòðîê è ìàëûõ ðàäèóñîâ çàïðîñà.
Ñïåöèàëèçèðîâàííûå äëÿ ñòðîê ïðåôèêñíûå äåðåâüÿ ôàêòè÷åñêè èñïîëüçó-
þò òîëüêî òå ìîäèôèêàöèè ñòðîêè-çàïðîñà, êîòîðûå ñîäåðæàòñÿ â áàçå. Êðîìå
òîãî, çà÷àñòóþ íå òðåáóåòñÿ âûïîëíÿòü ýòàï óòî÷íåíèÿ, òàê êàê êàíäèäàòû ÿâëÿ-
þòñÿ îòâåòîì íà çàïðîñ. Îäíàêî ýòè ÈÑ òðåáóþò áûñòðîé ïàìÿòè è ïëîõî ðàáî-
òàþò ñ áàçàìè êîðîòêèõ ñòðîê, êîòîðûå ñîäåðæàò ïî÷òè âñå âîçìîæíûå ñòðîêè
çàäàííîé äëèíû, òàê êàê ýòî íå óìåíüøàåò êîëè÷åñòâà ìîäèôèêàöèé. Äëÿ áîëü-
øèõ áàç ñ äëèííûìè íåñõîäíûìè ñòðîêàìè è áîëüøèìè ïîðîãàìè íà dist edit ìàëà
ýôôåêòèâíîñòü èñêëþ÷åíèÿ ñòðîê, êîòîðûå íå ÿâëÿþòñÿ îòâåòîì íà çàïðîñ.
Äðóãîé êëàññ ÈÑ ðàáîòàåò ñ ïðèçíàêàìè, êîòîðûå èçâëåêàþò èç ñòðîê, íàïðè-
ìåð ñ n-ãðàììàìè (ðàçëè÷íîé äëèíû, áåç ó÷åòà èëè ñ ó÷åòîì èõ ïîëîæåíèÿ, ñ ïåðå-
êðûòèåì èëè áåç íåãî è äð.). Àíàëèç êîëè÷åñòâà ñîâïàäàþùèõ èëè ñõîäíûõ n-ãðàìì
ñòðîêè-çàïðîñà è ñòðîê áàçû, ýôôåêòèâíî âûïîëíÿþùèéñÿ ñ ïîìîùüþ îáðàòíîãî
èíäåêñà, ïîçâîëÿåò îòîáðàòü ñòðîêè-êàíäèäàòû äëÿ óòî÷íåíèÿ èõ ñîîòâåòñòâèÿ èñ-
õîäíîìó çàïðîñó âû÷èñëåíèåì òî÷íîé âåëè÷èíû èëè ãðàíèöû íà dist edit ñòðîê. Âû-
áîð îïòèìàëüíîãî ðàçìåðà ïðèçíàêà äëÿ íàèâûñøåé ïðîèçâîäèòåëüíîñòè ÈÑ ÿâëÿåò-
ñÿ íåïðîñòîé çàäà÷åé [8]. Ó÷åò òîëüêî ÷àñòè n-ãðàìì (ïðåôèêñíàÿ ôèëüòðàöèÿ) ïî-
çâîëÿåò ïîâûñèòü ñêîðîñòü îòáîðà ñòðîê-êàíäèäàòîâ. Ðàçáèåíèå ñòðîê íà
íåïåðåñåêàþùèåñÿ ÷àñòè óìåíüøàåò êîëè÷åñòâî âûäåëÿåìûõ ïðèçíàêîâ.
Êðîìå òîãî, ðàññòîÿíèÿ ìåæäó âåêòîðàìè ÷àñòîò âñòðå÷àåìîñòè (èëè èíäèêàòî-
ðàìè íàëè÷èÿ) ïðèçíàêîâ ñòðîê îãðàíè÷èâàþò dist edit èñõîäíûõ ñòðîê. Ýòî ïîçâîëÿ-
åò ïðèìåíÿòü ÈÑ, ðàçðàáîòàííûå äëÿ áûñòðîãî ïîèñêà ïî ñõîäñòâó âåêòîðîâ [4–6],
äëÿ áûñòðîãî ïîèñêà ñòðîê-êàíäèäàòîâ ïî âåêòîðàì èõ ïðèçíàêîâ. Îòìåòèì âîçìîæ-
íîñòü ïîâûøåíèÿ ýôôåêòèâíîñòè ïîèñêà âåêòîðîâ çà ñ÷åò ñíèæåíèÿ èõ ðàçìåðíîñòè,
íàïðèìåð ñëó÷àéíûì ïðîåöèðîâàíèåì [1, 2, 74, 75] — ðàíäîìèçèðîâàííûì àëãîðèò-
ìîì, êîòîðûé ïðèìåíÿåòñÿ è â äðóãèõ çàäà÷àõ [76–78].
ÈÑ äëÿ âûïîëíåíèÿ çàïðîñîâ òî÷íîãî ïîèñêà ñ òåîðåòè÷åñêèìè ãàðàíòèÿìè
âðåìåíè ïîèñêà äëÿ õóäøåãî ñëó÷àÿ, ñóáëèíåéíîãî îò êîëè÷åñòâà ñòðîê â áàçå,
èìåþò ñóùåñòâåííûé íåäîñòàòîê — ýêñïîíåíöèàëüíóþ çàâèñèìîñòü âðåìåíè çà-
ïðîñà è/èëè çàòðàò ïàìÿòè îò ðàäèóñà çàïðîñà. Ýòî àíàëîã «ïðîêëÿòèÿ ðàçìåðíîñ-
òè» äëÿ âåêòîðíûõ ïðîñòðàíñòâ [11, 4, 5], à òàêæå äëÿ äàííûõ ñ «âíóòðåííåé»
198 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5
ðàçìåðíîñòüþ [3]. Ýêñïîíåíöèàëüíàÿ çàâèñèìîñòü íå ïîçâîëÿåò ðåàëèçîâàòü è èñ-
ïîëüçîâàòü òàêèå ÈÑ íà ïðàêòèêå, êðîìå êàê äëÿ î÷åíü ìàëûõ ðàäèóñîâ. Ìíîãèå
êëàññû ïðàêòè÷åñêè ðåàëèçóåìûõ ÈÑ, íå èìåþùèå ãàðàíòèé õóäøåãî ñëó÷àÿ,
äàþò âûèãðûø íàä ëèíåéíûì ïîèñêîì òîëüêî äëÿ ìàëûõ ðàäèóñîâ. Òàê, â [7] ðå-
àëèçîâàíû ÈÑ ñ ðàäèóñîì çàïðîñîâ äî òðåõ è îòìå÷àåòñÿ, ÷òî óñêîðåíèå ëèíåé-
íîãî ïîèñêà äîñòèãàåò ÷åòûðåõ ïîðÿäêîâ, íî áûñòðî íèâåëèðóåòñÿ ñ óâåëè÷åíèåì
ðàäèóñà. Îäíàêî ïîëåçíûå ïðàêòè÷åñêèå ïðèìåíåíèÿ ñóùåñòâóþò è äëÿ
åäèíè÷íîãî ðàäèóñà çàïðîñà.
ÈÑ äëÿ ïðèáëèæåííîãî ïîèñêà ñòðîê ñ ñóùåñòâåííî ñóáëèíåéíûì (ïîëèëî-
ãàðèôìè÷åñêèì îò N ) âðåìåíåì çàïðîñà è ïîëèíîìèàëüíûìè çàòðàòàìè ïàìÿòè
(ñì. ïîäðàçä. 5.1) èñïîëüçóþò âëîæåíèÿ â âåêòîðíûå ïðîñòðàíñòâà ñ ðàçíûìè òè-
ïàìè ðàññòîÿíèé è èçâåñòíûì èñêàæåíèåì âëîæåíèÿ. Äëÿ ïîèñêà ïî ïîëó÷åííûì
ïðåäñòàâëåíèÿì ïðèìåíÿþò ÈÑ ñ ãàðàíòèÿìè ñóáëèíåéíîãî âðåìåíè. Ýòè ÈÑ íå
ðåàëèçîâàíû íà ïðàêòèêå. ÈÑ äëÿ ïðèáëèæåííîãî ïîèñêà íà îñíîâå LSH, êîòî-
ðûå òàêæå ïðèìåíÿþò âëîæåíèÿ ñòðîê â âåêòîðû, èìåþò ïðàêòè÷åñêèå ðåàëèçà-
öèè, è äëÿ íèõ òàêæå ìîæíî îæèäàòü òåîðåòè÷åñêèõ ãàðàíòèé ñóáëèíåéíîãî
(õîòÿ è íå ëîãàðèôìè÷åñêîãî) âðåìåíè âûïîëíåíèÿ çàïðîñîâ [79]. Îäíàêî â [80]
ïðåäëîæåíà óñëîâíàÿ íèæíÿÿ ãðàíèöà âðåìåíè çàïðîñà ïðèáëèæåííîãî áëèæàé-
øåãî ñîñåäà äëÿ ëþáûõ àëãîðèòìîâ, âêëþ÷àÿ ðàíäîìèçèðîâàííûå, êîòîðàÿ ñëå-
äóåò èç óñëîâèÿ âûïîëíåíèÿ SETH. Ýòà ãðàíèöà òðåáóåò ïî÷òè ëèíåéíîãî âðåìå-
íè çàïðîñà ïðè ïîëèíîìèàëüíîì âðåìåíè ïðåäîáðàáîòêè. À èìåííî, åñëè âûïîë-
íÿåòñÿ SETH, òî äëÿ ëþáûõ êîíñòàíò � �, 0� ñóùåñòâóåò êîíñòàíòà � � � �� ( , )
òàêàÿ, ÷òî íèêàêîé àëãîðèòì íå ìîæåò ïðåäîáðàáîòàòü ìíîæåñòâî èç N âåêòîðîâ
çà âðåìÿ O N( )� è çàòåì îòâåòèòü íà çàïðîñ (1� �)-NN çà âðåìÿ O N( )1� � .
Íåðåøåííîé ïðîáëåìîé ÿâëÿåòñÿ îáó÷åíèå äðóãèì ìåðàì ñõîäñòâà, îòëè÷-
íûì îò dist edit , íà îñíîâå îáó÷àþùèõ âûáîðîê, â òîì ÷èñëå ñôîðìèðîâàííûõ
ñóæäåíèÿìè ñïåöèàëèñòîâ î ñõîäñòâå ñòðîê [9].
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Rachkovskij D.A. Real-valued vectors for fast distance and similarity estimation. Cybernetics and
Systems Analysis. 2016. Vol. 52, N 6. P. 967–988.
2. Rachkovskij D.A. Binary vectors for fast distance and similarity estimation. Cybernetics and Systems
Analysis. 2017. Vol. 53, N 1. P. 138–156.
3. Rachkovskij D.A. Distance-based index structures for fast similarity search. Cybernetics and Systems
Analysis. 2017. Vol. 53, N 4. P. 636–658.
4. Rachkovskij D.A. Index structures for fast similarity search for binary vectors. Cybernetics and
Systems Analysis. 2017. Vol. 53, N 5. P. 799–820.
5. Rachkovskij D.A. Index structures for fast similarity search for real-valued vectors. I. Cybernetics
and Systems Analysis. 2018. Vol. 54, N 1. P. 152–164.
6. Rachkovskij D.A. Index structures for fast similarity search for real-valued vectors. II. Cybernetics
and Systems Analysis. 2018. Vol. 54, N 2. P. 320–335.
7. Boytsov L. Indexing methods for approximate dictionary searching: Comparative analysis. J. Exp.
Algorithmics. 2011. Vol. 16. P. 1.1:1–1.1:91.
8. Jiang Y., Li G., Feng J., Li W. String similarity joins: An experimental evaluation. Proc. VLDB
Endowment. 2014. Vol. 7, N 8. P. 625–636.
9. Yu M., Li G., Deng D., Feng J. String similarity search and join: a survey. Frontiers of Computer
Science. 2016. Vol. 10, N 3. P. 399–417.
10. Backurs A., Indyk P. Edit distance cannot be computed in strongly subquadratic time (unless SETH
is false). Proc. STOC’15. 2015. P. 51–58.
11. Andoni A., Indyk P. Nearest neighbors in high-dimensional spaces. In: Handbook of Discrete and
Computational Geometry. 3rd edition. Chap. 43. Boca Raton, USA: CRC Press, 2017.
P. 1133–1153.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5 199
12. Andoni A., Indyk P. Near-optimal hashing algorithms for approximate nearest neighbor in high
dimensions. Communications of the ACM. 2008. Vol. 51, N 1. P. 117–122.
13. Mann W., Augsten N., Bouros P. An empirical evaluation of set similarity join techniques. Proc.
VLDB Endow. 2016. Vol. 9, N 9. P. 636–647.
14. Jia L., Zhang L.,Yu G., You J., Ding J., Li M. A survey on set similarity search and join.
International Journal of Performability Engineering. 2018. Vol. 14, N 2. P. 245–258.
15. Manber U., Wu S. An algorithm for approximate membership checking with application to password
security. Inf. Process. Lett. 1994. Vol. 50, N 4. P. 191–197.
16. Chegrane I., Belazzougui D. Simple, compact and robust approximate string dictionary. J. Discrete
Algorithms. 2014. Vol. 28. P. 49–60.
17. Belazzougui D. Faster and space-optimal edit distance “1” dictionary. Proc. CPM’09. 2009.
P. 154–167.
18. Belazzougui D., Venturini R. Compressed string dictionary search with edit distance one.
Algorithmica. 2016. Vol. 74, N 3. P. 1099–1122.
19. Chan T., Lewenstein M. Fast string dictionary lookup with one error. Proc. CPM’15. 2015.
P. 114–123.
20. Fredman M.L., Komlos J., Szemeredi E. Storing a sparse table with O(1) worst case access time.
Journal of the ACM. 1984. Vol. 31, N 3. P. 538–544.
21. Karp R.M., Rabin M.O. Efficient randomized pattern-matching algorithms. IBM Journal of Research
and Development. 1987. Vol. 31, N 2. P. 249–260.
22. Mor M., Fraenkel A.S. A Hash code method for detecting and correcting spelling errors.
Communications of the ACM. 1982.Vol. 25, N 12. P. 935–938.
23. Muth R., Manber U. Approximate multiple string search. Proc. CPM’96. 1996. P. 75–86.
24. Broder A., Mitzenmacher M. Network applications of bloom filters: A survey. Internet Mathematics.
2004. Vol. 1, N 4. P. 485–509.
25. Karch D., Luxen D., Sanders P. Improved fast similarity search in dictionaries. Proc. SPIRE’10.
2010. P. 173–178.
26. Cole R., Gottlieb L.-A., Lewenstein M. Dictionary matching and indexing with errors and don’t
cares. Proc. STOC’04. 2004. P. 91–100.
27. Chan H., Lam T.W., Sung W., Tam S., Wong S. Compressed indexes for approximate string
matching. Algorithmica. 2010. Vol. 58, N 2. P. 263–281.
28. Sokolov À.M. Vector representations for efficient comparison and search for similar strings.
Cybernetics and System Analysis. 2007. Vol. 43, N 4. P. 484–498.
29. Sokolov A.M. Investigation of accelerated search for close text sequences with the help of vector
representations. Cybernetics and Systems Analysis. 2008. Vol. 44, N 4. P. 493–506.
30. Datar M., Immorlica N., Indyk P., Mirrokni V.S. Locality-sensitive hashing scheme based on
p-stable distributions. Proc. SCG’04. 2004. P. 253–262.
31. Andoni A., Datar M., Immorlica N., Indyk P., Mirrokni V. Locality-Sensitive Hashing using stable
distributions. In: Nearest-Neighbor Methods in Learning and Vision: Theory and Practice.
Shakhnarovich G., Darrell T., Indyk P. (Eds.). Cambridge, MA: MIT Press, 2006. P. 61–72.
32. Bawa M., Condie T., Ganesan P. Lsh forest: self-tuning indexes for similarity search. Proc.
WWW’05. 2005. P. 651–660.
33. Andoni A., Razenshteyn I., Shekel Nosatzki N. Lsh forest: Practical algorithms made theoretical.
Proc. SODA’17. 2017. P. 67–78.
34. Zhang H., Zhang Q. EmbedJoin: efficient edit similarity joins via embeddings. Proc. KDD’17. 2017.
P. 585–594.
35. Chakraborty D., Goldenberg E., Koucky M. Streaming algorithms for embedding and computing edit
distance in the low distance regime. Proc. STOC’16. 2016. P. 712–725.
36. Li G., Deng D., Wang J., Feng J. Pass-join: A partition-based method for similarity joins. Proc.
VLDB Endowment. 2011. Vol. 5, N 3. P. 253–264.
37. Xiao C., Wang W., Lin X. Ed-Join: an efficient algorithm for similarity joins with edit distance
constraints. Proc. VLDB Endowment. 2008. Vol 1, N 1. P. 933–944.
38. Wang J., Li G., Feng J. Can we beat the prefix filtering?: An adaptive framework for similarity join
and search. Proc. SIGMOD’12. 2012. P. 85–96.
39. Qin J., Wang W., Lu Y., Xiao C., Lin X. Efficient exact edit similarity query processing with the
asymmetric signature scheme. Proc. SIGMOD’11. 2011. P. 1033–1044.
200 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5
40. Jokinen P., Ukkonen E. Two algorithms for approximate string matching in static texts. Proc.
MFCS’91. 1991. P. 240–248.
41. Gravano L., Ipeirotis P.G., Jagadish H.V., Koudas N., Muthukrishnan S., Srivastava D. Approximate
string joins in a database (almost) for free. Proc. VLDB’01. 2001. P. 491–500.
42. Li C., Wang B., Yang X.. VGRAM: Improving performance of approximate queries on string
collections using variable-length grams. Proc. VLDB’07. 2007. P. 303–314.
43. Yang X., Wang B., Li C. Cost-based variablelength-gram selection for string collections to support
approximate queries efficiently. Proc. SIGMOD’08. 2008. P. 353–364.
44. Kahveci T., Singh A. An efficient index structure for string databases. Proc. VLDB’01. 2001.
P. 351–360.
45. Jiang Y., Deng D., Wang J., Li G., Feng J. Efficient parallel partition-based algorithms for similarity
search and join with edit distance constraints. Proc. EDBT’13. 2013. P. 341–348.
46. Wei H., Yu J.X., Lu C. String similarity search: a hash-based approach. IEEE Transactions on
Knowledge and Data Engineering. 2018. Vol. 30, N 1. P. 170–184.
47. Vernicaand R., Li C. Efficient top-k algorithms for fuzzy search in string collections. Proc.
KEYS’09. 2009. P. 9–14.
48. Deng D., Li G., Feng J. A pivotal prefix based filtering algorithm for string similarity search. Proc.
SIGMOD’14. 2014. P. 673–684.
49. Chaudhuri S., Ganti V., Kaushik R. A primitive operator for similarity joins in data cleaning. Proc.
ICDE’06. 2006. P. 5–16.
50. Ukkonen E. Approximate string-matching over suffix trees. In: Combinatorial Pattern Matching.
CPM 1993. Lecture Notes in Computer Science. Apostolico A., Crochemore M., Galil Z., Manber U.
(Eds.). 1993. Vol 684. P. 228–242.
51. Bocek T., Hunt E., Hausheer D., Stiller B. Fast similarity search in peer-to-peer networks. Proc.
NOMS’08. 2008. P. 240–247.
52. Wang W., Xiao C., Lin X., Zhang C. Efficient approximate entity extraction with edit distance
constraints. Proc. SIGMOD’09. 2009. P. 759–770.
53. Chaudhuri S., Kaushik R. Extending autocompletion to tolerate errors. Proc. SIGMOD’09. 2009.
P. 707–718.
54. Li G., Ji S., Li C., Feng J. Efficient fuzzy full-text type-ahead search. The VLDB Journal. 2011.
Vol. 20, N 4. P. 617–640.
55. Feng J., Wang J., Li G. Trie-Join: a trie-based method for efficient string similarity joins. The VLDB
Journal. 2012. Vol. 21, N. 4. P. 437–461.
56. Gouda Ê., Rashad M. Efficient string edit similarity join algorithm. Computing and Informatics.
2017. Vol. 36. P. 683–704.
57. Wu S., Manber U. Fast text searching allowing errors. Communications of the ACM. 1992. Vol. 35,
N 10. P. 83–91.
58. Qin J., Xiao C. Pigeonring: A principle for faster thresholded similarity search. Proc. VLDB Endow.
2018. Vol. 12, N 1. P. 28–42.
59. Baeza-Yates R., Navarro G. Faster approximate string matching. Algorithmica. 1999. Vol. 23, N 2.
P. 127–158.
60. Navarro G., Sutinen E., Tarhio J. Indexing text with approximate q-grams. Journal of Discrete
Algorithms. 2005. Vol. 3, N 2–4. P. 157–175.
61. Ostrovsky R., Rabani Y. Low distortion embedding for edit distance. Journal of the ACM. 2007.
Vol. 54, N 5. P. 23–36.
62. Kushilevitz E., Ostrovsky R., Rabani Y. Efficient search for approximate nearest neighbor in high
dimensional spaces. SIAM Journal on Computing. 2000. Vol. 30, N 2. P. 457–474.
63. Indyk P. Approximate nearest neighbor under edit distance via product metrics. Proc. SODA’04.
2004. P. 646–650.
64. Indyk P. Approximate nearest neighbor algorithms for frechet metric via product metrics. Proc.
SoCG’02. 2002. P. 102–106.
65. Andoni A., Indyk P., Krauthgamer R. Overcoming the L1 non-embeddability barrier: Algorithms for
product metrics. Proc. SODA’09. 2009. P. 865–874.
66. Yang Z., Yu J., Kitsuregawa M. Fast algorithms for top-k approximate string matching. Proc.
AAAI’10. 2010. P. 1467–1473.
67. Zhang Z., Hadjieleftheriou M., Ooi B.C., Srivastava D. Bed-tree: An all-purpose index structure for
string similarity search based on edit distance. Proc. SIGMOD’10. 2010. P. 915–926.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5 201
68. Morton G.M. A computer oriented geodetic data base; and a new technique in file sequencing.
Technical Report. 1966. Ottawa, Canada: IBM Ltd. 20 p.
69. Lu W., Du X., Hadjieleftheriou M., Ooi B.C. Efficiently supporting edit distance based string
similarity search using B+-trees. IEEE Transactions on Knowledge and Data Engineering. 2014.
Vol. 26, N 12. P. 2983–2996.
70. Jagadish H.V., Ooi B.C., Tan K.-L., Yu C., Zhang R. iDistance: An adaptive b+-tree based indexing
method for nearest neighbor search. ACM Trans. Database Syst. 2005. Vol. 30, N 2. Ð. 364–397.
71. Deng D., Li G., Feng J., Li W.-S. Top-k string similarity search with edit-distance constraints. Proc.
ICDE’13. 2013. P. 925–936.
72. Wang X., Ding X., Tung A.K.H., Zhang Z. Efficient and effective kNN sequence search with
approximate n-grams. Proc. VLDB Endowment. 2013. Vol. 7, N 1. P. 1–12.
73. Yu M., Wang J., Li G., Zhang Y., Deng D., Feng J. A unified framework for string similarity search
with edit-distance constraint. The VLDB Journal. 2017. Vol. 26. P. 249–274.
74. Rachkovskij D.A. Formation of similarity-reflecting binary vectors with random binary projections.
Cybernetics and Systems Analysis. 2012. Vol. 51, N 2. P. 313–323.
75. Ðà÷êîâñüêèé Ä.À., Ãðèöåíêî Â.². Ðîçïîä³ëåíå ïîäàííÿ âåêòîðíèõ äàíèõ íà îñíîâ³ âèïàäêîâèõ
ïðîåêö³é. Êè¿â: ²íòåðñåðâ³ñ, 2018. 216 c.
76. Rachkovskij D.A., Revunova E.G. A randomized method for solving discrete ill-posed problems.
Cybernetics and Systems Analysis. 2012. Vol. 48, N 4. P. 621–635.
77. Revunova E.G. Model selection criteria for a linear model to solve discrete ill-posed problems on the
basis of singular decomposition and random projection. Cybernetics and Systems Analysis. 2016.
Vol. 52, N 4. P. 647–664.
78. Revunova E.G. Averaging over matrices in solving discrete ill-posed problems on the basis of
random projection. Proc. CSIT’17. 2017. P. 473–478.
79. McCauley S. Approximate similarity search under edit distance using locality-sensitive hashing.
arXiv:1907.01600. 2019.
80. Rubinstein A. Hardness of approximate nearest neighbor search. Proc. STOC’18. 2018.
P. 1260–1268.
Íàä³éøëà äî ðåäàêö³¿ 22.02.2019
Ä.À. Ðà÷êîâñüêèé
²ÍÄÅÊÑͲ ÑÒÐÓÊÒÓÐÈ ÄËß ØÂÈÄÊÎÃÎ ÏÎØÓÊÓ ÑÕÎÆÈÕ ÑÈÌÂÎËÜÍÈÕ ÐßÄʲÂ
Àíîòàö³ÿ. Íàâåäåíî îãëÿä ³íäåêñíèõ ñòðóêòóð äëÿ øâèäêîãî ïîøóêó çà
ñõîæ³ñòþ îá’ºêò³â, ùî ïðåäñòàâëåí³ á³íàðíèìè ñèìâîëüíûìè ðÿäêàìè. Ðîç-
ãëÿíóòî ³íäåêñí³ ñòðóêòóðè ÿê äëÿ òî÷íîãî, òàê ³ äëÿ íàáëèæåíîãî ïîøóêó çà
â³äñòàííþ ðåäàãóâàííÿ. Îïèñàíî ³íäåêñí³ ñòðóêòóðè íà îñíîâ³ îáåðíåíîãî
³íäåêñóâàííÿ, ãåøóâàííÿ, ùî çáåð³ãຠñõîæ³ñòü, äåðåâîâèäíèõ ñòðóêòóð. Âèê-
ëàäåíî ³äå¿ àëãîðèòì³â, â³äîìèõ òà íåùîäàâíî çàïðîïîíîâàíèõ.
Êëþ÷îâ³ ñëîâà: ïîøóê çà ñõîæ³ñòþ, â³äñòàíü ðåäàãóâàííÿ, íàéáëèæ÷èé
ñóñ³ä, áëèæí³é ñóñ³ä, ³íäåêñí³ ñòðóêòóðè, îáåðíåíå ³íäåêñóâàííÿ, n-ãðàìè, ëî-
êàëüíî-÷óòëèâå ãåøóâàííÿ, äåðåâîâèäí³ ñòðóêòóðè.
D.A. Rachkovskij
INDEX STRUCTURES FOR FAST SIMILARITY SEARCH FOR SYMBOLIC STRINGS
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.
Keywords: similarity search, edit distance, nearest neighbor, near neighbor,
index structures, inverted indexing, n-grams, locality-sensitive hashing, treelike
structures.
Ðà÷êîâñêèé Äìèòðèé Àíäðååâè÷,
äîêòîð òåõí. íàóê, âåäóùèé íàó÷íûé ñîòðóäíèê Ìåæäóíàðîäíîãî íàó÷íî-ó÷åáíîãî öåíòðà èíôîð-
ìàöèîííûõ òåõíîëîãèé è ñèñòåì ÍÀÍ Óêðàèíû è ÌÎÍ Óêðàèíû, Êèåâ, e-mail: dar@infrm.kiev.ua.
202 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 5
|