ковых указателей (см. раздел 12.4). Индекс - это набор строковых указателей; построение индекса - это сортировка строковых указателей. Основное преимущество использования бинарного поиска по сравнению с динамическими структурами данных заключается в экономии используемого объема памяти. Для индексирования текстовой строки в N позициях при помощи бинарного поиска требуется всего лишь N строковых указателей; и напротив, для индексирования строки в 7V позициях за счет использования метода, основанного на деревьях, требуется по меньшей мере 3iV указателей (один строковый указатель для текста и две связи). Как правило, индексные указатели текста огромны, поэтому бинарный поиск может оказаться более предпочтительным, т.к. гарантировано обеспечивает логарифмическую зависимость времени поиска, но при этом задействуется лишь одна треть объема памяти, используемого методами, основанными на деревьях. Однако, при наличии достаточного объема доступной памяти TST-деревья позволяют реализовать более быстрые операции search для многих приложений, поскольку, в отличие от бинарного поиска, перемещение по ключам выполняется без возвратов.

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

Упражнения

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

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

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

> 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 Реализуйте интерфейс, который позволяет palricia-алгоритму обрабатывать строковые ключи в стиле С (т.е. массивы символов), как если бы они были строками разрядов.

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

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

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

15.86 Экспериментально сравните высоту и длину внутреннего пути стандартного BST-дерева, patricia-дерева и TST-дерева, полученных в результате построения индексного указателя для текстовой строки, состояшей из случайных символов 32-символьного алфавита при = 10 Ю *, 10 и 10.

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

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

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

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

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

Внешний поиск

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

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