AOP_Tom3 (1021738), страница 137
Текст из файла (страница 137)
Существует несколько способов реализации этой идеи; возможно, простейший из них представлен на рис. ЗЗ. Имеется массив битов ТЕХТ (обычно довольно длинный), который может храниться во внешнем файле с произвольным доступом, поскольку при каждом поиске обращение к ТЕХТ осуществляется только один раз. Каждый ключ, который должен храниться в нашей таблице, определяется местом его начала в тексте; можно считать, что он идет от места своего начала и до конца текста. (Метод "Патриция" не ищет точного соответствия между ключом и аргументом; вместо этого определяется, существует ли ключ, начинающийся с аргумента).
В ситуации, показанной на рис. 33, представлено семь ключей, которые начинаются с каждого входящего в текст слова, а именно — с "ТН18 18 ТНЕ НООБЕ ТНАТ )АСК ВО1ЬТ?", "1Я ТНЕ НОННЕ ТНАТ ЛАСК ВО1ЕТ?", ..., ьВО1ЬТ?". Имеется одно важное ограничение: ни один ключ не может быть началом другого. Оно выполняется, если текст завершается специальным символом конца текста (в нашем случае это "?" ), который не встречается нигде в тексте. То же ограничение неявно применяется и в схеме луча алгоритма Т, в которой признаком конца слова служит "„". Дерево, используемое методом "Патриция" для поиска, должно целиком размещаться в оперативной памяти с произвольным доступом (или должно быть организовано по страничной схеме, описанной в разделе 6.2.4).
Оно состоит из заголовка и )ч' — 1 узла; узлы имеют несколько полей. КЕТ, указатель на текст. Это поле должно иметь длину как минимум 18 С бит, если текст содержит С символов. На рис. ЗЗ слова, показанные внутри Т Н 1 Я и 1 Я и Т Н Е и Н О В Я Е и Т Н А Т Л А С Н и Н Я 1 Ь Т Т Заголовок Рнс, 33. Пример текста и дерева метода "Патриция'. каждого узла, на самом деле представлены указателями на текст, например влгесто (ЛАСК) узел содержит число 24, которое указывает начальное положение ЛАСК Б01БТТ в текстовой строке. 1Б1ИК и ББ1ИК, ссылки внутри дерева. Длина этих полей должна составлять не менее 1КЛг бит. БОТАС и БТАС, однобитовые поля, которые указывают, являются лн ШИК и ББ1ИК ссылками на дочерние или родительские узлы данного узла соответственно. Пунктирные линии на рис.
33 соответствуют указателям„биты ТАС которых равны 1. БК1Р, число, которое указывает, сколько битов должно быть пропущено при поиске (как объяснялось ранее). Это поле должно быть достаточно велико для хранения наибольшего числа А„для которого в двух различных ключах найдутся совпадающие подцепочки из )г бнт. Обычно на практике можно считать, что А не слишком велико, и сообщать об ошибке при превышении размеров поля ЯК1Р.
На рис. 33 поля ЯК1Р показаны как числа внутри узлов. Заголовок содержит только поля КЕУ, ЕЫИК и БОТАС. Поиск в дереве метода "Патриция" выполняется следующим образом. Предположим, необходимо найти слово ТБЕ (его битовое представление — 10111 01000 00101). Начинаем просмотр с поля ЯК1Р в корневом узле сг, которое указывает, что шгедует проверить первый бит аргумента. Этот бит равен 1, и потому мы должны двигаться вправо. Поле ЯК1Р следующего узла, Т, указывает, что теперь нужно обратить внимание на 1+ 11 = 12-й бит аргумента. Он равен О, поэтому мы движемся влево.
Поле БК1Р следующего узла, е, заставляет нас взглянуть на (12+ 1)-й бит, равный 1. Находим, что НТАО = 1, так что следует вернуться к узлу Т, который отсылает нас к массиву ТЕХТ. Тот же путь поиска будет получен для любого аргумента, битовая маска которого равна 1хххх хххххх01..., и необходимо проверить, не соответствует ли аргумент уникальному ключу, начинающемуся с этой маски, а именно .-- с ТНЕ. Предположим, с другой стороны, что нужно найти некоторый ключ, начинающийся с ТН (или все такие ключи), Процесс поиска начинается так же, как описывалось выше, но в конечном счете мы попытаемся обратиться к несуществующему двенадцатому биту десятибитового аргумента.
Теперь необходимо сравнить аргумент с фрагментом массива ТЕХТ, определяемым в текущем узле (в нашем случае — узле у), Если совпадения не произошло, значит, аргумент не начинается ни с одного ключа; если же совпадение имело место, то аргумент служит началом любого ключа, иа который указывают пунктирные линии, выходящие из узла Т и его потомков (а именно — ТН1Я, ТНАТ, ТНЕ). Более точно процесс можно описать следующим образом.
Алгоритм Р ( КПатрицил"). Дан массив ТЕХТ и дерево с описанными выше полями КЕТ, ШИК, КЕ1ИК, ЕТАО, НТАО и ЯК1Р. Алгоритм определяет, имеется ли в массиве ТЕХТ ключ, начинаклцийся с некоторого аргумента К. (Если имеется г > 1 таких ключей, за 0(г) шагов можно последовательно установить расположение каждого из них; см. упр. 14.) Предполагается, что имеется, по меньшей мере, один ключ. Р1. [Инициализация.] Установить Р ( — НЕАР и 1 ~- О. (Переменная Р представляет собой указатель, который будет перемещаться вниз по дереву, а )' — счетчик, определяющий позиции битов аргумента.) Установить и равным количеству битов в аргументе К. Р2.
(Движение влево.] Присвоить Ц +- Р и Р +- ЕЕ1ИК(Ц). Если ЕТАО(Ц) = 1, перейти к шагу Рб. РЗ. (Пропуск битов.] (В этот люмент известно, что если первые 1 бит К соответствуют некоторому ключу, то они соответствуют ключу, начинающемуся в КЕУ(Р)). Установить 1 +- ) + ЯК1Р(Р). Если ) > и, перейти к шагу Рб. Р4. ',"Проверка бита.] (В этот момент известно, что если первые ) — 1 бит аргумента соответствуют некоторому ключу, то они соответствуют ключу, начинающемуся в КЕТ(Р)).
Если )-й бит аргумента равен О, перейти к шагу Р2; в противном случае .— к шагу Р5. Р5. [Перемещение вправо.] Присвоить Ц < — Р и Р +- КЕ1ИК(Ц). Если НТАО(Ц) = О, перейти к шагу РЗ. Рб.(Сравнение.] (В этот момент известно, что если аргумент соответствует некоторому ключу, то он соответствует ключу, начинающемуся в КЕУ(Р)). Сравнить К с ключом, начинающимся в позиции КЕТ(Р) в массиве ТЕХТ. Если они эквивалентны (до и-го бита (длины К) ), то алгоритм успешно завершается; в случае неравенства он завершается неудачей. 1 В упр. 15 показано, каким образом может быть построено дерево метода "Патриция'! Можно также вносить дополнения к тексту и вставлять новые ключи, если новый текстовый материал всегда заканчивается уникальным разделителем (например, символом конца текста с последующим серийным номером).
Алгоритм "Патриция" несколько причудлив, и требуется внимание для вьивлсния всех его достоинств. Анализ алгоритмов. Завершается этот раздел математическим анализом лучей, деревьев цифрового поиска и метода "Патриция". Важнейшие выводы будут приведены в самом конце раздела. Сначала рассмотрим бинарные лучи, т. е. лучи с М = 2. На рис. 34 показан бинарный луч, который был получен при рассмотрении шестнадцати ключей из примеров сортировки (глава 5) в качестве 10-битовых двоичных чисел.
(Ключи показаны в восьмеричной записи, например 1Ц4 представляет собой десятибитовое число 612 = (1001100100)з.) Как и в алгоритме Т, для хранения информации о ведущих битах ключей (до тех пор, пока ключ не идентифицируется однозначно) используется луч, в котором ключ записывается полностью. Рнс.
34. Пример случайного бинарного луча. Если сравнить рис. 34 с табл. 5.2.2-3, обнаружится удивительная взаимосвязь между "лучевой" памятью и обменной поразрядной сортировкой. (Возможно, эта связь очевидна.) 22 узла на рис. 34 точно совпадают с 22 стадиями из табл. 5.2.2-3 с соответствием р-го узла в предварительном порядке р-й стадии. Количество проверяемых на стадиях разбиения битов равно числу ключей в соответствующих узлах и их подлучах; значит, можно сформулировать следующий результат. Теорема Т. Если Ас различных двоичных чисел наметены в описанный выше бинарный луч, то (с) количество узлов луча равно количеству стадий разбиения при обменной поразрядной сортировке я (й) среднее количество проверок бспов, требующееся для выборки ключа с помощью алгоритма Т, равно 1/А! от количества проверок битов при обменной поразрядной сортировке.
! Благодаря этой теореме можно использовать весь математический аппарат, разработанный для поразрядной сортировки в разделе 5.2.2. Например, если предположить, что ключами являются случайные равномерно распределенные месКду 0 и 1 числа, заданные с бесконечной точностью, то количество проверок битов, необходимое для выборки, равно !и Ас+ у/!и 2+ 1/2 4 5(Ас) + 0(Ас '), а число узлов луча — Х/ )п 2+ Хб(Ж) + 0(1). Здесь 5(Х) и Б(Х) — сложные функции, которыми можно пренебречь, поскольку их абсолютные значения никогда нс превышают 10 (см, упр, 5.2.2 — 38 и 5.2.2-48). Конечно же, перед нами стоит более трудная задача: обобщить результаты, полученные лля бинарных лучей, на случай ЛХ-арных лучей. Мы опишем лишь стартовую точку исследований, помещая детальные инструкции в упражнения.
Пусть Ам †- среднее число внутренних узлов в случайном М-арном луче поиска, который содержит Х ключей. Тогда Ае = А~ — — О и для Х > 2 имеем ЛГ~ А =1+ 1 и )(~, ~ ), э) ь ~ э " + ь.и = ч поскольку ЛХ! М м/Й~!... Йм! представляет собой вероятность того, что й~ ключей находятся в первом подлуче, ..., Iсм .— в ЛХ-м. Это соотношение люжет быть переписано как = 1+ М ~' ( )(ЛХ вЂ” 1) ь.4ь при Л' > 2 /Х~ (4) ь с использованием симметрии и суммирования по Йз,..., йм. Аналогично, если через Сч обозначить общее среднее количество проверок битов, необходимое для поиска всех Х ключей в луче, то Се = С, = О и См = Л'+ЛХ' ~~ ~~ )(М вЂ” 1)~ ~Сь при Х ) 2.
гЛ~ (5) Смэш — — Х+ М' ) (ЛХ вЂ” 1) ьСь при Л > О. ~й/ (6) Это выражение практически идентично выражению (5), однако появления Л'+ 1 вместо Ж в левой части уравнения достаточно для того, чтобы коренным образом изменить характер рекуррентности, а потому использовавшиеся при изучении (5) методы становятся неприемлемыми. Рассмотрим сначала бинарный цифровой поиск. На рис. 35 показано дерево цифрового поиска, соответствующее шестнадцати ключам из рис. 34, если они В упр. 17 показано, как работать с такого рода рекуррентными соотношениями, а в упр. 18 — 25 приводится соответствующая теория случайных лучей (с другой точки зрения анализ Ам был впервые проведен в работе Ь. В.. Лобпэоп, ЛХ. Н. МсАпбгек, ХВЛХ Х Век.
апс~ Х1еге!. 8 (1964), 189 — 193, в связи с эквивалентным аппаратноориентированвым алгоритмом сортировки). Если теперь перейти к изучению деревьев цифрового поиска, то обнаружится, что формулы похожи, однако не настолько, чтобы можно было легко определить асимптотическое поведение. Например, если через Сл обозначить среднее суммарное количество проверок битов при поиске всех Х ключей в М-арном дереве цифрового поиска, нетрудно вывести, как и ранее, что Се = С~ = О и вставляются в порядке, который использовался в примерах главы 5. Если будет необходимо определить среднее количество проверок битов при случайном успешном поиске, окажется, что это просто длина внутреннего пути дерева, деленная на Х, так как для поиска узла на уровне 1 потребуется 1 проверок.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
