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


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




[111]

Построение кода Хаффмена

Хаффмен построил жадный алгоритм, который строит оптимальный префиксный код. Этот код называется кодом Хаффмена (Huffman code). Алгоритм строит дерево Г, соответствующее оптимальному коду, снизу вверх, начиная с множества из \С\ листьев и делая \С\ - 1 «слияний». Мы предполагаем, что для каждого символа с £ С задана его частота f[c]. Для нахождения двух объектов, подлежащих слиянию, используется очередь с приоритетами Q, использующая частоты / в качестве рангов - сливаются два объекта с наименьшими частотами. В результате слияния получается новый объект (внутренняя вершина), частота которого считается равной сумме частот двух сливаемых объектов.

Huffman (С)

9 return Extract-Min(Q)

Работа этого алгоритма для нашего примера показана на рис. 17.5. Поскольку имеется всего 6 букв, первоначально очередь имеет размер га = 6, и для построения дерева нужно сделать 5 слияний. Префиксный код соответствует дереву, полученному в результате всех этих слияний.

В строке 2 алгоритма в очередь Q помещаются символы из алфавита С (с соответствующими частотами). В цикле (строки 3-8) повторяется га - 1 раз следующая операция: из очереди изымаются две вершины ж и у с наименьшими частотами /[ж] и f[y], которые заменяются на одну вершину z с частотой /[ж] + f[y] и детьми ж и у (кого из них считать левым ребёнком, а кого правым - неважно: код получится другой, но его стоимость будет та же). В конце в очереди остаётся один узел - корень построенного двоичного дерева. Ссылка на него возвращается в строке 9.

Оценим время работы алгоритма, считая, что очередь Q реализована в виде двоичной кучи (см. главу 7). Инициализацию Q в строке 2 можно провести за О (га) операций с помощью процедуры Build-Heap из раздела 7.3. Цикл в строках 3-8 исполняется ровно га - 1 раз; поскольку каждая операция с кучей требует времени О (log га), общее время будет О (га log га). Стало быть, время работы алгоритма Huffman для алфавита из га символов будет О (га log га).

1 2 3

4 5 6 7 8

п\С\

for г

1 to га - 1


Рис. 17.5 Применение алгоритма Хаффмена к таблице частот рис. 17.3. Показаны последовательные состояния очереди (в порядке возрастания частот). На каждом шаге сливаются два поддерева с наименьшими частотами. Листья - прямоугольники, в которых символ и его частота разделены двоеточием. Внутренние вершины изображены кружками, в которых указаны суммы частот их детей. Ребро, идущее к левому ребёнку, помечено нулем, к правому - единицей. В результирующем дереве код любого символа написан на пути, ведущем из корня к этому символу, (а) Начальная стадия: п = 6 листьев, по одному на символ, (б)-(д) Промежуточные стадии, (е) Готовое дерево.

Правильность алгоритма Хаффмена

Чтобы доказать, что жадный алгоритм Huffman действительно даёт оптимум, мы покажем, что для задачи об оптимальном префиксном коде выполнены принцип жадного выбора и свойство оптимальности для подзадач. Начнём с принципа жадного выбора.

Лемма 17.2. Пусть в алфавите С каждый символ с £ С имеет частоту /[с]. Пусть х,у G С - два символа с наименьшими частотами. Тогда для С существует оптимальный префиксный код, в котором последовательности битов, кодирующие х и у, имеют одинаковую длину и различаются только в последнем бите.

Доказательство. Утверждение леммы будет выполнено, если листья, соответствующие хну, будут братьями. Рассмотрим дерево Г, соответствующее произвольному оптимальному префиксно-


Рис. 17.6 Доказательство леммы 17.2. Здесь Ъ и с - наиболее удалённые от корня листья-братья, а £ и у - листья с наименьшими частотами. Обмен х и Ъ превращает дерево Т в Т", а обмен у и с превращает Т в Г". При каждой из перестановок стоимость дерева не возрастает.

му коду, и покажем, что его можно модифицировать, не нарушая оптимальности, так, чтобы вышеуказанное условие выполнялось.

В самом деле, рассмотрим пару соседних (имеющих общего родителя) листьев в дереве Г, находящуюся на максимальном расстоянии от корня. (Такие существуют: в оптимальном дереве все внутренние вершины имеют степень 2, и потому лист наибольшей глубины имеет брата.) Символы, стоящие в этих листьях (назовём их бис) - не обязательно ж и у, но заведомо имеют не меньшие частоты (поскольку ж и у были двумя наиболее редкими символами). Не ограничивая общности, можно считать, что /[ж] f[b] и f[y] /[с]. Теперь поменяем местами в дереве Г символы Ь и ж (полученное дерево назовём Г), а затем символы сиу (полученное дерево назовём Г"). После таких обменов ж и у (см. пример на рис. 17.6) станут братьями, находящимися на максимальной глубине. Осталось убедиться, что при обменах стоимость дерева не возрастает и, следовательно, дерево Т" также является оптимальным. Другими словами, мы должны проверить, что В(Т) В(Т) В(Т"), где В - функция стоимости. В самом деле, стоимость определяется как сумма по всем листьям произведений частоты на глубину (17.3). При переходе от Г к Г в этой сумме меняются только два слагаемых: f[b]dx(b) + f[x\dj(x) заменяется на f[b]d,Ti(b) + f[x]dx(x), т.е. на f[b]dT(x) + f[x]dx(b). Таким образом,

В(Т) - В(Т) = f[b]dT(b) + f[x]dT(x) - f[b]dT(x) - f[x]dT(b) = = (f[b]-f[x])(dT(b)-dT(x))0.

Обе скобки неотрицательны: вспомним, что /[ж] f[b] и что dr(b) б?х(ж), так как лист b был одним из наиболее удалённых от корня. Аналогичным образом В(Т) В(Т"), так что В(Т) В(Т"), и поэтому Т" также оптимально (а все наши неравенства

Доказанная лемма показывает, что построение оптимального дерева всегда можно начать со слияния двух символов с наименьшей частотой. Следующее наблюдение оправдывает название «жадный» для такого алгоритма. Назовём стоимостью слияния сумму частот



[стр.Начало] [стр.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]