AOP_Tom3 (1021738), страница 121
Текст из файла (страница 121)
15). Еще более удивительны эмпирические данные, накопленные Дж. Д, Эппингером (Я. Е. Ерр!пйег) (САСМ 26 (1983), 663-669, 27 (1984), 235), который обнаружил, что длина пути немного уменьшается при небольшом количестве удалений и вставок, однако затем начинает увеличиваться до тех пор, пока не достигнет стабильного состояния после выполнения примерно пэ операций удаления/вставки. Это стабильное состояние хуже поведения случайного дерева при Х, болыпем примерно 150. Дальнейшее исследование Кульберсона (Сп1Ьегэоп) и Мунро (Мппго) (Сошр. ).
32 (1989), 68 — 75; А1аопйписа 5 (1990), 295 — 311) привело к правдоподобному предположению о том, что среднее время поиска в стабильном состоянии асимптотически равно ъ/2Х/юг. Однако Эппингер предложил простую модификацию, при которой алгоритм Р и его зеркальное отражение чередуются в одном алгоритме; он обнаружил, что это приводит к отличному стабильному состоянию, в котором длина пути снижается да примерно 88% от его обычного значения для случайных деревьев. Теоретического пояснения этого факта пока не найдено. Как упоминалось ранее, алгоритм Р не проверяет случай ШяК(Т) = Л, хотя это один из простейших случаев удаления.
Мы можем добавить новый шаг Р1- 1 мелсэу шагами Р1 и Р2. 01э. (Пуста ли ссылка ЬЫяК?) Если Ш(Е(Т) = Л, установить Ц < — йЬ?ИК(Т) и перейти к шагу?)4. В упр. 14 показано, что алгоритм Р с этим дополнительным шагом всегда оставляет дерево с той же, если не меньшей, длиной пути, что и алгоритм Р; иногда же результат оказывается даже лучше ожидаемого.
При комбинировании рассмотренного метода со стратегией симметричного удаления Эппингера длина пути при повторяющихся случайных удалениях/вставках уменьшается до примерно 86% от значения, получаемого при использовании вставок без удалений. 'Частота обращений. Пока что мы предполагали, что каждый ключ может стать объектом поиска с одинаковой вероятностью. Однако в более общем случае следует рассмотреть вероятности рь поиска я-го вставленного элемента (р1 + + ря = 1). Модифицированное выражение (2) (в предположении о случайном порядке дерево остается случайным и выполняется соотношение (5)) показывает, что среднее коли- Рис.
12. 31 наиболее употребительное англяйское слово, вставленное в порядке уменыпе- ния частоты. чество сравнений в случае успешного поиска составляет 1+ ~ рь(2Нг — 2) = 2~ рьНь — 1. Например, если вероятности соответствуют закону Зипфа (6.1 — (8)), среднее количество сравнений сводится к Нн — 1+ Н~ ~!Нн (12) в предположении, что ключи будут вставляться в гюрядке уменьшения нх важности (см. упр. 18). Эта величина примерно в два раза меньше величины, предсказываемой в результате анализа случая с равными частотами, н меньше, чем в случае бинарного поиска. На рис. 12 показано дерево, полученное в результате вставки 31 наиболее часто употребляюшегосн английского слова в порядке убывания частоты появления в текстах.
Относительные частоты, приведенные для каждого слова, взяты из Н. Г. Са1пеэ, СгурСапа!уэ1э (Хек Ъогк: Рояег, 1956), 226. Среднее количество сравнений при успешном поиске в этом дереве равно 4.042; соответствуклцее значение для бинарного поиска с использованием алгоритма 6,2.1В или 6.2.1С требует 4,393 сравнений. Оптимальные бинарные деревья поиска. Рассмотренный материал заставляет задуматься а том, какое дерево является наилучшим для поиска в таблице ключей с заданными частотами. Например, для случая с 31 наиболее употребительным словом оптимальное дерево показано на рис. 13; оно требует в среднем всего лишь 3 437 сравнений при успешном гюнске. Рис.
13. Оптимальное дерево поиска для 31 наиболее употребительного английского слова. Приступим и задаче поиска оптимального дерева. Например, при Х = 3 в предположении, что ключи К| С К2 < Кз имеют вероятности р, д, г соответственно, возможны пять деревьев: 1 11 (13) р+Зд+Зг рч 2д+Зг Сан: Зрд-2д-И 2р-~-Зд-~-г 2рд-д-~2г На рис. 14 показаны диапазоны значений р, д, г, для которых каждое из деревьев является оптимальным; сбалансированное дерево является наилучшим примерно в 45% случаев при случайном выборе р, д, г (см. упр.
21). К сожалению, при больших Ж имеется бинарных деревьев, так что перебрать их все и найти наилучшие — совершенно неразрешимая задача, Позтому стоит познакомиться с ними поближе, чтобы, лучше узнав свойства бинарных деревьев, найти среди них оптимальные. До сих пар нас интересовал успешный поиск, однако на практике неудачный поиск не менее важен (более того, в некоторых специфичных задачах именно он является определяющим; случаями успешного поиска в таких задачах можно попросту пренебречь. — Прим. нерее.). Например, представленные на рис. 13 слова соответствуют примерно 36% слов обычного английского текста; остальные 64%, естественно, повлияют на структуру оптимального дерева поиска.
Сформулируем задачу следующим образом. Даны 2п + 1 вероятностей р1,рд, ...,п„и дв,ды...,д„, где р1 — вероятность того, что аргументом поиска является К,; д; — вероятность того, что аргумент поиска лежит между К; н Кг ь1. П,а.а) (о, о, ц Рис. 14. На этой диаграмме показано, какое из пяти деревьев (13) является наилучшим в случае относительных частот (р д т) ключей (Кп Яг, Кг). '1ет факт, что р -т д+ г = 1, делает диаграмму двумерной несмотря на величие трех координат.
(Пусть йе представляет собой вероятность того, что аргумент поиска меньше, чем Км а й„. — вероятность того, что аргумент поиска больше, чем К„.) Таким образом, рг + рг + . + р + В + а + . + д„= 1 и мы хотим найти бинарное дерево, минимизирующее ожидаемое количество сравнений при поиске, а именно р.
(уровень(Я) + 1) + ~~ йь уровень((Я), (14) 1=1 ь=е где ОЗ вЂ” у'-й внутренний узел при симметричном обходе, а (К вЂ” ()с+1)-й внешний узел; корень дерева находится на нулевом уровне. Так, ожидаемое количество сравнений для бинарного дерева (15) равно 2ве+ 2р~ + Зц~ +Зрг+ Зог+рг+ от Назовем это значение ценой дерева.
а дерево с минимальной ценой — опглимальным. При таком определении требование, чтобы сумма всех р и д была равна 1, излишне — мы можем искать дерево с минимальной ценой с любой данной последовательностью весов (ры..., р„; до,..., д„). В разделе 2.5.4.5 мы изучали процедуру Хаффмана (Ни%пап) для построения деревьев с минимальной взвешенной длиной пути, однако этот метод требовал, чтобы все р были нулевыми, н, кроме того, в построенном этим методом дереве внешние узлы с весами (де,..., д„) обычно не располагались в правильном порядке с точки зрения симметричного обхода. Следовательно, нам надо поискать другие подходы к решению этой задачи. Нас спасет то, что все паддеревья оптимального дерева оптимальны.
Например, если (15) представляет собой оптимальное дерево для весов (рмрз рз; йо, Чс чз, с1з) та ега левое поддерево должно быть оптимально для (рырг', Чо, са,йз); любое Улуч- шение поддерева должно приводить к улучшению дерева в целом. Данный принцип предлагает вычислительную процедуру, которая систематично ищет все большие и ббльшие оптимальные поддеревья. Мы использовали эту же идею в разделе 5.4.9 для построения схем оптимального слияния; общий подход, известный как вдинамическае программирование", будет рассмотрен в разделе 7.7".
Пусть с(г,з) — цена аптимальнога поддерева с весами (рсэы .,РП йс . с14) и пусть ш(г',у) = рс, + . + р + ос+ + а — сумма этих весов (ачевидно, чта с(е,у) и ю(е,у) определены для 0 < 1 < у < и). Поскольку минимально возможная цена дерева с корнем ® равна св(г', 1) + с(з, к — 1) + с(/с, у), получим с(4,з) = О, с(с,,с') = го(г',,)) + ппп (с(е, lс — 1) + с((с,з)) при г < 1 (16) 1<451 Через В(г,у') при 1 < у' обозначим множество всех 1, для которых достигается минимум в (16); это множество определяет корни оптимальных поддеревьев.
С помощью уравнений (16) можно вычислить с(е, з) для у' — 1 = 1, 2,..., и; имеется примерно -и таких значений, а операция минимизапии выполняется примерно 1 з з для;и значений я. Зто означает, что мы в состоянии определить оптимальное дерево за О(из) единиц времени с использованием О(из) ячеек памяти. При оценке времени работы свойство монотонности позволяет уменьшить степень при и. Пусть т(е, у) означает элемент множества Я(г,,з'); нет необходимости в вычислении всего множества В(з, у) — - достаточно одного его представителя.
Найдя т(с, з — 1) и т(е'+1, 7) и используя результат упр. 27, мы всегда можем полагать, чта (17) т(е, у' — 1) < т(г, 4') < т(е+1, у') при неотрицательных весах. Зто ограничивает поиск минимума всего лишь т(з+1, у) — т(г,у — 1) + 1 проверяемыми в (16) значениями к вместо у — гй Общий объем работы при у' — е = с1 оценивается как (т(сг 61, с') — т(г, у — 1) + 1) = т(и — с1+1, и) — т(0, д — 1) + и — д + 1 < 2и, 4<~<в с=э — 4 так что общее время работы уменьшается до О(из). Детально эта процедура рассматривается в описании алгоритма К. Алгоритм К (Поиск оиизимальнмх бинарных дерееьео ириска).
Даны 2и+1 неотрицательных веса (ры...,рв; оо,...,д„), Алгоритм строит бинарные деревья ф,~), имеющие минилсальпую цену (в определенном ранее смысле) для весов (р,.ем..., р~", оа..., с1,). ВычислЯютсЯ тРи массива, а именно ф,Я, 0<с<у <и, цена1(е,у); ф,у], 0 < е < 7 < и, корень 4(е, Я; го[с,Я, 0 < г < 4' < и, общий вес с(г,у). * Имеетсв в аиду раздев вз планируемого автором тома 4.
— Приве перев. Результаты работы алгоритма определяются массивом г: при 1 = у У[у,у) пуст; в противном случае левое поддерево — у(у, г[у, у] — 1), а правое поддерево — у(г[Ц у], у'). К1. [Инициализация.] Для О < 1 < и установить с[у, 1] е- О, ю[у,у] е- 4у и уе[у, у] ею[у', у' — Ц+ру+а при у = с+1,..., и.
Затем для 1 < у < и уюптовить с[у — 1, Я ею[у — 1, Я и г[у' — 1, Я е- у. (Эти действия определякут все оптимальные деревья из одного узла.) К2. [Пикл по ~Г.] Выполнить шаг КЗ для сУ = 2, 3,..., и, затем остановить работу алгоритма. КЗ. [Цикл по Я] (К втоцу моменту уже определены оптимальные деревья с менее чем И узлами. На данном шаге определяются все оптимальные деревья с И узлами). Выполнить шаг К4 для у = сУ, 4+ 1, ..., и. к4. [поиск с[у, Я, г~г', у],] Установить у е- у — уУ, затем— с[у,у] ш[у,Я+пни,]ьу у)<ь<,у,~у у1(с[г, Ус — Ц+ с[/с,Я) и присвоить г[у,у] значение Ус, для которого достигается минимум.
(В упр. 22 доказывается, что г[у, у — Ц < с[1+1, Я.) $ 6 ~ бу'„:~у Рис. 15. Оптимальное бинарное дерево поиска для указателя КЧУ1С. В качестве примера алгоритма К рассмотрим рис. 15, основанный на приложении индексирования 'кеу-иогб-'ш-сопФехг" (ключевое слово в контексте -- К%1С). Заглавия всех статей в первых десяти томах УопгпаУ оГ сйе АСМ были рассортированы таким образом, чтобы каждому слову каждого заголовка соответствовала одна строка. Впрочем, некоторые слова наподобие ТНЕ и ЕОБАТ10УУ были признаны неинформативными и не вошли в указатель. Эти специальные слова и частота их появления обозначены внутренними узлами на рис. 15.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
