Поразрядный поиск

Trie-деревья

В этом разделе мы рассмотрим деревья поиска, которые позволяют использовать разряды ключей для проведения поиска подобно DST-деревьям, но ключи которых упорядочены, что позволяет поддерживать рекурсивные реализации операции сортировать и других операций таблиц символов, как для BST-деревьев. Основная идея заключается в хранении ключей только в нижней части дерева, в листьях. Результирующая структура данных обладает рядом полезных свойств и служит основой для нескольких эффективных алгоритмов поиска. Впервые эта структура была создана Брианде (Briandais) в 1959 г., и поскольку она оказалась удобной для выборки (retrieval), в 1960 г. Фредкин (Fredkin) дал ей специальное название trie. Обычно это слово произносится как " трайи " или " трай " (похоже на try — попытка, англ.), чтобы отличать его от " tree " (дерево). Наверно, в соответствии с принятой в книге терминологией следовало бы ввести термин " trie-деревья бинарного поиска " , но термин trie-дерево повсеместно используется и всем понятен. В этом разделе рассматривается базовая бинарная версия, в разделе 15.3 — ее важная модификация, а в разделах 15.4 и 15.5 — базовая многопутевая версия trie-деревьев и их варианты.

Trie-деревья можно использовать и для ключей с фиксированным количеством разрядов, и для битовых строк переменной длины. Для простоты сначала предположим, что ни один ключ поиска не является префиксом другого ключа. Это условие выполняется, например, когда все ключи различны и имеют фиксированную длину.

В trie-дереве ключи хранятся в листьях бинарного дерева. Вспомните, что было сказано в : лист в дереве — это узел, не имеющий дочерних узлов, что отличает его от внешнего узла, который интерпретируется как пустой дочерний узел. В бинарном дереве под листом понимается внутренний узел с пустыми левой и правой ссылками. Хранение ключей в листьях, а не во внутренних узлах позволяет использовать разряды ключей для управления поиском, как для DST-деревьев в разделе 15.1, сохраняя при этом свойство, что все ключи, текущий разряд которых равен 0, попадают в левое поддерево, а все ключи, текущий разряд которых равен 1 — в правое.

Каждый ключ в trie-дереве хранится в листе, который находится на пути, заданном последовательностью ведущих разрядов ключа. И наоборот, каждый лист в trie-дереве содержит единственный ключ, который начинается с разрядов, определенных путем из корня к этому листу. Пустые ссылки в не листовых узлах соответствуют последовательностям ведущих разрядов, которые не присутствуют ни в одном ключе trie-дерева. Следовательно, для поиска ключа в trie-дереве нужно всего лишь пройти по нему в соответствии с разрядами ключа, как в DST-деревьях, но при этом не нужно выполнять сравнения во внутренних узлах. Поиск начинается с левого разряда ключа и с верхушки дерева и проходит по левой ссылке, если текущий разряд равен 0, и по правой — если 1, перебирая разряды ключа по одному слева направо. Поиск, закончившийся на пустой ссылке, неудачен; поиск, закончившийся в листе, может быть завершен одним сравнения с ключом, поскольку этот узел содержит единственный ключ в дереве, который может быть равен искомому. Реализация этого процесса приведена в программе 15.2.

Для вставки ключа в trie-дерево вначале, как обычно, выполняется поиск. Если поиск завершается на пустой ссылке, она, как обычно, заменяется ссылкой на новый лист, содержащий ключ. Но если поиск заканчивается в листе, необходимо продолжить перемещение вниз по дереву, добавляя внутренний узел для каждого разряда, значение которого совпадает для искомого и найденного ключей; завершится этот процесс тем, что оба ключа в листьях, являющихся дочерними узлами внутреннего узла, будут соответствовать первому разряду, в котором они отличаются. Пример поиска и вставки в trie-дереве показан на рис 15.6; процесс построения trie-дерева вставками ключей в первоначально пустое дерево представлен на рис 15.7. Полная реализация алгоритма вставки приведена в программе 15.3.

Программа 15.2. Поиск в trie-дереве

В этой функции разряды ключа используются для управления переходами при перемещении вниз по дереву, так же, как и в программе 15.1 для DST-деревьев. Возможны три варианта: если поиск доходит до листа (с обеими пустыми ссылками), то это единственный узел trie-дерева, который может содержать запись с ключом v. В этом случае выполняется проверка, действительно ли этот узел содержит v (успешный поиск) или какой-то другой ключ, ведущие разряды которого совпадают с v (неудачный поиск). Если поиск доходит до пустой ссылки, то вторая ссылка родительского узла не должна быть пустой и, следовательно, в trie-дереве существует какой-то другой ключ, отличающийся от искомого текущим разрядом, т.е. поиск неудачен. В программе предполагается, что ключи различны и (если ключи могут иметь различную длину) ни один ключ не является префиксом другого ключа. Член item не используется в не листовых узлах.

private:
  Item searchR(link h, Key v, int d)
    { if (h == 0) return nullItem;
      if (h->l == 0  h->r == 0)
        { Key w = h->item.key();
          return (v == w) ? h->item : nullItem;
        }
      if (digit(v, d) == 0)
        return searchR(h->l, v, d+1);
      else
        return searchR(h->r, v, d+1);
    }
public:
  Item search(Key v)
    { return searchR(head, v, 0); }
      

Ключи в trie-дереве хранятся в листьях (узлах с обеими пустыми ссылками); пустые ссылки в не листовых узлах соответствуют последовательностям разрядов, не найденным ни в одном ключе trie-дерева.

При успешном поиске ключа H = 01000 в этом дереве (вверху) мы переходим из корня влево (поскольку первый бит в двоичном представлении ключа равен 0), затем вправо (поскольку второй бит равен 1), где и обнаруживаем H — единственный ключ в дереве, начинающийся с битов 01. Ни один из присутствующих в дереве ключей не начинается с 101 или 11, и эти последовательности битов приводят в trie-дереве к двум пустым не листовым ссылкам.

Чтобы вставить ключ I (внизу), придется добавить три не листовых узла: один — соответствующий 01, с пустой ссылкой, соответствующей 011; один — соответствующий 010, с пустой ссылкой, соответствующей 0101; и один — соответствующий 0100 с ключом H = 01000 в листе слева от него и с ключом I = 01001 в листе справа.

Программа 15.3. Вставка в trie-дерево

Для вставки нового узла в trie-дерево вначале, как обычно, выполняется поиск. В случае неудачного поиска возможны два варианта.

Если неудачный поиск завершен не в листе, пустая ссылка, на которой закончился поиск, как обычно, заменяется ссылкой на новый узел.

Если неудачный поиск завершен в листе, используется функция split, создающая по одному новому внутреннему узлу для каждой битовой позиции, в которой искомый и найденный ключ совпадают. Этот процесс завершается созданием одного внутреннего узла для самого левого разряда, в котором эти ключи различаются. Оператор switch в функции split преобразует два проверяемых разряда в число для переключения на один из четырех возможных случаев. Если разряды одинаковы (случай 002 = 0 или 112 = 3 ), разбиение продолжается; если разряды различны (случай 012 = 1 или 102 = 2 ), разбиение прекращается.

  private:
    link split(link p, link q, int d)
      { link t = new node(nullItem); t->N = 2;
         Key v = p->item.key(); Key w = q->item.key();
        switch(digit(v, d)*2 + digit(w, d))
          { case 0: t->l = split(p, q, d+1); break;
            case 1: t->l = p; t->r = q; break;
            case 2: t->r = p; t->l = q; break;
            case 3: t->r = split(p, q, d+1); break;
          }
        return t;
      }
    void insertR(link h, Item x, int d)
      { if (h == 0) { h = new node(x); return; }
        if (h->l == 0  h->r == 0)
          { h = split(new node(x), h, d); return; }
        if (digit(x.key(), d) == 0)
          insertR(h->l, x, d+1);
        else
          insertR(h->r, x, d+1);
      }
  public:
    ST(int maxN)
      { head = 0; }
    void insert(Item item)
      { insertR(head, item, 0); }
      

Поскольку алгоритм не обращается к пустым ссылкам в листьях и не хранит элементы в не листовых узлах, можно сократить объем используемой памяти с помощью конструкции union или пары производных классов, определив узлы как принадлежащие к одному из этих двух типов (см. упражнения 15.20 и 15.21). Но пока мы пойдем более простым путем, используя единственный тип узлов, который применялся в BST-деревьях, DST-деревьях и других структурах бинарных деревьев: внутренние узлы характеризуются пустыми ключами, а листья — пустыми ссылками; однако мы будем помнить, что при необходимости можно сэкономить память, теряемую из-за этого упрощения. В разделе 15.3 будет рассмотрено усовершенствование алгоритма, исключающее потребность в нескольких типах узлов, а в главе 16 приводится реализация, в которой используется конструкция union. А теперь рассмотрим основные свойства trie-деревьев, вытекающие из определения и приведенных примеров.

На этой последовательности рисунков показан результат вставки ключей A S E R C H I N в первоначально пустое trie-дерево.

Левое поддерево trie-дерева содержит все ключи, ведущий разряд которых равен 0, а правое поддерево — все ключи, ведущий разряд которых равен 1.

Это свойство trie-деревьев обусловливает прямое соответствие с поразрядным поиском: поиск по бинарному trie-дереву разбивает файл совершено так же, как при бинарной быстрой сортировке (см. ). Такое соответствие становится очевидным при сравнении trie-дерева, показанного на .

В частности, в отличие от DST-деревьев, trie-деревья обладают свойством упорядоченности ключей и поэтому позволяют элементарно реализовать операции сортировать и выбрать в таблице символов (см. упражнения 15.17 и 15.18). Более того, trie-деревья столь же хорошо сбалансированы, как и DST-деревья.

Еще один подход к анализу trie-деревьев заключается в обобщении способа анализа BST-деревьев (см. лемму 12.6). Вероятность того, что к ключей начинаются с бита 0, а N — k ключей начинаются с бита 1, равна $$ \left(\begin{array}{c} N\\ k \end{array}\right)/2^{N} $$ следовательно, длина внешнего пути описывается рекуррентным соотношением $$$$C_{N}=N+\dfrac{1}{2^{N}}\sum \limits_{k}\left( {N\choose k}(C_{k}+C_{N-k})\right)$$$$.

