Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[112]

сливаемых узлов. В упражнении 17.3-3 мы предложим вам доказать, что стоимость дерева равна сумме стоимостей всех слияний, необходимых для его построения. Стало быть, алгоритм Huffman на каждом шаге выбирает слияние, наименее увеличивающее стоимость.

Теперь установим свойство оптимальности для подзадач.

Пусть фиксирован алфавит С и два символа ж, у этого алфавита, а С - алфавит, который получится из С, если выкинуть ж и у и добавить новый символ z.

Рассмотрим кодовые деревья для С, в которых ж и у (точнее, соответствующие им листья) являются братьями. Каждому такому дереву соответствует кодовое дерево для С, которое получится, если выбросить вершины ж и у, а их общего родителя считать кодом символа z.

При этом соответствии каждому кодовому дереву для С соответствует ровно два кодовых дерева для С (в одном из них ж будет левым ребёнком, в другом - правым).

Пусть для каждого символа с из С фиксирована его частота /[с]. Определим частоты для символов из С, считая частотой символа z сумму /[ж] + f[y]; для остальных символов частоты остаются теми же, что и в С Тогда для кодовых деревьев (для обоих алфавитов) определены стоимости.

Лемма 17.3. Стоимости соответствующих друг другу деревьев Т и Т (при описанном соответствии) отличаются на величину

Доказательство. Легко видеть, что dj(c) = djt(c) для всех с £ С \{х,у}, а также что dj(x) = dj(y) = dx(z) + 1. Следовательно,

Эта лемма показывает, что выполнено свойство оптимальности для подзадач (оптимальное дерево Г соответствует оптимальному дереву Т для меньшей задачи).

Из двух доказанных лемм легко следует

Теорема 17.4. Алгоритм Huffman строит оптимальный префиксный код.

Доказательство. Лемма 17.2 показывает, что оптимальные кодовые деревья можно искать среди таких, у которых два наиболее редких символа (назовём из ж и у) являются братьями. Им соответствуют деревья для алфавита С, в котором символы ж и у слиты в один символ z. Считая частоту символа z равной сумме частот ж и

/И + /Ы-

f[x]dT(x) + f[y]dT(y)

f[z]dT,(z) + (f[x] + f[y])


у, можно применить лемму 17.3 и увидеть, что нам остаётся найти оптимальное кодовое дерево для алфавита С и затем добавить к вершине z двух детей, помеченных символами хну. Это и делает алгоритм Huffman.□

Упражнения

17.3-1 Докажите, что в бинарном дереве, соответствующем оптимальному префиксному коду, всякая вершина либо является листом, либо имеет двух детей.

17.3-2 Найдите код Хаффмена для алфавита, в котором частоты символов совпадают с первыми восемью числами Фибоначчи:

а : 1 Ъ : 1 с:2 d:3 е:5 f : 8 g : 13 h : 21.

Что будет, если в алфавите га символов, частоты которых совпадают с первыми га числами Фибоначчи?

17.3-3 Докажите, что стоимость двоичного дерева, соответствующего префиксному коду, можно вычислить следующим образом: для каждой вершины, не являющейся листом, найти сумму частот ее детей, и сложить все полученные числа.

17.3-4 Расположим символы алфавита в порядке убывания (невозрастания) частот. Докажите, что в оптимальном префиксном коде длины кодирующих эти символы последовательностей битов будут идти в неубывающем порядке.

17.3-5 Докажите, что оптимальный префиксный код для алфавита из га символов может быть представлен последовательностью из 2га - 1 + ra[log2 га] битов. (Указание: для задания структуры дерева достаточно 2га - 1 битов.)

17.3-6 Обобщите алгоритм Хаффмена на тернарные коды (каждый символ кодируется последовательностью из цифр 0, 1 и 2). Коды, порождаемые вашим алгоритмом, должны быть оптимальны.

17.3-7 Пусть алфавит содержит 28 = 256 символов, причём максимальная частота превосходит минимальную не более чем вдвое. Покажите, что для алфавита с такими частотами код Хаффмена не более эффективен, чем равномерный восьмибитовый код.

17.3-8 Профессор утверждает, что написанная им программа сжатия информации позволяет сжать любой файл длины 1000 (последовательность из тысячи 8-битовых байтов) хотя бы на один бит, после чего написанная им программа восстановления сможет


восстановить исходный файл. Почему он неправ? (Указание: сравните количество возможных файлов с количеством сжатых файлов).

★ 17.4 Теоретические основы жадных алгоритмов

В этом разделе мы вкратце расскажем о красивом разделе комбинаторики, связанном с жадными алгоритмами, - теории матро-идов. С помощью этой теории часто (хотя и не всегда: задачи из разделов 17.1 и 17.3 теорией матроидов не покрываются) удаётся установить, что данный жадный алгоритм даёт оптимум. Теория матроидов быстро развивается (см. ссылки в конце главы).

17.4.1. Матроиды

Матроидом (matroid) называется пара М = (S,X), удовлетворяющая следующим условиям.

1.S - конечное непустое множество.

2.X - непустое семейство подмножеств S; входящие в X подмножества называют независимыми (independent). При этом должно выполняться такое свойство: изВе!иАСВ следует А £ X (в частности, всегда 0 £ X). Семейство X, удовлетворяющее этому условию, называется наследственным (hereditary).

3.Если А £ X, В £ X и А < \В\, то существует такой элемент х £ В\А, что A U {ж} £ X. Это свойство семейства X называют свойством замены (exchange property).

Термин «матроид» принадлежит Хасслеру Уитни (Hassler Whitney). Он занимался матричными матроидами (matric matroids), у которых S - множество всех строк некоторой матрицы, и множество строк считается независимым, если эти строки линейно независимы в обычном смысле. (Легко показать, что действительно получается матроид, см. упр. 17.4-2.)

Другим примером является графовый матроид (graphic matroid) (Sg,Xg), строящийся по неориентированному графу G следующим образом: Sq совпадает со множеством рёбер графа, a Xq состоит из всех ацикличных (т.е. являющихся лесами) множеств рёбер. Графовые матроиды тесно связаны с задачей о минимальном покрывающем дереве, которую мы рассмотрим в главе 24.

Теорема 17.5. Если G = (V, Е) - неориентированный граф, то Mq = (Sg,Xg) является матроидом.

Доказательство. Так как подграф ацикличного графа ацикличен, множество Xq наследственно, и остаётся проверить свойство заме-



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]