Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 35
Текст из файла (страница 35)
32 и 12 (из раздела 6,2.2), тек как последнее дерево было построено тем же способом, но с использованием сравнения ключей вместо битов. Если принять во внимание данные частбты появления слов, цифровой поиск по дереву на рнс. 32 потребует в среднем 3.42 сравнений при успешном завершении поиска. Это несколько лучше, чем в случае дерева, показанного на рнс, 12, для которого требуется 4.04 сравнения (хотя, конечно же., время самого сравнения различно для зтих двух ситуаций). Рис. 32. Дерево цифрового поиска для 31 наиболее употребительного английского слова, вставленного в порядке уменьшения частот.
Алгоритм О (4п4ровой поиск со всгпоекой по дереву). Дана таблица записей, представляющих бинарное дерево, которое описано выше. Алгоритм предназначен для поиска некоторого аргумента К. Если К отсутствует в таблице, новый узел, содержащий К, вставляется в дерево в соответствующем месте. Алгоритм предполагает, что дерево не пусто и что его узлы имеют поля КЕТ, ШНК и НАТЕК, такие же, как в алгоритме 6.2,2Т.
В действительности, как вы можете убедиться сами, алгоритмы практически идентичны. 01. (Инициализация.] Установить Р < — КООТ и К'+- К. 02, (Сравнение.] Если К = Кеу(Р), поиск успешно завершается. В противном случае установить б равным лидирующему биту К' и сдвинуть К' влево на один бит (тем самым удалив этот бит и вставив О справа). Если Ь = О, перейти к шагу 03; в противном случае перейти к шагу П4. ?)3. [Перемещение влево.] Если ?.ЫМК(Р) З1 Л, установить Р < — 1Л.1МК(Р) н перейти к шагу 02.
В противном случае перейти к шагу?)5. Х)4. [Перемещение вправо.] Если Н1.1МК(Р) ф Л, установить Р <- ВЫМЕ(Р) и перейти к шагу 02. ?)5. [Вставка в дерево.] Установить Я ч.= АТА1?., КЕТ(Я) +- К, ~.ЫМК(Ц) +- ВЫМЕ(Ц) Л, Если Ь = О„присвоить 51.1МК(Р) ~- Я; в противном случае присвоить ВЫМЕ(Р) +- Я 1 Хотя алгоритм поиска ио дереву 6.2.2Т по сути своей бинарный, не сложно увидеть, что он может быть распространен на М-арный цифровой поиск для любого Ад > 2 (см. упр.
13). Дональд Р. Моррисон (Х)опа?6 В.. Магг?воп) [.?АСМ 15 (1968), 514-534] открыл весьма привлекательный способ построения Лцузловых деревьев поиска, основанных на бинарном представлении ключей бег необходимости их хранения в узлах.
Этот метод, названный "Патриция" (Распс?а — Ргасс?са? А?8опсЬпс То Неспето 1п1опиаСюп Сог?е? 1п А?рЬапшпепс), очень хорошо подходит для работы с большими ключами переменной длины, например с заголовками нли фразами, хранящимися в файле большого объема. Похожий алгоритм быч одновременно опубликован в Германик (С. СжеЬепЪегБег, Е)ейсгопмсйе ВесЬепап)а8еп 10 (1968), 223-226).
Основная суть метода "Патриция" состоит в построении бинарного дерева без однопутевых ветвей посредством включения в каждый узел количества битов, которые можно пропустить, прежде чем приступить к следующему тесту. Существует несколько способов реализации этой идеи; возможно, простейший из них представлен на рис. 33.
Имеется массив битов ТЕХТ (обычно довольно длинный), который может храниться ва внешнем файле с произвольным доступом, поскольку прн каждом поиске обращение к ТЕХТ осуществляется только один раз. Каждый ключ, который должен храниться в нашей таблице, определяется местом его начала в тексте; можно считать, что он идет от места своего начала и до конца текста. (Метод "Патриция' не ищет точного соответствия между ключом и аргументом; вместо этого определяется, существует ли ключ, ночиноюн(ийсл с аргумента). В ситуации, показанной на рис.
33, представлено семь ключей, которые начинаются с каждого входящего в текст слова, а именно — с "ТН1Б 15 ТНЕ НОННЕ ТНАТ БАСК В011ТТ", "15 ТНЕ НООБЕ ТНАТ БАСК ВОХЬТ?",..., "ВО11ТТ". Имеется одно важное ограничение: ни один ключ не может бмгль началом другого. Оно выполняется, если текст завершается специальным символом конца текста (в нашем случае это "Т"), который не встречается нигде в тексте, То же ограничение неявно применяется и в схеме луча алгоритма Т, в которой признаком конца слова служит "„". Дерево, используемое методом "Патриция" для поиска, должно целиком размещаться в оперативной памяти с произвольным доступом (илн должно быть организовано по страничной схеме, описанной в разделе 6.2.4).
Оно состоит из заголовка и Ю вЂ” 1 узла; узлы имеют несколько полей. КЕТ, указатель на текст. Это пале должно иметь длину как минимум ?8 С бит, если текст содержит С символов. На рис. ЗЗ слова, показанные внутри »»» ~ ~~ »~ к» ~»»»»»»» »»», м»»»»»»»»»»»»»» Заголовок Рис. 33. Пример текста и дерева метод» "Патриция". каждого узла, на самом деле представлены указателями на текст, например вместо (ЛАСКЛ узел содержит число 24, которое указывает начальное положение ЛАСК ВОП.ТТ в текстовой строке, 1,11ИК и ВНИК, ссьглки внутри дерева.
Длина этих полей должна составлять не менее 1ЗХ бит. ЕТАС и КТАС, однобитовые поля„которые указывают, являются ли ШИК и Ы,1ИК ссылками на дочерние или родительские узлы данного узла соответственно. Пунктирные линии на рис. ЗЗ соответствуют указателям, биты ТАС которых равны 1, ЗКХР, число, которое указывает, сколько битов должно быть пропущено при поиске (как объяснялось ранее). Это поле должно быть достаточно велико для хранения наибольшего числа А, для которого в двух различных ключах найдутся совпадающие подцепочки из lг бит. Обычно на практике можно считать, что А не слишком велико, и сообщать об ошибке при превышении размеров паля ЗКХР. На рнс. 33 поля ЗК1Р показаны как числа внутри узлов, Заголовок содержит толью поля КЕТ, 11.1ИК и БОТАС.
Поиск в дереве метода "Патриция" вьгполняется следующим образом. Предположим, необходимо найти слово ТКЕ (его битовое представление — 10111 01000 00101~. Начинаем просмотр с поля ЗКХР в корневом узле гт, которое указывает, что следует проверить первый бит аргумента. Этот бит равен 1, и потому мы должны двигаться вправо. Поле ЗК1Р следукпцего узла, у, указывает, что теперь нужно обратить внимание на 1+ 11 = 12-й бит аргумента. Он равен О, поэтому мы движемся влево. Поле ЗК1Р следующего ума, е, заставляет нас взглянуть на (12+ Ц-й бит, равный 1. Находим, что НТАО = 1, так что следует вернуться к узлу у, который отсылает нас к массиву ТЕХТ.
Тот же путь поиска будет получен для любого аргумента, битовая маска которого равна 1хххх ххххх х01..., и необходимо проверить, не соответствует ли аргумент уникальному ключу, начинающемуся с этой маски, а именно — с ТНЕ. Предположим, с другой стороны, что нужно найти некоторый ключ, начинающийся с ТН (илн все такие ключи). Процесс поиска начинается так же, как описывалось выше, но в конечном счете мы попьпаемся обратиться к несуществующему двенадцатому биту десятибитового аргумента. Теперь необходимо сравнить аргумент с фрагментом массива ТЕХТ, определяемым в текущем узле (в нашем случае — узле ~).
Если совпадения не произошло, значит, аргумент не начинается ни с одного ключа; если же совпадение имело место, то аргумент служит началом любого ключа, на который указывают пунктирные линии, выходящие из узла Т н его потомков (а именно -- ТН18, ТНАТ, ТНЕ). Более точно процесс можно описать следующим образом. Алгоритм Р ( вПаглрнцня").
Дан массив ТЕХТ и дерево с описанными выше полями КЕТ, (.ь1ИК, Н(.1ИК, СТАО, НТАО и ЯК1Р. Алгоритм определяет, имеется ли в массиве ТЕХТ ключ, начинающийся с некоторого аргумента К, (Если имеется г > 1 таких ключей, эа 0(г) шагов можно последовательно установить расположение каждого иэ них; см. упр. 14.) Предполагается, что имеется, по меньшей мере, один ключ. Р1.
[Инициализация.] Установить Р < — НЕАР и ) +- О. (Переменная Р представляет собой указатель, который будет перемещаться вниз по дереву, а у — счетчик„ определяющий позиции битов аргумента.) Установить и равным количеству битов в аргументе К. Р2. [Движение влево.] Присвоить Я <- Р и Р +- (.ь1ИК(й) .
Если ЕТАО(Ц) = 1, перейти к шагу Рб. РЗ. [Пропуск битов.] (В этот момент известно, что если первые у бит К соответствуют некоторому ключу, то они соответствуют ключу, начинающемуся в КЕТ(Р)). Установить ) ~ — 1 + ЗКТР(Р). Если,у > и, перейти к шагу Рб. Р4. [Проверка бита.] (В этот момент известно, что если первые 1 — 1 бит аргумента соответствуют некоторому ключу, то они соответствуют ключу, начинающемуся в КЕТ(Р)). Если .у-й бит аргумента равен О, перейти к шагу Р2; в противном случае — к шагу Рб. Рб.
[Перемещение вправо.) Присвоить Ц <- Р и Р +- Н(.1ИК(Ц). Если НТАО(Ц) = О, перейти к шагу РЗ. РН. [Сравнение.] (В этот момент известно, что если аргумент соответствует некоторому ключу, то он соответствует ключу, начинающемуся в КЕТ(Р)). Сравнить К с ключом, начинающимся в позиции КЕТ(Р) в массиве ТЕХТ. Если они эквивалентны (до и-го бита (длины К)), то алгоритм успешно завершается; в случае неравенства он завершается неудачей. $ В упр. 15 показано, каким образом может быть построено дерево метода "Патриция": Можно также вносить дополнения к тексту и вставлять новые ключи, если новый текстовый материал всегда заканчивается уникальным разделителем (например, символом конца текста с последующим серийным номером).
Алгоритм "Патриция" несколько причудлив, и требуется внимание для выявления всех его достоинств. Анализ алгоритмов. Завершается этот раздел математическим анализом лучей., деревьев цифрового поиска и метода "Патриция". Важнейшие выводы будут приведены в самом конце раздела. Сначала рассмотрим бинарные лучи, т. е. лучи с М = 2. На рис.
34 показан бинарный луч, который был получен при рассмотрении шестнадцати ключей из примеров сортировки (глава 5) в качестве 10-битовых двоичных чисел. (Ключи показаны в восьмеричной записи, например 1144 представляет собой десятибитовое число 612 = (1001100100)э.) Как и в алгоритме Т, для хранения информации о ведущих битах ключей (до тех пор, пока ключ не идентифицируется однозначно) используется луч, в котором ключ записывается полностью. Рнс.
34. Пример случайного бинарного луча. Если сравнить рнс. 34 с табл. 5.2.2-3, обнаружится удивительная взаимосвязь между "лучевой" памятью и обменной поразрядной сортировкой. (Возможно, эта связь очевидна.) 22 узла на рис. 34 точно совпадают с 22 стадиями из табл. 5.2.2 — 3 с оютветствнем р-го узла в предварительном порядке р-й стадии. Количество проверяемых на стадиях разбиения битов равно числу ключей в соответствующих узлах и их подлучах; значит, можно сформулировать следующий результат.
Теорема Т. Если У различных двоичных чисел помещены в описанный выше бинарный луч, то (!) количество узлов луча равно количеству стадий разбненяя лря обьгеннод поразрядной сортировке н (й) среднее количество проверок битов, требующееся для выборки ключа с помощью алгоритма Т, равно 1/Аг ог количества проверок битов пря обменной поразрядной сортировке. 5 Благодаря этой теореме можно использовать весь математический аппарат, разработанный лля поразрядной сортировки в разделе 5.2.2. Например, если предположить, что ключами являются случайные ранномерно распределенные между 0 и 1 числа, заданные с бесконечной точностью, то количество проверок битов, необходимое для выборки, равно!5 Х+ "г/!и 2+ 1/2+ 5(йг) + 0(Х '), а число узлов луча — Ю/)п 2+об(ЛХ)+О(1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
