FAQ / Сложные алгоритмы поиска

Теперь мы обратимся к двум алгоритмам, которые еще не анализировались с теоретической точки зрения. Начнем с древней проблемы поиска 'частичных совпадений': строка запроса может содержать как обычные буквы, так и нефиксированный символ 'любой' ('.'). Просмотр словаря дает единственное слово rococo, соответствующее образцу 'o.o.o', а образец 'a.a.a' соответствует множеству слов, куда входят banana, casaba и pajama.

Эта проблема изучалась многими исследователями, в том числе Аппелем и Джейкобсоном [1] и Манбером и Беза-Йейтсом [13]. Ривест [19] предложил при поиске частичных совпадений в борах идти по отдельной ветви, если буква задана, а для нефиксированного символа рекурсивно просматривать все ветви. Программа 4 реализует метод Риверса в троичных деревьях поиска; он вызывается посредством

srchtop = 0;
pmsearch(root, '.a.a.a');


В программе 4 имеется пять операторов if. Первый производит выход из функции, когда поиск проходит все дерево. Второй и пятый операторы if симметричны: они рекурсивно просматривают lokid (и hikid), когда ищется нефиксированный символ '.', или когда строка поиска меньше (больше), чем расщепляющий символ splitchar. Третий if рекурсивно просматривает eqkid, если и splitchar, и текущий символ строки запроса не являются нулевыми. Четвертый if отслеживает совпадение с запросом и добавляет указатель на всему слову (хранящемуся в eqkid, так как флаг storestring в программе 4 не нулевой) в выходной массив результатов поиска srcharr.

Согласно Ривесту поиск частичных совпадений в боре требует около O(n(k-s)/k) времени для ответа на слова запроса, в котором задано s букв, при заданном файле из n k-буквенных слов. Троичные деревья поиска можно рассматривать как реализацию его боров (с бинарными деревьями, реализующими множественные ветвления), так что мы предполагали применить его результаты непосредственно к нашей программе. Однако, эксперимент привел к неожиданному результату: нефиксированный символ в начале слова-запроса приводит к гораздо большим затратам, чем нефиксированный символ в конце слова. Для уже рассмотренного словаря в таблице 1 представлены запросы, число совпадений и число узлов, пройденных в процессе поиска, как для сбалансированного дерева, так и для случайного.

char *srcharr[100000];
int srchtop;
void pmsearch(Tptr p, char *s)
{
   if (!p) return;
   nodecnt++;
   if (*s == '.' || *s < p->splitchar)
      pmsearch(p->lokid, s);
   if (*s == '.' || *s == p->splitchar)
      if (p->splitchar && *s)
         pmsearch(p->eqkid, s+1);
   if (*s == 0 && p->splitchar == 0)
      srcharr[srchtop++] = (char *) p->eqkid;
   if (*s == '.' || *s > p->splitchar)
      pmsearch(p->hikid, s);
}

Программа 4. Поиск частичных совпадений

Чтобы изучить этот феномен, мы провели эксперименты как на словаре, так и на случайных данных (близких к словарю). Ограниченный объем данной статьи не позволяют нам описать эти эксперименты, подтверждающие приведенные в вышеуказанной таблице факты. Ключом к пониманию является то, что на верхних уровнях бора, представляющего словарь, велик фактор ветвления; начальный нефиксированный символ обычно приводит к 52 рекурсивным поискам. Ближе к концу слова, фактор ветвления напротив, становится небольшим; нефиксированный символ в конце слова часто дает всего лишь один рекурсивный поиск. Именно по этой причине Ривест полагает, что бинарные боры должны 'ветвиться в первом бите представления каждого символа ... до того, как ветвиться на втором бите каждого'. Флажолет и Пьюч [7] подробно проанализировали этот феномен для битовых боров; их методы можно расширить, чтобы обеспечить подробное представление цены поиска как функции от положения нефиксированного символа.

Таблица 1. Представление поиска частичных совпадений

Структура	Совпадения	Узлы Сбалансированное Случайное
television	1	18	24
tele......	17	261	265
t.l.v.s..n	1	153	164
....vision	1	36,484	37,178
banana	1	15	17
ban...	15	166	166
.a.a.a	19	2829	2746
...ana	8	14,056	13,756
abracadabra	1	21	17
.br.c.d.br.	1	244	266
a..a.a.a..a	1	1127	1104
xy.......	3	67	66
.......xy	3	156,145	157,449
.45	1	285,807	285,807

Наконец, мы обращаемся к проблеме поиска 'соседей' в множестве строк: мы должны найти все слова словаря, находящиеся не дальше заданного расстояния Хемминга от запрашиваемого слова. Например, поиск всех слов, находящихся от soda на расстоянии, не большем двух, даст code, coma и 117 других слов. Программа 5 выполняет поиск соседей в троичном дереве поиска. Ее аргументами являются узел дерева, строка и расстояние. Первый if обеспечивает возврат в случае, если узел пуст или расстояние отрицательно. Второй и четвертый if симметричны: они просматривают подходящее поддерево, если расстояние положительно, или если символ запроса с подходящей стороны от splitchar. Третий if либо проверяет совпадение, либо рекурсивно просматривает срединное поддерево.

void nearsearch(Tptr p, char *s, int d)
{
   if (!p || d < 0) return;
   nodecnt++;
   if (d > 0 || *s < p->splitchar)
      nearsearch(p->lokid, s, d);
   if (p->splitchar == 0) {
      if ((int) strlen(s) <= d)
         srcharr[srchtop++] = (char *) p->eqkid;
   } else
      nearsearch(p->eqkid, *s ? s+1:s, (*s==p->splitchar) ? d:d-1);
   if (d > 0 || *s > p->splitchar)
      nearsearch(p->hikid, s, d);
}

Программа 5. Поиск ближних соседей

Мы провели массированное исследование эффективности программы 5; ограничения на объем статьи позволяют кратко изложить результаты только одного из экспериментов. Таблица описывает его реализацию на двух похожих множествах данных:

D	Словарь   Мин Среднее Макс			Случайное   Мин Среднее Макс
0	9	17.0	22	9	17.1	22
1	228	403.5	558	188	239.5	279
2	1374	2455.5	3352	1690	1958.7	2155
3	6116	8553.7	10829	7991	8751.3	9255
4	15389	18268.3	21603	20751	21537.1	21998

Первая строка представляет цены выполнения поиска на расстоянии 0 для каждого слова в множестве. Рабочий 'словарь' представлял собой 10451 8-буквенных слов, в представляющем его дереве было 55870 узлов. Поиск на расстоянии 0 был проведен для всех слов в словаре. При поиске с наименьшей ценой было пройдено 9 узлов, а при поиске с наибольшей - 22 узла, в то время как средняя цена поиска была равна 17.0. 'Случайные' данные представляют 10000 8-буквенных слов, случайным образом сгенерированных по 10-символьному алфавиту и представленных в виде дерева с 56886 узлами. Последующие строки таблицы описывают поиски для расстояний от 1 до 4. Этот простой эксперимент показывает, что поиск ближайших соседей относительно эффективен, поиск более дальних становится более дорогим, и что простая вероятностная модель хорошо предсказывает время для реальных данных.