Это рекуррентное соотношение похоже на рекуррентное соотношение для быстрой сортировки, которое было решено в , но решить его значительно труднее. Как ни удивительно, решением является выражение для средних затрат на поиск, полученное на основании леммы 15.3, умноженное в точности на N (см. упражнение 15.26). Исследование самого рекуррентного соотношения позволяет понять, почему trie-деревья лучше сбалансированы, чем BST-деревья: вероятность того, что разбиение произойдет вблизи середины дерева, гораздо выше, чем для любого другого места. Поэтому это рекуррентное соотношение больше напоминает соотношение для сортировки слиянием (приблизительное решение которого равно NlgN), чем соотношение для быстрой сортировки (приблизительное решение 2NlgN).

Неприятное свойство trie-деревьев, также отличающее их от других рассмотренных типов деревьев поиска — однонаправленные пути для ключей с одинаковыми разрядами. Например, ключи, которые различаются только в последнем разряде, всегда требуют пути, длина которого равна длине ключа, независимо от количества ключей в дереве (см. рис 15.8). Количество внутренних узлов может быть даже больше, чем количество ключей.

На этих рисунках показан результат вставки ключей ), длина пути ограничена длиной двоичного представления ключей; однако, как видно из этого примера, пути могут иметь такую длину даже при наличии в trie-дереве всего двух ключей.

Полученные результаты можно проверить эмпирически. Например, на рис 15.9 показано большое дерево, имеющее на 44% больше узлов, чем BST-дерево или DST-дерево, построенное из этого же множества ключей. Тем не менее, оно хорошо сбалансировано, и затраты на поиск в нем почти оптимальны.

Это trie-дерево, построенное в результате вставки около 200 случайных ключей, хорошо сбалансировано, но из-за однонаправленного ветвления содержит на 44 процента больше узлов, чем было бы необходимо в ином случае. (Пустые ссылки в листьях не показаны.)

На первый взгляд может показаться, что дополнительные узлы приведут к существенному повышению средних затрат на поиск, но в действительности это не так: например, при удвоении количества узлов в сбалансированном trie-дереве средние затраты на поиск увеличатся всего на 1 (сравнение разрядов — прим. перев.).

Для удобства реализации в программах 15.2 и 15.3 предполагалось, что ключи различны и имеют фиксированную длину — чтобы иметь уверенность, что рано или поздно ключи окажутся различными, а программы смогут провести побитовую обработку и никогда не выйдут за границу ключей. Для удобства анализа в леммах 15.2 и 15.3 также неявно предполагалось, что ключи имеют произвольное количество разрядов, чтобы в конце концов, если пренебречь очень малой (экспоненциально убывающей) вероятностью, они оказывались различными. Прямым следствием этого допущения является то, что и программы, и их анализ применимы также для ключей, являющихся битовыми строками переменной длины, хотя здесь требуется нескольких уточнений.

Для использования программ в приведенном виде с ключами переменной длины нужно расширить ограничение различия ключей: ни один из ключей не должен быть префиксом другого ключа. Как будет показано в разделе 15.5, в некоторых приложениях это ограничение достигается автоматически. В противном случае такие ключи можно обрабатывать, сохраняя информацию во внутренних узлах, поскольку каждый обрабатываемый префикс соответствует какому-либо внутреннему узлу в trie-дереве (см. упражнение 15.31).

Для достаточно длинных ключей, состоящих из случайных разрядов, утверждения для среднего случая, приведенные в леммах 15.2 и 15.3, по-прежнему справедливы. В худшем случае высота trie-дерева по-прежнему ограничена количеством разрядов в самых длинных ключах. Эти затраты могут оказаться весьма существенными, если ключи имеют очень большую длину и, возможно, некоторое сходство, что вполне может быть в случае закодированных символьных данных. В следующих двух разделах рассматриваются методы снижения затрат в trie-деревьях с длинными ключами. Один из способов сокращения путей в trie-деревьях — свертывание однонаправленных ветвей в единые ссылки (изящный и эффективный метод выполнения этой задачи будет приведен в разделе 15.3). Другой способ уменьшения длин путей в trie-деревьях допускает существование более двух ссылок для каждого узла; этот подход является темой раздела 15.4.

Упражнения

15.11. Нарисуйте результат вставки элементов с ключами E A S Y Q U T I O N в указанном порядке в первоначально пустое trie-дерево.

15.12. Что происходит, если программа 15.3 применяется для вставки записи, ключ которой равен какому-либо ключу, уже присутствующему в trie-дереве?

15.13. Нарисуйте результат вставки элементов с ключами 01010011 00000111 00100001 01010001 11101100 00100001 10010101 01001010 в первоначально пустое trie-дерево.

15.14. Эмпирически сравните высоту, количество узлов и длину внутреннего пути trie-дерева, построенного вставками N случайных 32-разрядных ключей в первоначально пустое дерево, с этими же характеристиками стандартного BST-дерева и RB-дерева (), построенных из тех же ключей, для N = 103, 104, 105 и 106 (см. упражнение 15.6).

15.15. Приведите полную характеристику длины внутреннего пути для худшего случая trie-дерева, содержащего N различных w-разрядных ключей.

15.16. Реализуйте операцию удалить для реализации таблицы символов на основе trie-дерева.

15.17. Реализуйте операцию выбрать для реализации таблицы символов на основе trie-дерева.

15.18. Реализуйте операцию сортировать для реализации таблицы символов на основе trie-дерева.

15.19. Напишите программу, которая выводит все ключи trie-дерева, имеющие те же начальные t разрядов, что и заданный ключ.

15.20. Воспользуйтесь конструкцией union языка C++ для реализации операций найти и вставить на основе trie-деревьев с не листовыми узлами, которые содержат ссылки, но не содержат элементы, и с листьями, которые содержат элементы, но не содержат ссылки.

15.21. Воспользуйтесь парой производных классов для реализации операций найти и вставить на основе trie-деревьев с не листовыми узлами, которые содержат ссылки, но не содержат элементы, и с листьями, которые содержат элементы, но не содержат ссылки.

15.22. Измените программы 15.3 и 15.2 так, чтобы ключ поиска хранился в машинном регистре и при спуске по trie-дереву на уровень вниз для выборки следующего разряда выполнялся сдвиг на один разряд.

15.23. Измените программы 15.3 и 15.2 так, чтобы они использовали таблицу из 2^r trie-деревьев для фиксированной константы r. Первые r разрядов ключа должны использоваться для индексации в таблице, а по остальным разрядам ключа должны применяться стандартные алгоритмы доступа в trie-дереве. Это изменение позволяет сэкономить около r шагов, если только таблица не содержит большого количества пустых записей.

15.24. Какое значение r нужно выбрать в упражнении 15.23 при наличии N случайных ключей (которые достаточно длинны, чтобы их можно было считать различными)?

15.25. Напишите программу для вычисления количества узлов в trie-дереве, соответствующих данному множеству различных ключей фиксированной длины, с помощью их сортировки и сравнения соседних ключей в отсортированном списке.

15.26. Докажите по индукции, что $$$N\sum \limits_{t\geq 0}(1-(1-2^{-t})^{N})$$$ — это решение рекуррентного соотношения наподобие быстрой сортировки, приведенного после леммы 15.3, для длины внешнего пути в случайном trie-дереве.

15.27. Получите выражение, приведенное в лемме 15.4 для среднего количества узлов в случайном trie-дереве.

15.28. Напишите программу для вычисления среднего количества узлов в случайном trie-дереве, состоящем из N узлов, и вывода этого значения с точностью до 10-3, для N = 103, 104, 105 и 106 .

15.29. Докажите, что высота trie-дерева, построенного из N случайных битовых строк, приблизительно равна 2 lgN. Совет: воспользуйтесь решением задачи о дне рождения (см. лемму 14.2).

15.30. Докажите, что средние затраты на поиск в DST-дереве, построенном из случайных ключей, асимптотически равны lgN (см. леммы 15.1 и 15.2).

15.31. Измените программы 15.2 и 15.3 так, чтобы они обрабатывали битовые строки переменной длины с единственным ограничением: в структуре данных не должны храниться записи с повторяющимися ключами. В частности, решите, какое значение возвращать при вызове bit(v, d) для случая, когда d больше длины v.

15.32. Воспользуйтесь trie-деревом для построения структуры данных, которая может поддерживать АТД таблицы существования для w-разрядных целых чисел. Программа должна поддерживать операции создать, вставить и найти при условии, что вставить и найти принимают целочисленные аргументы, а найти возвращает nullItem.key() при неудачном поиске и полученный аргумент в случае успешного поиска.

Patricia-деревья

Основанный на trie-деревьях поиск, который описан в разделе 15.2, обладает двумя недостатками. Во-первых, однонаправленные ветвления приводят к созданию дополнительных, но по сути необязательных, узлов в trie-дереве. Во-вторых, trie-деревья содержат два различных типа узлов, что усложняет алгоритмы (см. упражнения 15.20 и 15.21). В 1968 г. Моррисон (Morrison) нашел способ устранить обе эти проблемы с помощью применения метода, который он назвал patricia ( " practical algorithm to retrieve information coded in alphanumeric " — " практический алгоритм получения информации, закодированной алфавитно-цифровыми символами " ). Моррисон разработал свой алгоритм для приложений, индексирующих строки, наподобие рассмотренных в разделе 15.5, но он также эффективен и для реализации таблицы символов. Подобно DST-деревьям, patricia-деревья позволяют выполнять поиск N ключей в дереве, содержащем всего N узлов; подобно trie-деревьям, они требуют для одного поиска выполнения всего лишь около lgN сравнений разрядов и одного сравнения полного ключа, а также поддерживают другие операции АТД. Более того, эти характеристики производительности не зависят от длины ключей, и структура данных пригодна для ключей переменой длины.

Взяв структуру данных стандартного trie-дерева, мы устраняем однонаправленные пути с помощью простого приема: в каждый узел помещается индекс разряда, который должен проверяться для выбора пути из этого узла. Таким образом, мы сразу переходим к разряду, в котором должно приниматься важное решение, пропуская сравнения разрядов в узлах, в которых все ключи в поддереве имеют одинаковые разряды. А внешние узлы исключаются при помощи еще одного простого приема: данные хранятся во внутренних узлах, а ссылки на внешние узлы заменяются ссылками, которые указывают в обратном направлении вверх на нужный внутренний узел в trie-дереве. Эти два изменения позволяют представлять trie-деревья как бинарные деревья, состоящие из узлов с ключом и двумя ссылками (а также дополнительным полем под индекс); такие деревья называются patricia-деревьями (patricia trie). В patricia-деревьях ключи хранятся в узлах, как в DST-деревьях, а обход дерева выполняется в соответствии с разрядами искомого ключа, но ключи в узлах не используются для управления поиском при спуске вниз по дереву. Они хранятся там просто для возможного обращения к ним впоследствии, при достижении нижней части дерева.

