AOP_Tom3 (1021738), страница 140
Текст из файла (страница 140)
Поиск по дереву (алгоритм 6.2.2Т) Цифровой поиск по дереву (алгоритм (У) Метод "Патриция" (алгоритм Р) 1 6 1 6 1 3 1 б 1 8 1 2 1 8 1 7 1 8 1 7 1 7 1 7 3 7 (Заметим, что дерево цифрового поиска будет сбалансировано чаше других.) В упр. 6.2. 2-5 приведена формула для вероятности в случае поиска по дереву; П(1/э(т)), где произведение берется по всем внутренним узлам х, а э(х) — число внутренних узлов в поддереве, корнем которого является х. Найдите аналогичные формулы для вероятности в случае (а) алгоритма П н (Ь) шггоритма Р.
ь 37. (М22) Рассмотритебинарноедерево, науровне1которогоимеетсяЬ~ внешних узлов, В тексте указывалось, что время неудачного поиска в деревьях цифрового поиска ие связано с длиной внешнего пути 2 (Ь| непосредственно, а пропорционально модифицпровавиай длине еиешнсге пуши 2 !Ь|2 '. Докажите или опровергните следующее утверждение: среди всех деревьев с Ге внешними узлами наименьшую модифицированную длину внешнего пути имеет то дерево, все внешние узлы которого расположены не более чем на двух смежных уровнях (см, упр, 5.3.1-20).
33. [М40] Разработайте алгоритм поиска дерева с и узлами, имеющего минимальное значение величины о (длина внутреннего пути)+Ь'. (модифицированная длина внешнего пути), где а и (1 — некоторые числа (см упр. 37). 39. [М43] Разработайте алгоритм поиска оптимальных деревьев цифрового поиска, аналогичных оптимальным бинарным деревьям поиска, которые рассматривалигь в рвздщ ле б 2.2. ь 40. [25] Пусть ае а~ аз... — это периодическая бинарная последовательность, в которой ая+ь = аь для всех Л > О. Покажите, что любая фиксированная последовательность такого типа может быть представлена в 0(Х) ячейках памяти так, что следующая операция может быть выполнена за О(Х) шагов. Определите для данной цепочки битов Ье 6~ .. Ь„ сколько раз она встречается в периоде (т.
е. найдите, сколько существует таких значений р, при которых 0 < р < Х и Ьь = арчь для 0 < Л < и). Предполагается, что каждая ячейка памяти достаточно велика, чтобы содержать любое целое число от О до Ж. [Указание. См. упр. 14,] 41. [НМВВ] (Приложение к теории групп.) Пусть С вЂ” свободная группа над символами (ам, .., а„), т. е. множество всех строк и = Ьы .. Ь„где каждый Ь. представляет собой либо аз либо а и не имеется смежных пар азо или а ал Обратным к о элементом является 6„... Ь~ . Перемножим две такие строки путом их конкатенации и сокращения смежных обратных пар. Пусть Н вЂ” подгруппа группы С, порожденная строками (Д,...
„3„), т. е множество всех элементов С, которые могут быть записаны в виде произведений В и обратных им элементов. Согласно широкоизвестной теореме Якоба Нильсена (дайоЬ ЬйеЕео) ]ем. Магвбай Най., ТЛе Тбеогу оу Сгоирэ (Нем Уогрс Масппйап, 1959), СЛ. 7] всегда можно найти образующие Вп..., В для Н, гл < р, обладающие тем свойством, что средний символ В, (или, по крайней мере, один из центральных символов В„егли его длина четна) никогда не сокращается в выражениях В,В; или В;В;, е = *1, за исключением случая у = ! и е = — 1.
Из этого свойства следует, что существует простой алгоритм проверки принадлежности некоторого элемента С подгруппе Н: запишем 2т ключей В„...,В „ В,,..., В в дерево, ориентированное на поиск по символам, с помощью 2п букв а„..., аьз а,,..., а„. Пусть п = Ьы .. 6„— данный элемент из С; если г = О, то и, разумеется, принадлежит Н. В противном случае ищем сг, определяя самый длинный префикс Ь~...
Ьь, который соответствует ключу. Если имеется несколько ключей, начинающихся с Ьм .. Ьы то о не принадлежит Н. Иначе обозначим этот единственный ключ через Ьм .. Ьь см .. с~ = В; и заменим о ключом В,, 'и = с~ ... с, Ьь+,... 6,. Если новое значение и длиннее старого (т. е. если ! > !с). о не принадлежит Н; в противном случае повторяем процесс с новым значением сс Из свойства Нильсена вытекает конечность этого алгоритма. Если а сводится к пустой строке, можно восстановить исходное предсщвление и в ниде произведений В.
Например, пусть [Вм Вэ. Вз) = (Ьбб, Ь а Ь, ба 6) и о = 6Ьобоаб. Лес В, В; Вз Вэ Вз вместе с описанным алгоритмом позволяет вывести, что о = В~ Вз В ~Вз Вз . Реализуйте этот алгоритм, используя в качестве входнгях данных вашей программы В,, 42. [83] (Сжашие спереди и сзади.) Если множество бинарных ключей используется в качестве индекса для разделения болыпого файла, можно не хранить полные ключи. Например, 16 ключей, показанных иа рис. 34, могут быть урезаны справа так, чтобы оставалось достаточное количество цифр для их однозначной идентификации: ОООО, 0001, 00100, ()0101, 010, ..., 1110001.
Такие урезанные ключи могут использоваться для разделения файла на 17 частей, и, например, в пятой части могут содержаться все ключи, начинающиеся с 0011 или 010, а в последней части — ключи, начинающиеся с 111001, 11101 нли 1111. Урезанные ключи можно представить в более компактной форме, если опустить все лидирующие цифры, совпадающие с цифрами предыдущего ключа: ОООО, ооо1, оо100, оооо1, о10, ..., оооооо1.
Бит, следующий за символам "о', всегда равен 1, позтому он также может быть опущен. В большом файле будет содержаться много символов "о", и мы должны хранить только их количество и значения последующих битов. Покажите, что общее количество битов в сжатом файле с исключенными символами "о" и последующим одним битом, всегда равно количеству узлов в бинарном луче с этими ключами. (Следовательно, среднее общее количество таких битов во всем индексе составляет около Ж/1п2, 1.44 бит на ключ. Этот способ сжатия был показан автору Э. Геллером (А.
Не11ег) и Р. Л. Джонсеном (В. Ь. Лойпзеп). Возможно и дальнейшее сжатие, поскольку нам необходимо только представление структуры луча; см. теорему 2.3.1А.) 43. (НМ22) Проанализируйте высоту случайного М-арного луча, имеющего М ключей и параметр обрезки в, как в упр. 20 (когда з = 1, зта величина представляет собой длину самого длинного общего префикса случайнь»х слов длиной Х в М-арнол» алфавите). ь 44. (30) (Дж. Л. Бентли (1. 1. Веп»!еу) н Р. Седгевик (В..
Бебйеъий).) Исследуйте тернарное представление лучей, при котором левая и правая ссылки соответствуют горизонтальным ветвям (2), в то время как средняя ссылка соответствует ветви, идущей вниз. ь 45. (МЯ51 »Если семь ключей, которые показаны на рис. 33, вставлены в ш»учайном порядке с помощью алгоритма, описанного в упр. 15, то чему равна вероятность получения показанного дерева? 6.5. ВЫБОРКА ПО ВТОРИЧНЫМ КЛЮЧАМ Мы злкончили изучение поиска по пераичн и хаю~ам, т. е. по ключам, которые однозначно определяют запись в файле. Однако иногда необходимо выполнить поиск, основанный на значениях других полей записей.
помимо первичного ключа. Эти другие поля часто именуются вторичными ключами или атрибутами записи. Например, имея файл регистрации с информацией о студентах университета, можно найти всех второкурсников из Огайо, не специализирующихся по математике или статистике, или нсех незамужних франкоговорящих аспиранток.
В общем случае полагается, что в каждой записи содержится несколько атрибутов, и необходимо найти все записи с некоторыми значениями этих атрибутов. Определение требуемых записей называется запросам (яаегу). Обычно запросы подразделякэтся на следующие три типа. а) Простой запрос., определяющий конкретное значение некоторого атрибута, например "СПЕЦИАЛИЗАЦИЯ = МАТЕМАТИКА" или "МЕСТОЖИТЕЛЬСТВО. ШТАТ = ОГАЙО". Ь) Запрос диапазона, запрашивающий определенный диапазон значений некоторого атрибута, например "ЦЕНА с $18.
ОО" нли "21 ( ВОЗРАСТ < 23". с) Логический запрос, состоящий из запросов предыдущих типов, скомбинированных при помощи логических операций АЛО, ОЯ, НОТ, например "(КУРС = ВТОРОКУРСНИК) АНО (МЕСТОЖИТЕЛЬСТВО. ШТАТ = ОГАЙО) АЛО НОТ ((СПЕЦИАЛИЗАЦИЯ = ИАТЕМАТИКА) ОЯ (СПЕЦИАЛИЗАЦИЯ = СТАТИСТИКА)) '. Проблема разработки эффективных технологий поиска достаточно сложна уже для этих трех простых типов запросов, а потому более сложные типы запросов обычно не рассматриваются. Например, железнодорожная компания может иметь файл с информацией о текущем состоянии всех товарных вагонов. Запрос наподобие "Найти все пустые вагоны-рефрижераторы в радиусе 500 миль от Сиэтла" при этом в явном виде невозможен, за исключением случая, когда "расстояние от Сиэтла' является атрибутом, хранящимся в каждой записи, а не сложной функцией вычисления этой величины по значениям других атрибутов. Использование же логических кванторов в дополнение к АИО, Ой, НОТ приведет к дальнейшему усложнению запросов, ограниченных исключительно воображением запрашивающего.
Имея файл со статистикой по бейсболу, например, можно запросить информацию о самой длинной серии удачных ударов в ночных играх. Такие запросы несмотря на их сложность могут выполняться в течение одного прохода по соответствующим образом упорядоченному файлу. Однако могут быть и существенно более сложные запросы, например "Найти все пары записей, имеющие одинаковые значения в пяти и более атрибутах (без укязания атрибутов, которые должны совпадать)". Такие запросы могут рассматриваться как общие задачи программирования, выходящие за рамки нашего обсуждения, хотя зачастую они могут быть разбиты на под3адачи, подобные рассматриваемым здесь.
Прежде чем приступить к изучению различных технологий получения информации по вторичным ключам, стбиг рассмотреть экономический аспект вопроса. Хотя огромное количество приложений помещается в жесткие рамки трех типов запросов, описанных выше, далеко не для всех из них подходят технологии, которые мы будем изучать; в некоторых из них лучше было бы использовать ручную, а не машинную рабату! Люди взобрались на Эверест просто потому, что он существует. И многое альпинистское снаряжение было разработано именно по этой причине. Так и в информационных технологиях; увидев перед собой Эверест даннгпх, люди тут же начинают разрабатывать снаряжение для его покорения, позволяющее в оперативном режиме ответить на все вопросы, которые только могут присниться в кошмарном сне.
Зачастую они просто не задумываются о вопросах стоимости. Такие вычисления возможны, но они пе подходят для любого приложения. Например, рассмотрим следующий простой подход к выборке по вторичным ключам; после сбора пакета из нескольких запросов (ба1сгггпд) выполним последовательный поиск по всему файлу, получая все нужные записи. (Сбор пакета означает, что мы накапливаем некоторое количество запросов перед их выполнением.) Такой метод вполне удовлетворителен при не слишком болыпих файлах и отсутствии требования немедленно обработать поступающие запросы. Этот подход может использоваться с файлами на лентах и требует работы компьютера над запросом через некоторые интервалы времени, что делает его вполне экономичным в плане стоимости оборудования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
