вероятная операция; и задача выполняется путем 1 миллиона проверок непосредственно индексированных разрядов. Решение основывается на идее, что хеш-функция создает короткий сертификат, представляющий ключ; это важная концепция, находящая применение и в приложениях, которые отличаются от реализаций таблиц символов.

В качестве реализации таблиц символов хеширование предпочтительней структур бинарных деревьев, рассмотренных в главах 12 и 13, поскольку оно несколько проще и может обеспечить оптимальное (постоянное) время поиска, если ключи относятся к стандартному типу или достаточно просты, чтобы можно было быть уверенным в разработке хорошей хеш-функции для них. Преимущества структур бинарных деревьев по сравнению с хешированием заключается в том, что деревья основываются на более простом абстрактном интерфейсе (разработка хеш-функции не требуется); деревья являются динамическими (никакая предварительная информация о количестве вставок не требуется); деревья могут обеспечить гарантированную производительность в худшем случае (все элементы могут быть помещены в одну и ту же позицию даже при использовании наилучшего метода хеширования); и, наконец, деревья поддерживают более широкий диапазон операций (самое главное, операции sort и select). Когда эти факторы не имеют значения, безусловно следует выбирать хеширование, только с одной важной оговоркой: когда ключи представляют собой длинные строки, их можно встроить в структуры данных, которые могут обеспечить методы поиска, работающие еще быстрее хеширования. Подобного рода структуры - тема главы 15.

Упражнения

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

> 14.49 Для 1 миллиона целочисленных ключей вычислите количество сравнений, выполняемых каждым из трех методов хеширования (раздельным связыванием, линейным зондированием и двойным хешированием) в среднем для обнаружения промаха при поиске, когда они всего могут использовать 3 миллиона слов памяти (как имело бы место в случае BST-деревьев).

14.50 Реализуйте АТД таблицы символов, обеспечивающий быстрое обнаружение промаха при поиске, как описано в тексте, используя для второй проверки раздельное связывание.

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

Внескольких методах поиска обработка ведется за счет исследования ключей поиска по небольшим фрагментам за раз вместо того, чтобы на каждом шаге сравнивать полные значения ключей. Эти методы носят название поразрядного поиска (radix-search) и работают аналогично методам поразрядной сортировки, которые рассматривались в главе 10. Они удобны, когда фрагменты ключей поиска легкодоступны, и могут обеспечить эффективные решения для множества реальных применений поиска.

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

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

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

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

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

Обычно при поразрядном поиске вначале исследуются старшие цифры ключей. Многие методы непосредственно соответствуют методам поразрядной сортировки сначала по старшей цифре (most significant digit - MSD) подобно тому, как поиск, основанный на BST-дереве, соответствует быстрой сортировке. В частности, мы рассмотрим аналоги методов сортировки с линейной зависимостью времени выполнения, приведенных в главе 10 - методы поиска с линейной зависимостью времени выполнения, основанные на том же принципе.

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

А 00001 S 10011 Е 00101 R 10010 С 00011 Н 01000 I 01001 N 01110 G 00111 X 11000 М 01101 Р 10000 L 01100

15.1 Деревья цифрового поиска

простейший метод поразрядного поиска основан на использовании деревьев цифрового поиска (digital search trees - DST), на которые в дальнейшем будем ссылаться как на DST-деревья. Алгоритмы поиска и вставки аналогичны поиску в бинарном дереве, за исключением одного различия: ветвление в дереве выполняется не в соответствии с результатом сравнения полных ключей, а в соответствии с выбранными разрядами ключа. На первом уровне используется ведущий разряд; на втором уровне используется разряд, следующий за ведущим, и т.д., пока не

РИСУНОК 15.1 ДВОИЧНЫЕ ПРЕДСТАВЛЕНИЯ ОДНОСИМВОЛЬНЫХ КЛЮЧЕЙ

Подобно тому, как это было сделано в главе 10, в небольших примерах, приведенных на рисунках этой главы, 5-разрядное двоичное представление числа i используется для представления i-mou буквы алфавита, как здесь продемонстрировано на примере нескольких ключей. Предполагается, что биты нумеруются слева направо от О до 4.