Как было отмечено в предыдущем абзаце, понять работу алгоритма проще, если сначала заметить, что стандартные trie-деревья и patricia-деревья можно считать различными представлениями одной и той же абстрактной структуры trie-дерева. Например, trie-деревья, показанные на рис 15.10 и вверху на рис 15.11, где показаны поиск и вставка в patricia-деревьях, представляют ту же абстрактную структуру, что и trie-деревья на рис 15.6. В алгоритмах поиска и вставки для patricia-деревьев используется, создается и поддерживается конкретное представление абстрактной структуры данных trie-дерева, которое отличается от используемого в алгоритмах поиска и вставки из раздела 15.2; но лежащая в их основе абстракция остается той же самой.

Программа 15.4 является реализацией алгоритма поиска в patricia-дереве. Используемый в ней метод отличается от поиска в trie-дереве тремя аспектами: нет явных пустых ссылок, в ключе проверяется не следующий разряд, а указанный, и поиск завершается сравнением ключа в точке, где происходит переход вверх по дереву. Указывает ли ссылка вверх, проверить легко, т.к. индексы разрядов в узлах (по определению) увеличиваются по мере перемещения вниз по дереву. Поиск начинается с корня и проходит вниз по дереву, используя в каждом узле индекс разряда для определения проверяемого разряда в искомом ключе — если этот разряд равен 1, выполняется переход вправо, а если 0 — влево.

При успешном поиске ключа R = 10010 в этом patricia-дереве выполняется переход вправо (поскольку нулевой бит равен 1), затем влево (поскольку бит 4 равен 0), что приводит к ключу R (единственному ключу в дереве, начинающемуся с последовательности 1***0).

При спуске по дереву выполняется проверка только тех разрядов ключа, которые указаны цифрами над узлами (ключи в узлах игнорируются).

При встрече первой ссылки, указывающей вверх, искомый ключ сравнивается с ключом в указанном узле, т.к. это единственный ключ в дереве, который может быть равен искомому ключу.

При неудачном поиске ключа I = 01001 выполняется переход влево от корня (поскольку нулевой бит равен 0), затем по правой (направленной вверх) ссылке (поскольку первый бит равен 1), и выясняется, что ключ H (единственный ключ в дереве, начинающийся с последовательности 01) не равен I .

Программа 15.4. Поиск в patricia-дереве

Рекурсивная функция searchR возвращает уникальный узел, который может содержать запись с ключом v. Она спускается вниз по trie-дереву, используя биты дерева для управления поиском, но в каждом встреченном узле проверяет только один бит — указанный в поле bit. Функция прерывает поиск, встретив внешнюю ссылку, указывающую вверх. Функция поиска search вызывает функцию searchR, а затем проверяет ключ в этом узле для определения того, был ли поиск успешным или неудачным.

  private:
    Item searchR(link h, Key v, int d)
      { if (h->bit <= d) return h->item;
        if (digit(v, h->bit) == 0)
          return searchR(h->l, v, h->bit);
        else
        return searchR(h->r, v, h->bit);
      }
  public:
    Item search(Key v)
      { Item t = searchR(head, v, -1);
        return (v == t.key()) ? t : nullItem;
      }
       

При спуске вниз по дереву ключи в узлах вообще не проверяются. Но однажды встречается ссылка, указывающая вверх: каждая направленная вверх ссылка указывает на уникальный ключ в дереве, содержащий разряды, которые привели поиск к этой ссылке. Значит, если ключ в узле, указанном первой направленной вверх ссылкой, равен искомому ключу, поиск закончен успешно; в противном случае он неудачен.

На рис 15.10 показан поиск в patricia-дереве. Если в trie-дереве поиск завершается неудачей тогда, когда он обнаруживает пустую ссылку, то соответствующий поиск в patricia-дереве следует несколько иным путем, нежели поиск в стандартном trie-дереве, т.к. при спуске по дереву разряды, соответствующие однонаправленным путям, вообще не проверяются. Поиск в trie-дереве завершается в листе, а поиск в patricia-дереве завершается сравнением с тем же ключом, что и при поиске в trie-дереве, но без проверки разрядов, соответствующих однонаправленному пути в trie-дереве.

Реализация вставки в patricia-деревья отражает два случая, возникающих при вставке в trie-деревья (см. рис 15.11). Как обычно, информация о месте вставки нового ключа определяется в результате неудачного поиска. В trie-деревьях поиск может быть неудачным либо из-за пустой ссылки, либо из-за несовпадения ключа в листе. При использовании patricia-деревьев для определения требуемого типа вставки приходится выполнять больше действий, т.к. во время поиска пропускаются разряды, соответствующие однонаправленным путям.

Чтобы вставить ключ I в приведенное на рис 15.10patricia-дерево, мы добавляем новый узел для проверки бита 4, поскольку ключи H = 01000 и I = 01001 отличаются только этим разрядом (вверху). В последующих поисках в trie-дереве, которые дойдут до нового узла, необходимо проверить ключ H (левая ссылка), если 4 разряд ключа поиска равен 0; а если этот разряд равен 1 (правая ссылка), то следует проверить ключ I. Для вставки ключа N = 01110 (внизу) между ключами H и I добавляется новый узел для проверки бита 2, поскольку именно этот бит отличает N от H и I.

Поиск в patricia-деревьях всегда завершается сравнением ключа, и этот ключ содержит всю нужную информацию. Мы находим самый левый разряд, которым отличаются искомый ключ и ключ, прервавший поиск, затем снова выполняем поиск в дереве, сравнивая позицию этого разряда с позициями разрядов в узлах на пути поиска. Если попадется узел, задающий более старший разряд, чем тот, которым различаются искомый и найденный ключи, то это говорит о пропуске во время поиска в particia-дереве разряда, который должен был бы привести к пустой ссылке при аналогичном поиске в trie-дереве — поэтому необходимо добавить новый узел, который обеспечит проверку этого разряда. Если не удается отыскать узел, задающий более старший разряд, чем тот, которым различаются искомый и найденный ключи, значит, поиск в patricia-дереве соответствует поиску в trie-дереве, завершившемуся в листе. В таком случае добавляется новый узел, который различает искомый ключ и ключ, прервавший поиск. Всегда добавляется только один узел, задающий самый левый разряд, которым отличаются ключи, в то время как при использовании стандартного trie-дерева для достижения этого разряда могло бы потребоваться добавление нескольких узлов, формирующих однонаправленный путь. Помимо функции различения разрядов, новый узел будет использоваться также и для хранения нового элемента. Пример начальных этапов построения trie-дерева показан на рис 15.12.

Эта последовательность рисунков отражает результат вставки ключей показан результат вставки ключей I и N в дерево, показанное на нижнем рисунке.

Программа 15.5 является реализацией алгоритма вставки в patricia-дерево. Ее код вытекает непосредственно из описания, приведенного в предыдущем абзаце, с одним дополнением: мы считаем, что ссылки на узлы, содержащие индексы разрядов, не большие, чем индекс текущего разряда — это ссылки на внешние узлы. Код вставки просто проверяет это свойство ссылок, но он не должен перемещать ключи или ссылки. На первый взгляд направленные вверх ссылки в patricia-деревьях выглядят загадочно, но выбор ссылок, которые должны использоваться при вставке каждого узла, удивительно прост. А использование одного типа узла вместо двух существенно упрощает код.

По построению все внешние узлы, расположенные ниже узла с индексом к, начинаются с тех же самых к разрядов (иначе для различения этих узлов понадобился бы узел с индексом, меньшим к). Следовательно, patricia-дерево можно преобразовать в стандартное trie-дерево, создав соответствующие внутренние узлы между узлами, в которых были пропущены разряды, и заменив ссылки вверх на ссылки, указывающие на внешние узлы (см. упражнение 15.48). Однако свойство 15.2 выполняется для patricia-деревьев не полностью, т.к. присваивание ключей внутренним узлам зависит от порядка вставки ключей. Структура внутренних узлов зависит от порядка вставки ключей, а внешние ссылки и размещение значений ключей — нет.

Программа 15.5. Вставка в patricia-дерево

Процесс вставки ключа в patricia-дерево начинается с поиска. Функция searchR из программы 15.5 приводит к уникальному ключу в дереве, который должен отличаться от вставляемого. Мы находим самый левый бит, которым отличаются этот и искомый ключи, а затем при помощи рекурсивной функции insertR спускаемся вниз по дереву и вставляем новый узел, содержащий v в этой позиции.

В функции insertR рассматриваются два случая, соответствующие случаям, показанным на рис 15.11. Новый узел может заместить внутреннюю ссылку (если ключ поиска отличается от ключа, найденного в пропущенной битовой позиции) или внешнюю ссылку (если бит, которым отличаются искомый ключ и найденный, не нужен для различения найденного ключа от всех других ключей в дереве).

private:
  link insertR(link h, Item x, int d, link p)
    { Key v = x.key();
      if ((h->bit >= d) || (h->bit <= p->bit))
        { link t = new node(x); t->bit = d;
          t->l = (digit(v, t->bit) ? h : t);
          t->r = (digit(v, t->bit) ? t : h);
          return t;
        }
      if (digit(v, h->bit) == 0)
        h->l = insertR(h->l, x, d, h);
      else
      h->r = insertR(h->r, x, d, h);
      return h;
    }
public:
  void insert(Item x)
    { Key v = x.key(); int i;
      Key w = searchR(head->l, v, -1).key();
      if (v == w) return;
      for (i = 0; digit(v, i) == digit(w, i); i++) ;
      head->l = insertR(head->l, x, i, head);
    }
  ST(int maxN)
    { head = new node(nullItem);
      head->l = head->r = head;
    }
      

Важное следствие того, что patricia-дерево представляет лежащую в его основе структуру стандартного trie-дерева, заключается в том, что для посещения узлов в порядке возрастания их ключей можно использовать рекурсивный обход дерева слева направо, что демонстрирует программа 15.6. Посещаются только внешние узлы, которые выявляются проверкой на наличие не увеличивающихся индексов разрядов.

