AOP_Tom3 (1021738), страница 135
Текст из файла (страница 135)
Е. О'Хе)1) (Асса 1пб 29 (1992), 241-265) создано для минимизации времени выполнения дисковых операций путем расположения соседних записей в одном цилиндре; тем самым поддерживается высокая эффективность работы приложений, в которых требуется одновременный доступ к множеству последовательных записей (в этом случае «ВВЯ выделяется курсивом и Н означает "яе))пепг)в)л — "последовательный"). БВ-дерево (см. Р. Реггая(па апб В.. Огояя), АТОС 27 (1995), 693-702; БОВА 7 (1996), 373 — 382) представляет собой элегантную комбинацию структуры В-дерева с деревьями "Патриция", о которых пойдет речь в разделе 6.3; в этом случае "БВ" записывается обычным шрифтом и 8 означает "яГПпб" — "строка". Такие деревья используются во многих приложениях для крупномасштабной обработки текстов и обеспечивают эффективную сортировку строк переменной длины на диске (Агбе, Геггаб)па, Сгояя|, ап)1 Чйгег, АТОС 29 (1997), 540 -548].
УПРАЖНЕНИЯ 1. (10) Какое В-дерево порядка 7 получится после вставки ключа 613 в дерево, показанное на рис. 30 (технелогия переливания не используется)? 2. (15) Выполните упр. 1, используя технологию переливания с разделением на три части, как в (10). 3. [ЯУ) Предположим, что ключи 1, .2, 3, .. в порядке возрастания вставляются в изначально пустое В-дерево порядка 101, Какой ключ приведет к появлению листьев на уровне 4: а) без использования переливания; Ь) при использовании переливания с разделением только на 2 части, как в (4); с) прн использовании В -дерева порядка 101 с переливанием и разделением на 3 части, как в (10)т 4. (Я1) (Байер (Вауег) и Мак-Крейт (МсСге)ЯЬГ).) Объясните, как выполнить вставки в обобщенное В-дерево так, чтобы нее узлы, кроме корня и листьев, имели не менее 4 гл — -' потомков.
б. (Я1) Предположим, что для узлов отведено по 1000 символов во внешней памяти. Если каждый указатель занимает 5 символов и если ключ имеет длину, кратную пяти и находящуюся в пределах от 5 до 50 символов, то каково минимальное количество символов, занятых в узле после его разделения в процессе вставки? (Рассмотрите только простую процедуру разделения, аналогичную описанной в тексте для В-дерева с ключом фиксированной длины без переливания; рассмотрите перемещение вверх ключа, который делает оставшиеся части наиболее близкими по размеру.) 6. (ЯЗ) Разработайте алгоритм удаления нз В-деревьев. 7. (ЯЯ) Разработайте алгоритм конкатенации В-деревьев (см.
раздел 6.2.3). 6. (НМЗ7) Рассмотрим обобгцение вставки в дерева, предложенное Мюнцем (Минея) и Узгалисом (1)хба))я), в котором каждая страница может содержать М ключей. Пусть в дерево вставлено Х случайных элементов, так что оно имеет 1)) + 1 внешний узел. Обозначим через Ьль вероятность того, что при неудачном поиске потребуется )г обращений к О) страницам и что он закончится е узле, родительский узел которого принадлежит странице, содержащей 1 ключей.
Пусть Вл (е) = 2 5 .гяь — соответствующая производящая О) 0) ь функция. Докажите, что В~О~(з) = бнх и в<"( ) = ~ ' 1ВЮ ( )+ '+' В"-и( ) д, 1<2 см; х )У+1 и-1 )ч+1 и — ! ,У+1 -1 )У+1 н~ В~м1( ) — В~ьц ( ) + В(м-И( ) к х,,+1 и-~ х + )у+1 л-~ Найдите асимптотическое поведение С!,, = 2,.', В~эн(1) — среднего числа страниц, к которым осуществляется обращение при неудачном поиске.
(Указание. Выразите рекуррентное соотношение с помощью матрицы — 3 О ... О 2х 3 -4 О 4 О О О О И'(х) = О О ...-М 1 0 О О ., М+1 — 2 Мало известно, даже пОи использовании иных эквивалентных алгоритмов, об оптимизации выделения памяти, минимизации количества необходимых операций И т.
П. Эта облает~ исследований должна черпать Ресхрсы Дла дальнейшего прогресса как из чистой, так и иэ прикладной математики. — ЭНГОНИ Г. ЕГГИНГЕР (АИ ГНО1ч'г Е. ОЕГЗЗНЕЕЯ) (1961) и сопоставьте Сь с многочленом Х-й степени в Иг(1)(. 9. (хх( Может ли идея В-деревьев использоваться для получения элементов линейного списка по позиции, а не по значению ключа (см.
алгоритм 6.2.3В)? ь 10. (85) Обдумайте, каким образом большой файл, организованный в ниде В-дерева, можно использовать для доступа и изменения со стороны большого числа однонременно работающих пользователей, чтобы пользователи различных страниц практически не мешали друг другу. 6.3. ЦИФРОВОЙ ПОИСК Вмксто методов поиска, основанных иа сравиеиии ключей, можно воспользоваться представлением ключей в виде последовательности цифр или букв.
Рассмотрим, например, "побуквенные метки" в больших словарях (или записных адресных книжках), которые позволяют мгновенно найти страницы со словами, начинающимися с определенной буквы". Развивая идею побуквенных меток до ее логического завершения, можно получить схему поиска, основанную иа повторяемом индексировании, которое проиллюстрировано в табл. 1. Предположим, что необходимо проверить, является ли данный аргумеит поиска одним из 31 наиболее употребительного английского слова (см. рис. 12 и 13 в разделе 6.2.2).
Данные представлены в табл. 1 в виде струкгпуры лучпее. Луч, по сути, — зто М-ариое дерево, узлы которого представляют М-местиые векторы с компонентами, соответствующими' цифрам или буквам. Каждый узел уровня ! является набором всех ключей, начинающихся с определенной пшшедовательности ! символов, которая называется его префиксом (ргедх); узел определяет разветвлеиие ~а М путей в зависимости от ! + 1 символа. Например, луч из табл.
1 содержит 12 узлов; узел (1) представляет собой корени, в котором мы ищем первую букву. Если первой буквой является, скажем, Н, из таблицы следует, что либо зто слово НОТ, либо такого слова вообще иет в таблице. В то же время, если первая буква — Н, то узел (1) отправит иас к узлу (9) для поиска второй буквы тем же способом. Узел (9) указывает, что вторая буква должна быть А, Н или 1.
Префикс узла (10) — НА. Пустые записи в таблице означают отсутствие связей. Узлы-векторы в табл. 1 расположены в соответствии с кодами символов Н1Х. Это означает, что "лучевой поиск" будет весьма быстрым, поскольку следует просто выбирать слова из массивов с использованием символов наших ключей в качестве индексов. Технологии быстрого миогопутевого принятия решения по индексу иазываются просмотром таблицы (гаЫе )оо11-а1) в отличие от поиска по таблице (саЫе !оо[с-пр) (см, Р. М.
Б!1егшап, САСМ 4 (1961), 172-173, 175]. Алгоритм Т ('Лу севой поиск" (Т)че зепгсй)). Дана таблица записей в форме М- ариого луча. Алгоритм осуществляет поиск по заданному аргументу К. Узлы луча представляют собой векторы, индексы которых изменяются от 0 до М вЂ” 1: каждый компонент такого вектора представляет собой ключ или ссылку (возможио, пустую). Т1. (Ииициализация.) Установить ссылочную переменную Р таким образом, чтобы оиа указывала яа кореяь луча. Т2.
[Ветвлеиие.) Установить )с равным следующему символу входного аргумента ключа К слева направо. (Если аргумеит полностью проскаинроваи, устапоиить * Наличие у страницы книги трех свободных сторон позволило однвжды переводчику этого раздела оснвстить свой словарь метквмн поиска до третьей буквы слева включительно, Прим. нерее. ЯЯ В оригинале используется термин 1же (произносится кек английское слово "1гу"), предложенный Э. Фредкиным (Е. Ртебйбп) [САСМ 3 (1900), 490 — 500). Этот терл1ин предстввлиет собой часть слова "ге1жета19 В русскам переводе будет использоваться часть слова "получение" (информвцни).
Н хотя при этом теряется апределеннэя игра слов, основанная нв схожести слов 1же н сгее, приобретается некоторый смысл, заложенный в слове лрч: быстрый четко определенный по направлению двнжения поиск. — Прим. иерее. )с равным "пустому" символу или символу "конец слова". Символ должен быть представлен в виде чиш!а в диапазоне 0 < )с < М). Обозначим через Х к-й элемент в НОРЕ(Р). Если Х представляет собой ссылку, перейти к шагу ТЗ, если Х вЂ” — ключ, перейти к шагу Т4. ТЗ. [Продвижение.] Если Х ф Л, установить Р < — Х и вернуться к шагу Т2; в противном случае алгоритм завершается неудачей. Т4. ]Сравнение.] Если Х = К, алгоритм завершается успешно; в противном случае алгоритм завершается неудачей.
$ Таблица 1 луч для з1 нлиБОлее унОтРеьитез!ьнОГО АнГлийскОГО слОВА (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) А В С 0 В Р С Н 1 В з Х и Н 0 Р 0 Н Ф и 9 Т 0 Ч и Х Ч 2 Заметим, что при неудачном поиске будет найден элемент, более всего совпадающий с искомым, что может оказаться полезным в некоторых приложениях. Для сравнения скорости работы данного алгоритма со скоростями других алгоритмов из этой главы напишем коротенькую И1Х-программу, в которой предполагается, что символы представляют собой байты, а максимальная длина ключа 5 байт.
Программа Т ( "Лучевой поиск" (2)зе гевгс)з )). В этой программе предполагается, что все ключи занимают одно слово машины И1Х; в случае, если в ключе содержится менее 5 символов, он дополняется пробелами справа, Поскольку мы используем коды символов И1Х, каждый байт аргумента поиска содержит число, меньшее 30. Ссылки представлены в виде отрицательных чисел в поле 0: 2 узла слова. гП = Р, гХ = непросканированная часть К, 1 Р +- указатель иа корень луча. С Т2. Ветвление С Получение следующего символа, т. е. А. С Ц е- Р+ /с.
С Р = йХИК(Ц). С ПА ППП гг ПК тП ПЛ. и. П - ° ...и ггпь. 1 1 Успешное завершение при гА = ЛС Выход при отсутствии в луче. 01 БТАКТ 08 08 2Н 1Ц 08 00 07 08 00 10 11 ГАПЛИЕ ЬОХ К ЕИТ1 БООТ БЬАХ 1 БТА и+1(2:2) ЕИТ2 0,1 1.01И 0,2(0:2) 11Р 2В ЬОА 0,2 СИРА К 1Е БОССЕББ ЕЦО Время работы программы составляет 8С + 8 единиц, где С вЂ” количество проверяемых символов. Поскольку С < 5„время поиска никогда ие превышает 48 единиц времени.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
