Более сложные алгоритмы поиска

Теперь мы обратимся к двум алгоритмам, которые еще не анализировались с теоретической точки зрения. Начнем с древней проблемы поиска "частичных совпадений": строка запроса может содержать как обычные буквы, так и нефиксированный символ «любой» (обозначается символом '.'). Просмотр словаря дает единственное слово 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);
   }

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

Наконец, мы обращаемся к проблеме поиска «соседей» в множестве строк: мы должны найти все слова словаря, находящиеся не дальше заданного расстояния Хемминга от запрашиваемого слова. Например, поиск всех слов, находящихся от 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);
   }