Patricia-деревья — наиболее показательный вариант метода поразрядного поиска: он позволяет находить разряды, которые различают ключи поиска, и встраивать их в структуру данных (без лишних узлов), быстро приводящую от любого искомого ключа к единственному ключу в структуре, который может быть равен искомому. На рис 15.13 показано patricia-дерево, образованное теми же ключами, что и для построения trie-дерева на рис 15.9: patricia-дерево не только содержит на 44% узлов меньше по сравнению со стандартным trie-деревом, но и почти идеально сбалансировано.

Это patricia-дерево, построенное в результате вставки примерно 200 случайных ключей, эквивалентно trie-дереву, приведенному на рис 15.9, в котором удалены однонаправленные пути. Результирующее дерево почти идеально сбалансировано.

Программа 15.6. Сортировка в patricia-дереве

Данная рекурсивная процедура отображает записи в patricia-дереве в порядке следования их ключей. Здесь предполагается, что элементы располагаются в (виртуальных) внешних узлах, которые могут быть выявлены проверкой, что индекс разряда в текущем узле не превышает индекс разряда его родительского узла. В остальном эта программа представляет собой реализацию стандартного поперечного обхода дерева.

  private:
    void showR(link h, ostream os, int d)
      { if (h->bit <= d) { h->item.show(os); return; }
        showR(h->l, os, h->bit);
        showR(h->r, os, h->bit);
      }
  public:
    void show(ostream os)
      { showR(head->l, os, -1); }
      

В . Поэтому данные методы, несомненно, следует рассматривать в качестве возможных реализаций таблиц символов даже при использовании ключей, которые представимы в виде коротких битовых строк, с учетом ряда упомянутых очевидных компромиссов.

Эти сравнительные значения времени построения и поиска в таблицах символов, содержащих случайные последовательности 32-разрядных целых чисел, подтверждают, что поразрядные методы могут конкурировать с методами, использующими сбалансированные деревья, даже в случае ключей, состоящих из случайных битов. Различия в производительности более заметны, если ключи являются длинными и не обязательно случайными (см. таблица 15.2), или когда возможен эффективный доступ к разрядам ключа (см. упражнение 15.22).

Обратите внимание, что затраты на поиск, приведенные в лемме 15.5, не возрастают с увеличением длины ключа. И напротив, затраты на поиск в стандартном trie-дереве, как правило, зависят от длины ключей: позиция первого разряда, которым различаются два заданных ключа, может находиться сколь угодно далеко. Все рассмотренные ранее методы поиска, основанные на сравнениях, также зависят от длины ключа: даже если два ключа различаются только самым правым разрядом, для их сравнения требуется время, пропорциональное длине ключей. А в методах хеширования всегда требуется время, пропорциональное длине ключа — на вычисление хеш-функции. Однако patricia-деревья сразу обращаются к значимым разрядам и обычно проверяют менее lgN из них. В связи с этим patricia-метод (или поиск по trie-дереву со свернутыми однонаправленными путями) является рекомендуемым методом поиска при наличии длинных ключей.

Например, предположим, что используется компьютер, обеспечивающий эффективный доступ к 8-разрядным байтам данных, и требуется выполнять поиск среди миллионов 1000-разрядных ключей. В этом случае patricia-методу для выполнения поиска будет нужен доступ лишь приблизительно к 20 байтам искомого ключа плюс одна 125-байтовая операция проверки на равенство. А при использовании хеширования потребовался бы доступ ко всем 125 байтам искомого ключа для вычисления хеш-функции (плюс несколько проверок на равенство), а методы, основанные на сравнениях, потребовали бы от 20 до 30 полных сравнений ключей. Конечно, сравнения ключей, особенно на ранних этапах поиска, требуют проверки всего нескольких байтов, но на последующих этапах, как правило, необходимо сравнение значительно большего количества байтов. В разделе 15.5 мы снова сравним производительность различных методов поиска для длинных ключей.

Patricia-ялгоритм не накладывает какие-либо ограничения на длину искомых ключей. Этот алгоритм особенно эффективен в приложениях с потенциально очень длинными ключами переменной длины, наподобие рассматриваемых в разделе 15.5. При использовании patricia-деревьев обычно можно надеяться, что количество проверок разрядов, необходимых для поиска среди N записей, даже с очень длинными ключами, будет приблизительно пропорционально lgN.

Упражнения

15.33. Что происходит при использовании программы 15.5 для вставки записи, ключ которой равен какому-либо ключу, уже присутствующему в patricia-дереве?

15.34. Нарисуйте patricia-дерево, образованное вставками ключей E A S Y Q U T I O N в указанном порядке в первоначально пустое дерево.

15.35. Нарисуйте patricia-дерево, образованное вставками ключей 01010011 00000111 00100001 01010001 11101100 00100001 10010101 01001010 в указанном порядке в первоначально пустое дерево.

15.36. Нарисуйте patricia-дерево, образованное вставками ключей 01001010 10010101 00100001 11101100 01010001 00100001 00000111 01010011 в указанном порядке в первоначально пустое дерево.

15.37. Экспериментально сравните высоту и длину внутреннего пути patricia-дерева, построенного вставками N случайных 32-разрядных ключей в первоначально пустое дерево, с этими же характеристиками стандартного BST-дерева и RB-дерева (), построенных из этих же ключей, для N = 103, 104, 105 и 106 (см. упражнения 15.6 и 15.14).

15.38. Приведите полную характеристику длины внутреннего пути для худшего случая patricia-дерева, содержащего N различных w-разрядных ключей.

15.39. Реализуйте операцию выбрать для таблицы символов на основе patricia-дерева.

15.40. Реализуйте операцию удалить для таблицы символов на основе patricia-дерева.

15.41. Реализуйте операцию объединить для таблицы символов на основе patricia-дерева. о 15.42. Напишите программу, которая выводит все ключи patricia-дерева, имеющие те же начальные t разрядов, что и заданный ключ.

15.43. Измените стандартные поиск и вставку в trie-дереве (программы 15.2 и 15.3), чтобы исключить однонаправленные пути, как в patricia-деревьях. Если вы выполнили упражнение 15.20, начните с полученной в нем программы.

15.44. Измените поиск и вставку в patricia-дереве (программы 15.4 и 15.5), чтобы использовать таблицу, содержащую 2^r trie-деревьев, как описано в упражнении 15.23.

15.45. Покажите, что каждый ключ в patricia-дереве находится на собственном пути поиска и, следовательно, во время выполнения операции найти встречается как по пути вниз по дереву, так и в конце этого пути.

15.46. Измените программу поиска в patricia-дереве (программа 15.4), чтобы она сравнивала ключи при спуске вниз по дереву, для повышения производительности успешного поиска. Экспериментально оцените эффективность этого изменения (см. упражнение 15.45).

15.47. Воспользуйтесь patricia-деревом для построения структуры данных, которая может поддерживать АТД таблицы существования для w-разрядных двоичных целых чисел (см. упражнение 15.32).

15.48. Напишите программу, которая преобразует patricia-дерево в стандартное trie-дерево с теми же ключами, и наоборот.

Многопутевые trie-деревья и TST-деревья

Мы уже видели, что производительность поразрядной сортировки можно существенно увеличить, рассматривая одновременно более чем один разряд. То же самое справедливо и в отношении поразрядного поиска: сравнивая одновременно по r разрядов, скорость поиска можно увеличить в r раз. Однако здесь есть скрытая опасность, из-за которой эту идею следует применять более осторожно, чем в случае поразрядной сортировки. Проблема заключается в том, что одновременное сравнение r разрядов соответствует использованию узлов дерева с R = 2r ссылками, а это может привести к значительным излишним затратам памяти на неиспользуемые ссылки.

В (бинарных) trie-деревьях, описанных в разделе 15.2, узлы, соответствующие разрядам ключей, имеют две ссылки: одну для нулевого разряда ключа, и вторую — для единичного. Естественно обобщить их до R-путевых trie-деревьев, в которых цифрам ключа соответствуют узлы с R ссылками, по одной для каждого возможного значения цифры. Ключи хранятся в листьях (узлах со всеми пустыми ссылками). Поиск в R-путевом trie-дереве начинается с корня и с самой левой цифры ключа, и цифры ключа используются для управления спуском по дереву. Если значение цифры равно i, выполняется переход по i-ой ссылке (и на следующую цифру). Если обнаружен лист, он содержит единственный ключ в trie-дереве, ведущие цифры которого соответствуют пройденному пути, поэтому для определения того, успешно или неудачно завершился поиск, остается сравнить этот ключ с искомым. При достижении пустой ссылки понятно, что поиск неудачен, поскольку эта ссылка соответствует последовательности ведущих цифр, не найденной ни в одном ключе trie-дерева. На рис 15.14 показано 10-путевое trie-дерево, представляющее некоторое множество десятичных чисел.

На этом рисунке показано trie-дерево, которое позволяет различать набор чисел (см. рис 12.1). Каждый узел имеет 10 ссылок (по одной для каждой возможной цифры). Ссылка 0 в корне указывает на trie-дерево для ключей, первая цифра которых равна 0 (есть только одно такое число); ссылка 1 указывает на trie-дерево для ключей с первой цифрой 1 (таких деревьев два) и т.д. Ни одно из этих чисел не начинается с цифр 4, 7, 8 или 9, поэтому соответствующие ссылки остаются пустыми. В дереве присутствует только по одному числу, первая цифра которого равна 0, 2 и 5, поэтому для каждой из этих цифр имеется лист, содержащий соответствующее число. Остальная часть структуры построена рекурсивно, переходя каждый раз на одну цифру вправо.

Как отмечалось в главе 10 , встречающиеся на практике числа обычно различаются сравнительно небольшим количеством узлов trie-дерева. Эта же особенность для более общих типов ключей служит основой для ряда эффективных алгоритмов поиска.

Прежде чем создавать полную реализацию таблицы символов с несколькими типами узлов, мы начнем изучение многопутевых деревьев с задачи таблицы существования, в которой хранятся только ключи (без записей или связанной с ними информации). Требуется разработать алгоритмы операций вставки ключа в структуру данных и поиска в структуре данных, чтобы определить, был ли уже вставлен заданный ключ. Чтобы использовать тот же интерфейс, что и для более общих реализаций таблиц символов, мы будем придерживаться соглашения, что функция поиска возвращает nullItem в случае неудачи и фиктивный элемент, содержащий искомый ключ, в случае успеха. Это соглашение упрощает код и способствует наглядному представлению структуры многопутевых trie-деревьев. В разделе 15.5 будут рассмотрены более общие реализации таблиц символов, в том числе индексы строк.

