РИСУНОК 15.13 ПРИМЕР PATRICIA-ДЕРЕВА

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

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

Лемма 15.5 Вставка или поиск случайного ключа в patricia-дереве, построенном из N случайных строк разрядов, требует приблизительно IgN сравнений разрядов в среднем и приблизительно 2 IgN сравнений разрядов в худшем случае. Количество сравнений разрядов никогда не превышает длины ключа.

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

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

Таблица 15.1 Экспериментальные результаты исследования реализаций trie-деревьев

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

конструирование попадания при поиске

Ключ:

В RB-дерево бинарного поиска (программы 12.8 и 13.6)

D DST-дерево (программа 15.1)

Т trie-дерево (программы 15.2 и 15.3)

Р patricia-дерево (программы 15.4 и 15.5)

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

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

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

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

Упражнения

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

[> 15.34 Нарисуйте patricia-дерево, образованное в результате вставки ключей Е А S YQUTIONb указанном порядке в первоначально пустое trie-дерево.

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

в указанном порядке в первоначально пустое trie-дерево.

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

в указанном порядке в первоначально пустое trie-дерево.

15.37 Экспериментально сравните высоту и длину внутреннего пути patricia-дерева, построенного в результате вставки Л случайных 32-разрядных ключей в первоначально пустое trie-дерево, с этими же характеристиками стандартного BST-дерева и RB-дерева (глава 13), образованных из этих же ключей, для jV = 10, Ю*, 10 и 10 (см. упражнения 15.6 и 15.14).

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

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

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

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

о 15.42 Создайте программу, которая выводит все ключи patricia-дерева, имеющие такие же начальные / разрядов, как и у заданного искомого ключа.

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

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

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