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

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

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

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