Для простоты в этом определении предполагается, что ни один ключ не является префиксом другого. Обычно это ограничение достигается при условии, что все ключи различны и либо имеют фиксированную длину, либо содержат завершающий символ со значением NULLdigit — сигнальный символ, который не используется ни для каких других целей. Суть данного определения в том, что таблицы существования можно реализовать с помощью trie-деревьев существования, не храня внутри trie-дерева никакой информации. Вся информация неявно определяется структурой trie-дерева. Каждый узел содержит R + 1 ссылку (по одной для каждой возможной цифры плюс одна ссылка для NULLdigit) и не содержит никакой другой информации. Для управления спуском по trie-дереву во время поиска используются цифры ключа. Если ссылка на NULLdigit встретилась одновременно с завершением цифр ключа, то поиск успешен, иначе — неудачен. Для вставки нового ключа поиск выполняется до тех пор, пока не встретится пустая ссылка, а затем добавляются узлы для каждого из оставшихся символов ключа. На рис 15.15 показан пример 27-путевого trie-дерева; программа 15.7 содержит реализацию базовых процедур поиска и вставки в (многопутевом) trie-дереве существования.

Если ключи имеют фиксированную длину и различны, можно обойтись без конечного символа и прекращать поиск при достижении конца ключа (см. упражнение 15.55). Мы уже встречались с примером подобного trie-дерева, когда использовали trie-деревья для описания MSD-сортировки ключей фиксированной длины (см. рис 10.10).

В некотором смысле это чисто абстрактное представление структуры trie-дерева является оптимальным, т.к. оно может поддерживать выполнение операции найти за время, пропорциональное длине ключа, при затратах памяти, в худшем случае пропорциональных количеству всех символов в ключе. Однако общий объем используемой памяти может оказаться весьма большим, поскольку для каждого символа нужно около R ссылок, поэтому необходимы более эффективные реализации. Как было показано для случая бинарных trie-деревьев, чистую структуру trie-дерева удобно рассматривать как конкретное представление базовой абстрактной структуры, являющейся хорошо определенным представлением используемого набора ключей, а затем рассмотреть и другие представления той же абстрактной структуры, которые могут обеспечить лучшую производительность.

Предполагается, что ключи в структуре данных различны, и ни один ключ не является префиксом другого. При выполнении поиска в стандартном многопутевом trie-дереве цифры ключа используются для управления поиском при спуске по дереву, при этом возможны три варианта. Если достигнута пустая ссылка, значит, поиск неудачен; если достигнут лист, содержащий ключ поиска, то поиск успешен; и если достигнут лист, содержащий другой ключ — поиск неудачен. Все листья имеют R пустых ссылок, поэтому, как было сказано в разделе 15.2, узлы-листья и не листовые узлы удобно представить по-разному. Такая реализация будет рассмотрена в , а в этой главе предлагается другой подход. В любом случае можно обобщить аналитические результаты из раздела 15.3 и получить представление о характеристиках производительности стандартных многопутевых деревьев.

26-путевое trie-дерево для слов now, is и the (вверху) имеет девять узлов: корень плюс по одному узлу для каждой буквы. Здесь узлы помечены буквами, но в этой структуре данных не нужны явные метки узлов, поскольку метка каждого узла может быть получена, исходя из позиции его ссылки в массиве ссылок родительского узла. При вставке ключа time в существующем узле для буквы t создается новая ветка, и добавляются новые узлы для букв i, m и e (в центре); для вставки ключа for создается новая ветка от корня, и добавляются новые узлы для букв f, o и r.

Характеристики производительности, указанные в лемме 15.6, представляют собой крайний случай компромисса между временем и памятью. С одной стороны, имеется большое количество неиспользуемых пустых ссылок — лишь несколько узлов вблизи вершины дерева используют более одной-двух из своих ссылок. Зато, с другой стороны, высота дерева получается небольшой.

Программа 15.7. Поиск и вставка в R-путевом trie-дереве существования

В данной реализации операций найти и вставить АТД таблицы существования для многопутевых trie-деревьев ключи хранятся неявно внутри структуры trie-дерева. Каждый узел содержит R указателей на следующий, более низкий уровень trie-дерева. Если t-я цифра ключа равна i, происходит переход на уровне t по i-ой ссылке. Функция поиска возвращает фиктивный элемент, содержащий переданный в аргументе ключ, если он присутствует в таблице, или nullItem в противном случае. В качестве альтернативы можно было бы изменить интерфейс, чтобы в нем использовался только тип Key, или в созданном классе элементов реализовать преобразование типа из Item в Key.

  private:
    struct node
    { node **next;
      node()
        { next = new node*[R];
          for (int i = 0; i < R; i++) next[i] = 0;
        }
    };
  typedef node *link;
  link head;
  Item searchR(link h, Key v, int d)
    { int i = digit(v, d);
      if (h == 0) return nullItem;
      if (i == NULLdigit)
        { Item dummy(v); return dummy; }
      return searchR(h->next[i], v, d+1);
    }
    void insertR(link h, Item x, int d)
      { int i = digit(x.key(), d);
        if (h == 0) h = new node;
        if (i == NULLdigit) return;
        insertR(h->next[i], x, d+1);
      }
    public:
      ST(int maxN)
      { head = 0; }
    Item search(Key v)
      { return searchR(head, v, 0); }
    void insert(Item x)
      { insertR(head, x, 0); }
      

Предположим, например, что используется типичное значение R = 256 и имеется N случайных 64-разрядных ключей. В соответствии с леммой 15.6 для выполнения поиска потребуется lgN / 8 сравнений символов (максимум 8), и при этом будет задействовано менее 47 N ссылок. Если объем доступной памяти не ограничен, этот метод является весьма эффективной альтернативой. А взяв в этом примере R = 65536, можно сократить затраты на выполнение поиска до 4 сравнений символов, однако при этом потребуется более 5900 N ссылок.

Мы вернемся к стандартным многопутевым деревьям в разделе 15.5. Далее до конца этого раздела рассматривается альтернативное представление trie-деревьев, построенных программой 15.7: trie-дерево тернарного поиска (ternary search trie — TST), или просто TST-дерево, полная форма которого показана на рис 15.16.

На этих рисунках показаны три различных реализации trie-дерева существования для 16 слов call me ishmael some years ago never mind how long precisely having little or no money: 26-путевое trie-дерево существования (вверху), абстрактное trie-дерево с удаленными пустыми ссылками (в центре) и представление TST-деревом (внизу). 26-путевое trie-дерево содержит слишком много ссылок, но TST-дерево служит эффективным представлением абстрактного trie-дерева.

В двух верхних trie-деревьях предполагается, что ни один ключ не является префиксом другого. Например, добавление ключа not привело бы к потере ключа no. Для решения этой проблемы в конец каждого ключа можно добавить нулевой символ, как показано в TST-дереве на нижнем рисунке.

В TST-дереве каждый узел содержит символ и три ссылки, соответствующие ключам, текущие цифры которых меньше, равны или больше символа этого узла.

Этот подход эквивалентен реализации узлов trie-дерева в виде BST-деревьев, в которых в качестве ключей используются символы, соответствующие непустым ссылкам. В стандартных trie-деревьях существования из программы 15.7 узлы trie-дерева представляются R + 1 ссылками, и символы, представленные каждой непустой ссылкой, определяются их индексами. В соответствующем TST-дереве существования все символы, соответствующие непустым ссылкам, явно присутствуют в узлах: мы находим символы, соответствующие ключам, только проходя по средним ссылкам.

Алгоритм поиска для реализации АТД таблицы существования на основе TST-деревьев настолько прост, что его нетрудно написать самостоятельно. Алгоритм вставки несколько сложнее, но в точности соответствует вставке в trie-деревьях существования. В начале поиска первый символ ключа сравнивается с символом в корне. Если он меньше, поиск продолжается по левой ссылке, если больше — по правой, а если равен, поиск проходит по средней ссылке, и выполняется переход к следующему символу ключа. В любом случае алгоритм продолжается рекурсивно. Поиск завершается неудачно, если встретилась пустая ссылка или ключ поиска закончился раньше, чем в дереве встретился символ NULLdigit. Поиск завершается успешно, если происходит переход по средней ссылке с символом NULLdigit. Для вставки нового ключа выполняется поиск, а затем добавляются новые узлы для символов в заключительной части ключа — точно так же, как и в trie-деревьях. Подробности реализации этих алгоритмов приведены в программе 15.8, а на рис 15.17 показаны TST-деревья, соответствующие trie-деревьям на рис 15.15.

TST-дерево существования содержит по одному узлу для каждой буквы, но каждый узел имеет только 3 дочерних узла, а не 26. Деревья на трех верхних рисунках — это TST-деревья, соответствующие примеру вставки на рис. 15.15 рис 15.15, за исключением того, что к каждому ключу дописан завершающий символ. Это позволяет снять ограничение, что ни один ключ не может быть префиксом другого. Теперь можно, например, вставить ключ theory (рисунок внизу).

Продолжая использовать соответствие между деревьями поиска и алгоритмами сортировки, мы видим, что TST-деревья соответствуют трехпутевой поразрядной сортировке, так же, как BST-деревья соответствуют быстрой сортировке, trie-деревья — бинарной быстрой сортировке, а М-путевые trie-деревья — М-путевой поразрядной сортировке. Структура рекурсивных вызовов для трехпутевой поразрядной сортировки, показанная на рис 10.12, представляет собой TST-дерево для этого набора ключей. Проблема пустых ссылок, присущая trie-деревьям, соответствует проблеме пустых контейнеров поразрядной сортировки; трехпутевое ветвление обеспечивает эффективное решение обеих этих проблем.

Программа 15.8. Поиск и вставка в TST-дереве существования

