THISuISuTHEuHOUSEuTHATuJACKuBUILT?

10111 О1СКЮ01ОО1 lOllU 00000 01001 lOllO 00000 10111 01000 OOJOI 01)000 01000 10000 11000 lOlIO 00101 00000 10111 01000 00001 10111 OODOOOIon OOWI 00011 01100 00000 OOOlO 1100001001 01101 IDIII llltl

Заголовок

(HOUSE)

Рис. 33. Пример текста и дерева метода "Патриция".

каждого узла, на самом деле представлены указателями на текст, например вместо (JACK) узел содержит число 24, которое указывает начальное положение JACK BUILT? в текстовой строке.

LLINK и RLINK, ссылки внутри дерева. Длина этих полей должна составлять не менее Ig N бит.

LTAG и RTAG, однобитовые поля, которые указывают, являются ли LLINK и RLINK ссылками на дочерние или родительские узлы данного узла соответственно. Пунктирные линии на рис. 33 соответствуют указателям, биты TAG которых равны 1.

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

Заголовок содержит только поля KEY, LLINK и LTAG.

Поиск в дереве метода "Патриция" выполняется следующим образом. Предположим, необходимо найти слово THE (его битовое представление - 101110100000101). Начинаем просмотр с поля SKIP в корневом узле а, которое указывает, что следует проверить первый бит аргумента. Этот бит равен 1, и потому мы должны двигаться вправо. Поле SKIP следующего узла, 7, указывает, что теперь нужно обратить внимание на 1 -t-ll = 12-й бит аргумента. Он равен О, поэтому мы движемся влево. Поле SKIP следующего узла, е, заставляет нас взглянуть на (12-ь1)-й бит, равный 1.

Находим, что RTAG = 1, так что следует вернуться к узлу 7, который отсылает нас к массиву TEXT. Тот же путь поиска будет получен для любого аргумента, битовая маска которого равна IxxxxxxxxxxOl..., и необходимо проверить, не соответствует ли аргумент уникальному ключу, начинающемуся с этой маски, а именно - с THE.

Предположим, с другой стороны, что нужно найти некоторый ключ, начинающийся с ТН (или все такие ключи). Процесс поиска начинается так же, как описывалось выше, но в конечном счете мы попытаемся обратиться к несуществующему двенадцатому биту десятибитового аргумента. Теперь необходимо сравнить аргумент с фрагментом массива TEXT, определяемым в текущем узле (в нашем случае - узле 7). Если совпадения не произощло, значит, аргумент не начинается ни с одного ключа; если же совпадение имело место, то аргумент служит началом любого ключа, на который указывают пунктирные линии, выходящие из узла 7 и его потомков (а именно - THIS, THAT, THE).

Более точно процесс можно описать следующим образом.

Алгоритм Р ( "Патриция"). Дан массив TEXT и дерево с описанными выше полями KEY, LLINK, RLINK, LTAG, RTAG и SKIP. Алгоритм определяет, имеется ли в массиве TEXT ключ, начинающийся с некоторого аргумента К. (Если имеется г > 1 таких ключей, за 0{г) шагов можно последовательно установить расположение каждого из них; см. упр. 14.) Предполагается, что имеется, по меньшей мере, один ключ.

Р1. [Инициализация.] Установить Р <- HEAD и j <- 0. (Переменная Р представляет собой указатель, который будет перемещаться вниз по дереву, а j - счетчик, определяющий позиции битов аргумента.) Установить п равным количеству битов в аргументе К.

Р2. [Движение влево.] Присвоить Q Р и Р •f- LLINK(Q). Если LTAG(Q) = 1, перейти к шагу Рб.

РЗ. [Пропуск битов.] (В этот момент известно, что если первые j бит К соответствуют некоторому ключу, то они соответствуют ключу, начинающемуся в KEY(P)). Установить j j + SKIP(P). Если j > п, перейти к шагу Рб.

Р4. [Проверка бита.] (В этот момент известно, что если первые j - I бит аргумента соответствуют некоторому ключу, то они соответствуют ключу, начинающемуся в KEY(P)). Если j-й бит аргумента равен О, перейти к шагу Р2; в противном случае - к шагу Р5.

Р5. [Перемещение вправо.] Присвоить Q •f- Р и Р RLINK(Q). Если RTAG(Q) = О, перейти к шагу РЗ.

Рб. [Сравнение.] (В этот момент известно, что если аргумент соответствует некоторому ключу, то он соответствует ключу, начинающемуся в KEY(P)). Сравнить К с ключом, начинающимся в позиции KEY(P) в массиве TEXT. Если они эквивалентны (до п-го бита (длины К)), то алгоритм успешно завершается; в случае неравенства он завершается неудачей.

В упр. 15 показано, каким образом может быть построено дерево метода "Патриция" Можно также вносить дополнения к тексту и вставлять новые ключи, если новый текстовый материал всегда заканчивается уникальным разделителем (например, символом конца текста с последующим серийным номером).

Алгоритм "Патриция" несколько причудлив, и требуется внимание для выявления всех его достоинств.

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

Сначала рассмотрим бинарные лучи, т. е. лучи с М = 2. На рис. 34 показан бинарный луч, который был получен при рассмотрении шестнадцати ключей из примеров сортировки (глава 5) в качестве 10-битовых двоичных чисел. (Ключи показаны в восьмеричной записи, например 1144 представляет собой десятибитовое число 612 = (1001100100)2.) Как и в алгоритме Т, для хранения информации о ведущих битах ключей (до тех пор, пока ключ не идентифицируется однозначно) используется луч, в котором ключ записывается полностью.

0075

0127

04 23

0767

0775

г-> 1000

1144

J I1277

Рис. 34. Пример случайного бинарного луча.

Если сравнить рис. 34 с табл. 5.2.2-3, обнаружится удивительная взаимосвязь между "лучевой" памятью и обменной поразрядной сортировкой. (Возможно, эта связь очевидна.) 22 узла на рис. 34 точно совпадают с 22 стадиями из табл. 5.2.2-3 с соответствием р-го узла в предварительном порядке р-й стадии. Количество проверяемых на стадиях разбиения битов равно числу ключей в соответствующих узлах и их подлучах; значит, можно сформулировать следующий результат.

Теорема Т. Если N различных двоичных чисел помещены в описанный выше бинарный луч, то (i) количество узлов луча равно количеству стадий разбиения при обменной поразрядной сортировке и (ii) среднее количество проверок битов, требующееся для выборки ключа с помощью алгоритма Т, равно 1/N от количества проверок битов при обменной поразрядной сортировке.

Благодаря этой теореме можно использовать весь математический аппарат, разработанный для поразрядной сортировки в разделе 5.2.2. Например, если предположить, что ключами являются случайные равномерно распределенные между О и 1 числа, заданные с бесконечной точностью, то количество проверок битов, необходимое для выборки, равно lgiV-t-7/ln2-t- l/2--(5(iV) + 0{N~), а число узлов