Это код реализует те же алгоритмы абстрактного trie-дерева, что и в программе 15.7, но каждый узел содержит лишь одну цифру и три ссылки: по одной для ключей, следующая цифра которых меньше, равна и больше соответствующей цифры в искомом ключе.

  private:
    struct node
    { Item item; int d; node *l, *m, *r;
      node(int k)
        { d = k; l = 0; m = 0; r = 0; }
    };
  typedef node *link;
  link head;
  Item nullItem;
  Item searchR(link h, Key v, int d)
    { int i = digit(v, d);
      if (h == 0) return nullItem;
      if (i == NULLdigit)
        { Item dummy(v); return dummy; }
      if (i < h->d) return searchR(h->l, v, d);
      if (i == h->d) return searchR(h->m, v, d+1);
      if (i > h->d) return searchR(h->r, v, d);
    }
    void insertR(link h, Item x, int d)
      { int i = digit(x.key(), d);
        if (h == 0) h = new node(i);
        if (i == NULLdigit) return;
        if (i < h->d) insertR(h->l, x, d);
        if (i == h->d) insertR(h->m, x, d+1);
        if (i > h->d) insertR(h->r, x, d);
      }
    public:
      ST(int maxN)
      { head = 0; }
    Item search(Key v)
      { return searchR(head, v, 0); }
    void insert(Item x)
      { insertR(head, x, 0); }
      

Эффективность использования памяти TST-деревьями можно повысить, помещая ключи в листья в тех точках, где они различны, и сворачивая однонаправленные пути между внутренними узлами, как в patricia-деревьях. В конце этого раздела мы рассмотрим реализацию, основанную на первом из этих изменений.

Эти ключи из онлайновой библиотечной базы данных иллюстрируют гибкость структуры, обеспечиваемую в приложениях обработки строковых ключей. Некоторые символы могут быть смоделированы случайными буквами, другие — случайными цифрами, а третьи имеют фиксированное значение или структуру.

Главное достоинство TST-деревьев заключается в том, что они аккуратно приспосабливаются к неоднородностям в ключах, которые весьма вероятны в реальных приложениях. Это проявляется в виде двух основных эффектов. Во-первых, ключи в реальных приложениях берутся из больших символьных наборов, а использование конкретных символов из набора далеко от однородного — например, в конкретном наборе строк, скорее всего, будет использоваться лишь небольшая часть возможных символов. Используя TST-деревья, можно применять 256-символьную ASCII-кодировку или даже 65536-символьный Unicode, не беспокоясь о лишних затратах в узлах с 256- или 65536-путевым ветвлением и не задумываясь, какие наборы символов действительно применяются. Unicode-строки символов алфавитов, отличных от латинского, могут содержать тысячи символов — TST-деревья особенно подходят для строковых ключей, состоящих из таких символов. Во-вторых, в реальных приложениях ключи часто имеют структурированный формат, различный в разных приложениях, когда в одной части ключа используются только буквы, в другой — только цифры, а в качестве разделителей используются специальные символы (см. упражнение 15.72). Например, на рис 15.18 приведен список номеров вызовов онлайновой библиотечной базы данных. В случае таких ключей некоторые из узлов trie-дерева могут быть представлены унарными узлами в TST-дереве (там, где все ключи содержат разделители), другие могут быть представлены BST-деревьями, состоящими из 10 узлов (там, где все ключи содержат цифры), а третьи — BST-деревьями из 26 узлов (там, где все ключи содержат буквы). Эта структура создается автоматически, без какого-либо специального анализа ключей.

Второе практическое достоинство поиска, основанного на TST-деревьях, по сравнению с множеством других алгоритмов заключается в том, что неудачные поиски обычно исключительно эффективны даже при длинных ключах. Часто для завершения неудачного поиска алгоритм использует лишь несколько сравнений байтов (и проходит по нескольким ссылкам). Как было показано в разделе 15.3, для неудачного поиска в хеш-таблице, содержащей N ключей, требуется время, пропорциональное длине ключа (для вычисления хеш-функции), а в дереве поиска требуется не менее lgN сравнений ключей. Даже в patricia-дереве для неудачного поиска случайного ключа требуетсяlgN сравнений разрядов.

В таблица 15.2 приведены экспериментальные данные, подтверждающие выводы, приведенные в двух предыдущих абзацах.

Эти сравнительные значения времени построения и поиска в таблицах символов, образованных строковыми ключами, наподобие библиотечных номеров на рис 15.18, подтверждают, что TST-деревья, хотя и требуют больших затрат при построении, обеспечивают наиболее быстрый неудачный поиск строковых ключей. В основном это обусловлено тем, что для поиска не требуется просмотр всех символов ключа.

Третья причина привлекательности TST-деревьев заключается в том, что они поддерживают более общие операции, чем рассмотренные операции таблиц символов. Например, в программе 15.9 можно не указать отдельные символы ключа поиска, и она выведет все ключи в структуре данных, которые соответствуют указанным цифрам искомого ключа. Пример такого поиска показан на рис 15.19. Очевидно, что, внеся небольшие изменения, эту программу можно приспособить для перебора всех соответствующих ключей (как для операции сортировать), а не просто для их вывода (см. упражнение 15.58).

TST-деревья позволяют легко решать еще несколько аналогичных задач. Например, можно посетить все ключи в структуре данных, которые отличаются от ключа поиска не более чем одним цифровым символом (см. упражнение 15.59). В других реализациях таблиц символов подобные операции требуют больших затрат или вовсе невозможны. Эти и многие другие задачи обнаружения нестрогого соответствия со строкой поиска будут рассмотрены в части 5.

Patricia-деревья предоставляют несколько аналогичных преимуществ; основное практическое преимущество TST-деревьев по сравнению с patricia-деревьями заключается в том, что они обеспечивают доступ к байтам или символам, а не к разрядам ключей. Одна из причин, почему это различие считается преимуществом, связана с тем, что предназначенные для этого машинные операции реализованы во многих компьютерах, а C++ обеспечивает непосредственный доступ к байтам символьных строк в стиле C. Другая причина состоит в том, что в некоторых приложениях работа с байтами или символами в структуре данных естественным образом соответствует байтовой структуре самих данных — например, в задаче поиска частичного соответствия, описанной в предыдущем абзаце (хотя, как будет показано в , поиск частичного соответствия можно ускорить и с помощью продуманного использования доступа к разрядам).

Для устранения однонаправленных путей в TST-деревьях заметим, что большинство однонаправленных путей соответствует концам ключей, что несущественно, если применяется реализация таблицы символов, в которой записи хранятся в листьях, помещенных на самом верхнем уровне дерева различения ключей. Можно также использовать индексацию байтов, как в patricia-деревьях (см. упражнение 15.65), однако для простоты мы опустим это изменение. Сочетание многопутевого ветвления и представления в виде TST-дерева и само по себе достаточно эффективно во многих приложениях, но свертывание однонаправленных путей в стиле patricia-деревьев еще больше повышает производительность в тех случаях, когда ключи часто совпадают во многих символах подряд (см. упражнение 15.72).

Чтобы найти все ключи в TST-дереве, которые соответствуют шаблону i* (вверху), мы выполняем поиск i в BST-дереве для первого символа. В данном примере после двух однопутевых разветвлений найдено слово is — единственное слово, соответствующее шаблону. Чтобы найти соответствия более общему шаблону наподобие *o* (внизу), в BST-дереве посещаются все узлы, соответствующие первому символу, но поиск продолжается только там, где есть o во втором символе — окончательно это дает слова for и now.

Еще одно простое усовершенствование поиска, основанного на использовании TST-деревьев — использование большого явного многопутевого узла в корне. Для этого проще всего хранить таблицу R TST-деревьев: по одному для каждого возможного значения первой буквы в ключах. Если значение R невелико, можно использовать первые две буквы ключей (и таблицу размером R² ). Чтобы этот метод был эффективен, ведущие цифры ключей должны быть распределены достаточно равномерно. Результирующий гибридный алгоритм поиска соответствует тому, как человек мог бы искать фамилии в телефонном справочнике. Вначале принимается многопутевое решение ( " Так, фамилия начинается на А " ), а затем, вероятно, принимается несколько двухпутевых решений ( " Она находится перед Анискин, но после Азазель " ), после чего символы сравниваются последовательно ( " Алгонавт... Нет, Алгоритмиста здесь нет, поскольку ни одно слово не начинается с Алгор! " ).

Программы 15.10—15.12 включают в себя основанную на TST-дереве реализацию операций таблицы символов найти и вставить, в которой используется R-путевое ветвление в корне и хранение элементов в листьях (поэтому здесь нет однонаправленных путей, если ключи различны).

Эти программы, похоже, являются наиболее быстрыми программами поиска строковых ключей или ключей с большим основанием системы счисления. Лежащая в их основе структура TST-дерева может поддерживать также множество других операций.

В таблице символов, которая разрастается до очень больших размеров, можно согласовывать коэффициент ветвления с размером таблицы. В главе 16 будет показан систематический способ увеличения многопутевого trie-дерева, чтобы можно было воспользоваться преимуществами многопутевого поиска при произвольных размерах файлов.

Например, при наличии 1 миллиарда случайных строковых ключей, при R = 256 и при использовании на верхнем уровне таблицы размером R2 = 65536 , для выполнения типичного поиска потребуется около $$$ln 10^{9} — 2 ln 256 \approx 20.7 — 11.1 = 9.6$$$ сравнений байтов. Использование таблицы в верхней части дерева уменьшает затраты на поиск в два раза.

Если ключи действительно случайны, этой производительности можно достичь с помощью более непосредственных алгоритмов, использующих ведущие байты ключа и таблицу существования, как было описано в . Однако TST-деревья позволяют получить такую же производительность и при менее случайной структуре ключей.

Программа 15.10. Определения типов узлов в гибридном TST-дереве

Этот код определяет структуры данных, используемые в программах 15.11 и 15.12, которые предназначены для реализации таблицы символов с помощью TST-деревьев. Здесь используется R-путевое ветвление в корне: корень представляет собой массив heads, состоящий из R ссылок и индексированный первой цифрой ключей. Каждая ссылка указывает на TST-дерево, построенное из всех ключей, которые начинаются с соответствующей цифры. Этот гибрид сочетает в себе преимущества trie-деревьев (быстрый поиск с помощью индексации в корне) и TST-деревьев (эффективное использование памяти: один узел для каждого символа кроме корня).

  struct node
    { Item item; int d; node *l, *m, *r;
      node(Item x, int k)
        { item = x; d = k; l = 0; m = 0; r = 0; }
      node(node* h, int k)
        { d = k; l = 0; m = h; r = 0; }
      int internal()
        { return d != NULLdigit; }
    };
    typedef node *link;
    link heads[R];
    Item nullItem;
      

Интересно сравнить TST-деревья без многопутевого ветвления в корне со стандартными BST-деревьями при использовании случайных ключей. В соответствии с леммой 15.8 для выполнения поиска в TST-дереве требуется около lnN сравнений байтов, в то время как в стандартных BST-деревьях требуется около lnN сравнений ключей. В верхней части BST-дерева сравнения ключей можно выполнить с помощью сравнения всего одного байта, но в нижней части для выполнения сравнения ключа может потребоваться много байтовых сравнений. Но не это различие в производительности является решающим. Причины, по которым при использовании строковых ключей TST-деревья предпочтительнее стандартных BST-деревьев, таковы: они обеспечивают быстрый неудачный поиск; они непосредственно годятся для многопутевого ветвления в корне; и (что наиболее важно) они хорошо подходят для строковых ключей, не являющихся случайными, поэтому в TST-дереве длина поиска никогда не превышает длину ключа.

Программа 15.11. Вставка в гибридное TST-дерево для АТД таблицы символов

Данная реализация операции вставить использует TST-деревья, содержащие элементы в листьях (что обобщает программу 15.3). В ней используется R-путевое ветвление по первому символу и отдельные TST-деревья — для всех слов, начинающихся с каждого символа. Если поиск завершается на пустой ссылке, то создается лист для хранения элемента. Если поиск завершается в листе, создаются внутренние узлы, необходимые для различения найденного и искомого ключей. private:

  link split(link p, link q, int d)
    { int pd = digit(p->item.key(), d),
      qd = digit(q->item.key(), d);
      link t = new node(nullItem, qd);
      if (pd < qd)
        { t->m = q; t->l = new node(p, pd); }
      if (pd == qd)
        { t->m = split(p, q, d+1); }
      if (pd > qd)
        { t->m = q; t->r = new node(p, pd); }
      return t;
    }
    link newext(Item x)
      { return new node(x, NULLdigit); }
    void insertR(link h, Item x, int d)
      { int i = digit(x.key(), d);
        if (h == 0)
          { h = new node(newext(x), i); return; }
        if (!h->internal())
          { h = split(newext(x), h, d); return; }
        if (i < h->d) insertR(h->l, x, d);
        if (i == h->d) insertR(h->m, x, d+1);
        if (i > h->d) insertR(h->r, x, d);
      }
    public:
      ST(int maxN)
      { for (int i = 0; i < R; i++) heads[i] = 0; }
    void insert(Item x)
      { insertR(heads[digit(x.key(), 0)], x, 1); }
      

Программа 15.12. Поиск в гибридном TST-дереве для АТД таблицы символов

Данная реализация операции найти для TST-деревьев (построенных программой 15.11) похожа на поиск в многопутевом trie-дереве, но в ней каждый узел (за исключением корня) содержит только три, а не R, ссылки. Цифры ключа используются при спуске вниз по дереву, который завершается либо на пустой ссылке (неудачный поиск), либо в листе, содержащем ключ, который или равен (успешный поиск), или не равен (неудачный поиск) искомому ключу.

  private:
    Item searchR(link h, Key v, int d)
    { if (h == 0) return nullItem;
      if (h->internal())
        { int i = digit(v, d), k = h->d;
          if (i < k) return searchR(h->l, v, d);
          if (i == k) return searchR(h->m, v, d+1);
          if (i > k) return searchR(h->r, v, d);
        }
      if (v == h->item.key()) return h->item;
      return nullItem;
    }
  public:
    Item search(Key v)
    { return searchR(heads[digit(v, 0)], v, 1); }
      

Некоторые приложения не могут воспользоваться преимуществом R-путевого ветвления в корне — например, все ключи в примере с библиотечными номерами на рис. 15.18 рис 15.18 начинаются с буквы L или W. Для других приложений может требоваться более высокий коэффициент ветвления в корне: например, как было сказано, если бы ключи были случайными целыми числами, пришлось бы использовать максимально большую таблицу. Подобную зависимость от приложения можно использовать при настройке алгоритма на максимальную производительность, но не следует забывать о том, что одно из наиболее привлекательных свойств TST-деревьев — возможность не беспокоиться о зависимости от приложений и обеспечение достаточно высокой производительности без каких-либо настроек.

Вероятно, наиболее важное свойство trie-деревьев или TST-деревьев с записями в листьях заключается в том, что их характеристики производительности не зависят от длины ключа. Следовательно, их можно использовать для ключей произвольной длины. В разделе 15.5 мы рассмотрим одно очень эффективное приложение такого рода.

Упражнения

15.49. Нарисуйте trie-дерево существования, образованное вставками слов now is the time for all good people to come the aid of their party в первоначально пустое дерево. Используйте 27-путевое ветвление.

15.50. Нарисуйте TST-дерево существования, образованное вставками слов now is the time for all good people to come the aid of their party в первоначально пустое дерево.

15.51. Нарисуйте 4-путевое trie-дерево, образованное вставками элементов с ключами 01010011 00000111 00100001 01010001 11101100 00100001 10010101 01001010 в первоначально пустое дерево, в котором используются 2-разрядные байты.

15.52. Нарисуйте TST-дерево, образованное вставками элементов с ключами 01010011 00000111 00100001 01010001 11101100 00100001 10010101 01001010 в первоначально пустое дерево, в котором используются 2-разрядные байты.

15.53. Нарисуйте TST-дерево, образованное вставками элементов с ключами 01010011 00000111 00100001 01010001 11101100 00100001 10010101 01001010 в первоначально пустое дерево, в котором используются 4-разрядные байты.

15.54. Нарисуйте TST-дерево, образованное вставками элементов с ключами библиотечных номеров на рис 15.18 в первоначально пустое дерево.

15.55. Измените реализацию поиска и вставки в многопутевом trie-дереве, приведенную в программе 15.7, так, чтобы она работала для ключей фиксированной длины, которые являются w-байтовыми словами (т.е. не требуется указание конца ключа).

15.56. Измените реализацию поиска и вставки в TST-дереве, приведенную в программе 15.8, так, чтобы она работала для ключей фиксированной длины, которые являются w-байтовыми словами (т.е. не требуется указание конца ключа).

15.57. Экспериментально сравните время и объем памяти, требуемые для 8-путевого trie-дерева, построенного из случайных целых чисел с использованием 3-разрядных байтов, для 4-путевого trie-дерева, построенного из случайных целых чисел с использованием 2-разрядных байтов, и для бинарного trie-дерева, построенного из тех же ключей, при N = 103, 104, 105 и 106 (см. упражнение 15.14).

15.58. Измените программу 15.9 так, чтобы она посещала все узлы, соответствующие искомому ключу (аналогично операции сортировать).

15.59. Напишите функцию, которая для заданного целочисленного значения k выводит все ключи в TST-дереве, отличающиеся от искомого не более чем в k позициях.

15.60. Приведите полную характеристику длины внутреннего пути худшего случая R-путевого trie-дерева с N различными w-разрядными ключами.

15.61. Разработайте реализацию таблицы символов на основе многопутевых trie-деревьев, которая включает в себя деструктор, конструктор копирования и перегруженную операцию присваивания, а также поддерживает операции создать, подсчитать, найти, вставить, удалить и объединить для АТД первого класса таблицы символов, поддерживающей клиентские дескрипторы (см. упражнения 12.6 и 12.7).

15.62. Разработайте реализацию таблицы символов на основе многопутевых TST-деревьев, которая включает в себя деструктор, конструктор копирования и перегруженную операцию присваивания, а также поддерживает операции создать, подсчитать, найти, вставить, удалить и объединить для АТД первого класса таблицы символов, поддерживающей клиентские дескрипторы (см. упражнения 12.6 и 12.7).

15.63. Напишите программу, которая выводит все ключи в R-путевом trie-дереве, имеющие те же первые t байтов, что и заданный ключ поиска.

15.64. Измените реализацию поиска и вставки в многопутевом trie-дереве, приведенную в программе 15.7, чтобы исключить однонаправленные пути, как в patricia-деревьях.

15.65. Измените реализацию поиска и вставки в TST-дереве, приведенную в программе 15.8, чтобы исключить однонаправленные пути, как в patricia-деревьях.

15.66. Напишите программу, которая балансирует BST-деревья, представляющие внутренние узлы TST-дерева (реорганизует их так, чтобы все их внешние узлы располагались на одном или двух уровнях).

15.67. Напишите версию операции вставить для TST-деревьев, которая поддерживает представление всех внутренних узлов в виде сбалансированных деревьев (см. упражнение 15.66).

15.68. Приведите полную характеристику длины внутреннего пути худшего случая TST-дерева, содержащего N различных w-разрядных ключей.

15.69. Напишите программу, генерирующую случайные 80-байтовые строковые ключи (см. упражнение 10.19). Воспользуйтесь этим генератором для построения 256-пу-тевого trie-дерева, содержащего N случайных ключей при N = 103, 104, 105 и 106 , применяя операцию найти, а после неудачного поиска — операцию вставить. Программа должна выводить общее количество узлов в каждом дереве и общее время построения каждого дерева.

15.70. Выполните упражнение 15.69 для TST-деревьев. Сравните полученные характеристики производительности с характеристиками trie-деревьев.

15.71. Напишите программу, которая генерирует ключи, тасуя случайную 80-байтовую последовательность (см. упражнение 10.21). Воспользуйтесь полученным генератором ключей для построения 256-путевого trie-дерева, содержащего N случайных ключей при N = 103, 104, 105 и 106 . Для вставки применяйте операцию найти, а после неудачного поиска — операцию вставить. Сравните полученные характеристики производительности с характеристиками для случайных ключей из упражнения 15.69.

о 15.72. Напишите программу, которая генерирует 30-байтовые случайные строки из четырех полей: 4-байтового поля, содержащего одну из 10 заданных строк; 10-байтового поля, содержащего одну из 50 заданных строк; 1-байтового поля, содержащего одно из двух заданных значений; и 15-байтового поля, содержащего случайные буквенные выровненные влево строки, длина которых с равной вероятностью может составлять от 4 до 15 символов (см. упражнение 10.23). Воспользуйтесь этим генератором ключей для построения 256-путевого trie-дерева, содержащего N случайных ключей при N = 103, 104, 105 и 106 . Для вставки применяйте операцию найти, а после неудачного поиска — операцию вставить. Обеспечьте возможность вывода общего количества узлов в каждом trie-дереве и общего времени, затраченного на построение каждого trie-дерева. Сравните полученные характеристики производительности с характеристиками для случайных ключей (см. упражнение 15.69).

15.73. Выполните упражнение 15.72 для случая TST-деревьев. Сравните полученные характеристики производительности с характеристиками для trie-деревьев.

15.74. Разработайте реализацию операций найти и вставить для ключей в виде строк байтов, использующую многопутевые деревья цифрового поиска.

15.75. Нарисуйте 27-путевое DST-дерево (см. упражнение 15.74), образованное вставками элементов с ключами now is the time for all good people to come the aid of their party в первоначально пустое дерево.

15.76. Разработайте реализацию поиска и вставки в многопутевом trie-дереве, в котором для представления узлов trie-дерева используются связные списки (в отличие от используемого для TST-деревьев представления в виде BST-дерева). Определите экспериментальным путем, что эффективнее использовать: упорядоченные или неупорядоченные списки, и сравните эту реализацию с реализацией на основе TST-деревьев.

Алгоритмы индексирования текстовых строк

В был рассмотрен процесс построения индекса строк, где для определения, присутствует ли в длинном тексте заданная ключевая строка, использовалось BST-дерево с указателями на подстроки. В этом разделе мы рассмотрим более сложные реализации этого АТД, использующие многопутевые trie-деревья, но отправная точка остается той же. Каждая позиция в тексте считается началом строкового ключа, который простирается до конца текста. Из этих ключей строится таблица символов, содержащая указатели на строки. Все ключи различны (хотя бы потому, что все они имеют различную длину), и почти все они очень велики. Цель поиска состоит в определении, является ли заданный искомый ключ префиксом одного из ключей в индексном указателе, что эквивалентно определению того, присутствует ли искомый ключ где-либо в текстовой строке.

Дерево поиска, которое построено из ключей, определенных индексами символов текстовой строки, называется деревом суффиксов (suffix tree). Для его построения можно воспользоваться любым алгоритмом, допускающим ключи переменной длины. Особенно подходят методы, основанные на применении trie-деревьев (за исключением методов, формирующих однонаправленные пути из окончаний ключей), поскольку их время выполнения зависит не от длины ключей, а только от количества цифр, необходимых для различения. Такое поведение прямо противоположно, например, алгоритмам хеширования, которые нельзя непосредственно применить для решения этой задачи, т.к. их время выполнения пропорционально длине ключей.

На рис 15.20 приведены примеры строковых индексов, построенных с использованием BST-деревьев, patricia-деревьев и TST-деревьев (с листьями). В этих индексах используются только ключи, которые начинаются на границах слов; индексирование, начинающееся с границ символов, позволило бы построить более сложный индекс, но при этом потребовало бы гораздо больше памяти.

Строго говоря, даже текст, состоящий из случайной строки, не приводит к случайному набору ключей в соответствующем индексе (поскольку ключи не являются независимыми). Однако в реальных приложениях, использующих индексирование, редко приходится иметь дело со случайными текстами, и это теоретическое несоответствие не помешает нам пользоваться преимуществом быстрых реализаций индексирования, возможных благодаря поразрядным методам. Мы не будем подробно рассматривать характеристики производительности при использовании каждого из этих алгоритмов для построения строкового индекса, т.к. многие компромиссы, связанные с общими таблицами символов со строковыми ключами, проявляются и при решении задачи индексирования строк.

Здесь показаны индексы текстовых строк, построенные из текста call me ishmael some years ago never mind how long precisely... с использованием BST-дерева (вверху), patricia-дерева (в центре) и TST-дерева (внизу). Узлы, содержащие указатели на строки, отмечены первыми четырьмя символами указываемых строк.

Для обычного текста в первую очередь, вероятно, стоит рассмотреть реализации на основе стандартных BST-деревьев, поскольку их легко реализовать (см. упражнение 12.10). Для типичных приложений это решение должно обеспечить хорошую производительность. Один из побочных эффектов взаимной зависимости ключей — особенно при построении строкового индекса для каждой символьной позиции — то, что худший случай BST-деревьев не будет особой проблемой в очень больших текстах, поскольку несбалансированные BST-деревья возникают только в крайне причудливых случаях.

Patricia-деревья изначально разрабатывались для приложений строкового индексирования. Для использования программ 15.5 и 15.4 потребуется лишь обеспечить реализацию функции bit, чтобы при заданном указателе на строку и целочисленном значении i она возвращала i-й бит строки (см. упражнение 15.82). На практике высота patricia-дерева, реализующего индекс текстовой строки, будет логарифмической. Кроме того, patricia-дерево обеспечивает быстрые реализации неудачного поиска, т.к. в нем нет необходимости проверять все байты ключа.

TST-деревья обеспечивают некоторые преимущества в производительности, характерные для patricia-деревьев, легко реализуются и используют встроенные операции доступа к байтам, обычно присутствующие в современных компьютерах. Кроме того, они допускают простые реализации, подобные программе 15.9, которые могут решать и задачи, более сложные, чем поиск полного соответствия с искомым ключом. Для построения строкового индекса на основе TST-дерева необходимо удалить код, обрабатывающий конечные части ключей в структуре данных, поскольку ни одна строка гарантированно не является префиксом другой и, следовательно, никогда не придется сравнивать строки вплоть до их конца. При этом нужно изменить определение операции == в интерфейсе типа элемента, чтобы две строки считались равными, если одна из них является префиксом другой, как это было сделано в разделе 12.7 , поскольку мы будем сравнивать ключ поиска (короткий) с текстовой строкой (длинной), начиная с некоторой позиции внутри текстовой строки. Третье удобное изменение — хранение в каждом узле не символов, а их индексов в строке, чтобы каждый узел в дереве ссылался на позицию в текстовой строке (позицию, которая следует за первым вхождением строки, определенной символами на ветвях равенства от корня до этого узла). Реализация перечисленных изменений — интересное и поучительное упражнение, ведущее к созданию гибкой и эффективной реализации индекса текстовых строк (см. упражнение 15.81).

Несмотря на все описанные преимущества, важно помнить, что в обычных приложениях, использующих индексирование текста с помощью DST-деревьев, patricia-деревьев или TST-деревьев, сам текст фиксирован, и поэтому нет необходимости использовать динамические операции вставить. То есть, как правило, индекс строится один раз, а затем без каких-либо изменений используется для выполнения очень большого количества поисков. Следовательно, динамические структуры данных типа BST-деревьев, patricia-деревьев или TST-деревьев могут оказаться вообще ненужными: достаточно базового алгоритма бинарного поиска. Индекс представляет собой набор указателей на строки, а формирование индекса эквивалентно сортировке этих указателей. Основное преимущество бинарного поиска по сравнению с динамическими структурами данных заключается в экономии памяти. Для индексирования текстовой строки в N позициях при помощи бинарного поиска требуется лишь N указателей на строки; а для индексирования строки в N позициях с помощью метода, основанного на каком-либо дереве, требуется, по меньшей мере 3N указателей (один указатель на строку и еще две ссылки на поддеревья). Как правило, индексные указатели текста имеют очень большой размер, поэтому бинарный поиск может оказаться более удобным, т.к. он гарантирует логарифмическое время поиска, но при этом использует менее трети памяти, используемой методами на основе деревьев. Но при наличии достаточного объема доступной памяти TST- или trie-деревья позволяют для многих приложений реализовать более быстрые операции найти, т.к., в отличие от бинарного поиска, перемещение по ключам выполняется без возвратов.

Если имеется очень большой текст, но ожидается немного поисков в нем, то построение полного индексного указателя, видимо, будет неоправданным. Задача поиска строк состоит в быстром определении, содержит ли текст заданный искомый ключ (без предварительной обработки текста). Между этими двумя крайними случаями — без предварительной обработки и с построением полного индекса — находится много других задач обработки строк.

Упражнения

15.77. Нарисуйте 26-путевое DST-дерево, образованное в результате индексирования текстовой строки из слов now is the time for all good people to come the aid of their party.

15.78. Нарисуйте 26-путевое trie-дерево, образованное в результате индексирования текстовой строки из слов now is the time for all good people to come the aid of their party.

15.79. Нарисуйте TST-дерево, образованное в результате индексирования текстовой строки из слов .

15.80. Нарисуйте TST-дерево, образованное в результате индексирования текстовой строки из слов now is the time for all good people to come the aid of their party. Используйте описанную в тексте реализацию, в которой TST-дерево содержит в каждом узле указатели на символы строк.

15.81. Измените реализации поиска и вставки в TST-дерево, приведенные в программах 15.11 и 15.12, чтобы обеспечить индексирование строк на основе TST-дерева.

15.82. Реализуйте интерфейс, позволяющий с помощью patricia-деревьев обрабатывать строковые ключи в стиле C (т.е. массивы символов), как если бы они были битовыми строками.

15.83. Нарисуйте patricia-дерево, образованное в результате индексирования текстовой строки из слов now is the time for all good people to come the aid of their party при использовании 5-разрядного двоичного кодирования, когда i-я буква алфавита кодируется двоичным представлением числа i.

15.84. Объясните, почему неэффективна идея улучшения бинарного поиска с помощью того же базового принципа, на котором основаны TST-деревья (сравнение символов, а не строк).

15.85. Найдите в вашей системе большой (не менее 10⁶ байтов) текстовый файл и сравните высоту и длину внутреннего пути стандартного BST-дерева, patricia-дерева и TST-дерева, полученных в результате построения индексного указателя для данного файла.

15.86. Экспериментально сравните высоту и длину внутреннего пути стандартного BST-дерева, patricia-дерева и TST-дерева, полученных в результате построения индексного указателя для текстовой строки, состоящей из N случайных символов 32-символьного алфавита при N = 103, 104, 105 и 106 .

15.87. Напишите эффективную программу для определения самой длинной повторяющейся последовательности в очень длинной текстовой строке.

15.88. Напишите эффективную программу для определения 10-символьной последовательности, чаще всего встречающейся в очень длинной текстовой строке.

15.89. Постройте индекс строки, который поддерживает операцию, возвращающую количество вхождений ее аргумента в индексированном тексте, а также поддерживает, подобно операции сортировать, операцию найти, которая посещает все позиции в тексте, соответствующие искомому ключу.

15.90. Опишите текстовую строку, состоящую из N символов, для которой индексирование, основанное на применении TST-дерева, работает особенно плохо. Оцените затраты на индексирование этой же строки с помощью BST-дерева.

15.91. Пусть нужно проиндексировать случайную N-разрядную строку для позиций разрядов, кратных 16. Экспериментально определите, какие размеры байтов (1, 2, 4, 8 или 16) ведут к наименьшему времени индексирования с помощью TST-дерева, при N = 103, 104, 105 и 106 .