Изменения

Пусть <tex>A=\{a_{1},a_{2}, \ldots ,a_{n}\}</tex> — алфавит из <tex>n</tex> различных символов, <tex>W=\{w_{1},w_{2}, \ldots ,w_{n}\}</tex> — соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов <tex>C=\{c_{1},c_{2}, \ldots ,c_{n}\}</tex>, где <tex>c_{i}</tex> является кодом для символа <tex>a_{i}</tex>, такой, что: :* <tex>c_{i}</tex> не является префиксом для <tex>c_{j}</tex>, при <tex>i \ne j</tex>, :* cумма <tex>\sum\limits_{i \in [1, n]} w_{i}\cdot |c_{i}|</tex> минимальна (<tex>|c_{i}|</tex> — длина кода <tex>c_{i}</tex>), называется '''Кодыкодом Хаффмана''' .}} == Алгоритм построения бинарного кода Хаффмана == Построение кода Хаффмана сводится к построению соответствующего [[ Двоичная_куча | бинарного дерева]] по следующему алгоритму: # Составим [[Список | список]] кодируемых символов, при этом будем рассматривать один символ как дерево, состоящее из одного элемента c весом, равным частоте появления символа в строке.# Из списка выберем два узла с наименьшим весом.# Сформируем новый узел с весом, равным сумме весов выбранных узлов, и присоединим к нему два выбранных узла в качестве детей.# Добавим к списку только что сформированный узел вместо двух объединенных узлов.# Если в списке больше одного узла, то повторим пункты со второго по пятый. === Время работы ===Если сортировать элементы после каждого суммирования или использовать [[Приоритетные_очереди | приоритетную очередь]], то алгоритм будет работать за время <tex>O(N \log N)</tex>.Такую асимптотику можно [[Алгоритм_Хаффмана_за_O(n) |улучшить до <tex>O(N)</tex>]], используя обычные массивы. === Пример === [[Файл:Huffman_abracadabra.jpg|400px|thumb|right|Дерево Хаффмана для слова <tex>abracadabra</tex>]] Закодируем слово <tex>abracadabra</tex>. Тогда алфавит будет <tex>A= \{a, b, r, c, d\} </tex>, а набор весов (частота появления символов алфавита в кодируемом слове) <tex>W=\{5, 2, 2, 1, 1\}</tex>: В дереве Хаффмана будет <tex>5</tex> узлов: {| class="wikitable"! Узел || a || b || r || с || d|-| Вес || 5 || 2 || 2 || 1 || 1|} По алгоритму возьмем два символа с наименьшей частотой {{---}} это <tex>c</tex> и <tex>d</tex>. Сформируем из них новый узел <tex>cd</tex> весом <tex>2</tex> и добавим его к списку узлов: {| class="wikitable"! Узел || a || b || r || cd |-| Вес || 5 || 2 || 2 || 2|} Затем опять объединим в один узел два минимальных по весу узла {{---}} <tex>r</tex> и <tex>cd</tex>: {| class="wikitable"! Узел || a || rcd || b |-| Вес || 5 || 4 || 2 |} Еще раз повторим эту же операцию, но для узлов <tex>rcd</tex> и <tex>b</tex>: {| class="wikitable"! Узел || brcd || a|-| Вес || 6 || 5 |} На последнем шаге объединим два узла {{---}} <tex>brcd</tex> и <tex>a</tex>: {| class="wikitable"! Узел || abrcd|-| Вес || 11|} Остался один узел, значит, мы пришли к корню дерева Хаффмана (смотри рисунок). Теперь для каждого символа выберем кодовое слово (бинарная последовательность, обозначающая путь по дереву к этому символу от корня): {| class="wikitable"! Символ || a || b || r || с || d|-| Код || 0 || 11 || 101 || 1000 || 1001|} Таким образом, закодированное слово <tex>abracadabra</tex> будет выглядеть как <tex>01110101000010010111010</tex>. Длина закодированного слова {{---}} <tex>23</tex> бита. Стоит заметить, что если бы мы использовали алгоритм кодирования с одинаковой длиной всех кодовых слов, то закодированное слово заняло бы <tex>33</tex> бита, что существенно больше. == Корректность алгоритма Хаффмана == Чтобы доказать корректность алгоритма Хаффмана, покажем, что в задаче о построении оптимального префиксного кода проявляются свойства жадного выбора и оптимальной подструктуры. В сформулированной ниже лемме показано соблюдение свойства жадного выбора. {{Лемма|id=lemma1|about=1|statement=Пусть <tex>C</tex> — алфавит, каждый символ <tex>c \in C</tex> которого встречается с частотой <tex>f[c]</tex>. Пусть <tex>x</tex> и <tex>y</tex> — два символа алфавита <tex>C</tex> с самыми низкими частотами. Тогда для алфавита <tex>C</tex> существует оптимальный префиксный код, кодовые слова символов <tex>x</tex> и <tex>y</tex> в котором имеют одинаковую максимальную длину и отличаются лишь последним битом. |proof=Возьмем дерево <tex>T</tex>, представляющее произвольный оптимальный префиксный код для алфавита <tex>C</tex>. Преобразуем его в дерево, представляющее другой оптимальный префиксный код, в котором символы <tex>x</tex> и <tex>y</tex> — листья с общим родительским узлом, находящиеся на максимальной глубине. Пусть символы <tex>a</tex> и <tex>b</tex> имеют общий родительский узел и находятся на максимальной глубине дерева <tex>T</tex>. Предположим, что <tex>f[a] \leqslant f[b]</tex> и <tex>f[x] \leqslant f[y]</tex>. Так как <tex>f[x]</tex> и <tex>f[y]</tex> — две наименьшие частоты, а <tex>f[a]</tex> и <tex>f[b]</tex> — две произвольные частоты, то выполняются отношения <tex>f[x] \leqslant f[a]</tex> и <tex>f[y] \leqslant f[b]</tex>. Пусть дерево <tex>T'</tex> — дерево, полученное из <tex>T</tex> путем перестановки листьев <tex>a</tex> и <tex>x</tex>, а дерево <tex>T''</tex> — дерево полученное из <tex>T'</tex> перестановкой листьев <tex>b</tex> и <tex>y</tex>. Разность стоимостей деревьев <tex>T</tex> и <tex>T'</tex> равна: <tex>B(T) - B(T'Алгоритм Хаффмана) = \sum\limits_{c \in C} f(c)d_T(c) - \sum\limits_{c \in C} f(c)d_{T'}(c) = (f[a] - f[x])(d_T(a) - d_T(x)),</tex> что больше либо равно <tex>0</tex>, так как величины <tex>f[a] - f[x]</tex> и <tex>d_T(a) - d_T(x)</tex> неотрицательны. Величина <tex>f[a] - f[x]</tex> неотрицательна, потому что <tex>x</tex> — лист с минимальной частотой, а величина <tex>d_T(a) - d_T(x)</tex> является неотрицательной, так как лист <tex>a</tex> находится на максимальной глубине в дереве <tex>T</tex>. Точно так же перестановка листьев <tex>y</tex> и <tex>b</tex> не будет приводить к увеличению стоимости. Таким образом, разность <tex>B(T') - B(T'' )</tex> тоже будет неотрицательной. Таким образом, выполняется неравенство <tex>B(T'') \leqslant B(T)</tex>. С другой стороны, <tex>T</tex> — оптимальное дерево, поэтому должно выполняться неравенство <tex>B(T) \leqslant B(T'Huffman codes')</tex>. Отсюда следует, что <tex>B(T) = B(T'') </tex>. Значит, <tex>T''</tex> — широко распространенный и очень эф- фективный метод сжатия данныхдерево, которыйпредставляющее оптимальный префиксный код, в зависимости от характеристик этих данныхкотором символы <tex>x</tex> и <tex>y</tex> имеют одинаковую максимальную длину, обычно позволяет сэкономить от 20% до 90% объемачто и доказывает лемму.

{{Лемма|id=lemma2|about= Построение кода Хаффмана 2|statement== Хаффман изобрел жадный алгоритм, позволяющий составить оптимальный префиксный код, который получил название код Хаффмана. Доказательство корректности этого алгоритма основывается на свойстве жадного выбора и оптимальной подструктуре. Вместо того чтобы демонстрировать, что эти свойства выполняются, а затем разрабатывать псевдокод, сначала мы представим псевдокод. Это поможет прояснить, как алгоритм осуществляет жадный выбор. В приведенном ниже псевдокоде предполагается, что Пусть дан алфавит <tex>C</tex> — множество, состоящее из <tex>n</tex> символов, и что каждый из символов в котором для каждого символа <tex>c\in C</tex> — объект с определенной частотой определены частоты <tex>f([c)]</tex>. В алгоритме строится дерево Пусть <tex>Tx</tex>, соответствующее оптимальному коду, причем построение идет в восходящем направлении. Процесс построения начинается с множества, состоящего из и <tex>|C|y</tex> листьев, после чего последовательно выполняется — два символа из алфавита <tex>|C|-1</tex> операций "слияния", в результате которых образуется конечное деревос минимальными частотами. Для идентификации двух наименее часто встречающихся объектов, подлежащих слиянию, используется очередь с приоритетами Пусть <tex>QC'</tex>— алфавит, ключами в которой являются частоты полученный из алфавита <tex>fC</tex>. В результате слияния двух объектов образуется новый объект, частота появления которого является суммой частот объединенных объектов:<br><br>'''Huffman(путем удаления символов <tex>Cx</tex>)''' <br># и <tex>n \gets |C|y</tex> <br># и добавления нового символа <tex>Q \gets Cz</tex> , так что <brtex># C'''for''' <tex>i = C \backslash \{ x, y \} \gets 1cup {z}</tex> '''to''' . По определению частоты <tex>n - 1f</tex> в алфавите <brtex>:# C'''do''' Выделить память для узла <tex>z</tex> <br># left[z] «- х <- Extract_Min(Q)<br> # right[z] <- у <- ExtractJMin(Q) <br># Insert(Q, z) <br># return Extract_Min(Q) > Возврат корня дерева <br>Для рассмотренного ранее примера алгоритм Хаффмана выводит результат, при- веденный на рис. 16.4. На каждом этапе показано содержимое очереди, элементы которой рассортированы в порядке возрастания их частот. На каждом шаге рабо- ты алгоритма объединяются два объекта (дерева) совпадают с самыми низкими частотами. Листья изображены в виде прямоугольников, в каждом из которых указана буква и соответствующая ей частота. Внутренние узлы представлены кругами* содер- жащими сумму частот дочерних узлов. Ребро, соединяющее внутренний узел с левым дочерним узлом, имеет метку 0, а ребро, соединяющее его с правым до- черним узлом, — метку 1. Слово кода для буквы образуется последовательностью меток на ребрах, соединяющих корень с листом, представляющим эту букву. По- Глава 16. Жадные алгоритмы 463 a) if-л] [^) I \у:\2\ алфавите <tex> П| |d IM |.,.4S| 6) Ki2) ЬИ в) ® ШЕ ® ШШ оC</ \i о/ 1Ж11Ж1 о/ \tex> t 5 р ч л) ЕВЕ (inn) о ч \ I f7i2i |b 13 f) i Рис. 16.4. Этапы работы алгоритма Хаффмана для частот, заданных в табл. 16.1 сколысу данное множество содержит шесть букв, размер исходной очереди равен 6 (часть а рисунка), а для построения дерева требуется пять слияний. Промежуточ- ные этапы изображены в частях б-д. Конечное дерево (рис. 16.4е) представляет оптимальный префиксный код. Как уже говорилось, слово кода для буквы — это последовательность меток на пути от корня к листу с этой буквой. В строке 2 инициализируется очередь с приоритетами Q, состоящая из эле- ментов множества С. Цикл for в строках 3-8 поочередно извлекает по два узла, х и у, которые характеризуются в очереди наименьшими частотами, и заменяет их в очереди новым узлом z, представляющим объединение упомянутых выше элементов. Частота появления z вычисляется в строке 7 как сумма частот х и у. Узел х является левым дочерним узлом z, а у — его правым дочерним узлом. (Этот порядок является произвольным; перестановка левого и правого дочерних узлов приводит к созданию другого кода с той же стоимостью.) После п — 1 объедине- ний в очереди остается один узел — корень дерева кодов, который возвращается в строке 9. При анализе времени работы алгоритма Хаффмана предполагается, что Q реа- лизована как бинарная неубывающая пирамида (см. главу 6). Для множества С, со- стоящего из п символов, инициализацию очереди Q в строке 2 можно выполнить 464 Часть IV. Усовершенствованные методы разработки и анализа за время О (п) с помощью процедуры Build_Min_Heap из раздела 6.3. Цикл for в строках 3-8 выполняется ровно и — 1 раз, и поскольку для каждой операции над пирамидой требуется время О (lgn), вклад цикла во время работы алгорит- ма равен O(nlgn). Таким образом, полное время работы процедуры Huffman с входным множеством, состоящим из п символов, равно О (nlgn). Корректность алгоритма Хаффмана Чтобы доказать корректность жадного алгоритма Huffman, покажем, что в за- даче о построении оптимального префиксного кода проявляются свойства жадного выбора и оптимальной подструктуры. В сформулированной ниже лемме показано соблюдение свойства жадного выбора. Лемма 16.2. Пусть С — алфавит, каждый символ с€С которого встречается с ча- стотой / [с]. Пусть х и у — два символа алфавита С с самыми низкими частотами. Тогда для алфавита С существует оптимальный префиксный код, кодовые слова символов х и у в котором имеют одинаковую длину и отличаются лишь последним битом. Доказательство. Идея доказательства состоит в том, чтобы взять дерево Т, пред- ставляющее произвольный оптимальный префиксный код, и преобразовать его в дерево, представляющее другой оптимальный префиксный код, в котором сим- волы х и у являются листьями с общим родительским узлом, причем в новом дереве эти листья находятся на максимальной глубине. Пусть а и b — два символа, представленные листьями с общим родительским узлом, которые находятся на максимальной глубине дерева Т. Предположим без потери общности, что / [а] ^ / [Ь] и / [х] ^ / [у]. Поскольку / [х] и / [у] — две самые маленькие исключением частоты (в указанном порядке), а / [а] и / [6] — две произвольные частоты, то выполняются соотношения <tex>f[x]^f [а] и / [у] ^ / [6z]. Как показано на рис. 16.5, в результате перестановки в дереве Т листьев а и х получается дерево Т", а при последующей перестановке в дереве V листьев Ь и у получается дерево Т". Согласно уравнению A6.5), разность стоимостей деревьев Т и Т" равна В(Т)-В (Г') = ?/(c)dr (с) - ?/(c)(fev (с) = сес сес = f [x] dT (х) + f [ay] dT (а) - f [x] dT, (х) - </ [a] dTtex> (а) = = / [х] dT (х) + / [a] dT (а) - / [х] dT (а) - / [а] dT (x) = = (f[a]-f[x})(dT(a)-dT(x)). Пусть <tex>0, поскольку величины / [а]-/ [х] и йт (aj—dr (x) неотрицательны. Величина / [а] — - f [х] неотрицательна, потому что х — лист с минимальной частотой, величина (о) — dr (x) неотрицательна, потому что а — лист на максимальной глубине Глава 16. Жадные алгоритмы 465 Рис. 16.5. Иллюстрация ключевых этапов доказательства леммы 16.2 в дереве Т. Аналогично, перестановка листьев у и b не приведет к увеличению стоимости, поэтому величина В (Т") — В (Т") неотрицательна. Таким образом, выполняется неравенство В (Г") ^ В (Т), и поскольку Т — оптимальное дерево, то должно также выполняться неравенство В (Т) T'< В (Т"), откуда следует, что В {Т") = В (Т). Таким образом, Т" — оптимальное дерево, в котором х и у — находящиеся на максимальной глубине дочерние листья одного и того же узла, что и доказывает лемму. д Из леммы 16.2 следует, что процесс построения оптимального дерева путем объединения узлов без потери общности можно начать с жадного выбора, при котором объединению подлежат два символа с наименьшими частотами. Почему такой выбор будет жадным? Стоимость объединения можно рассматривать как сумму частот входящих в него элементов. В упражнении 16.3-3 предлагается показать, что полная стоимость сконструированного таким образом дерева равна сумме стоимостей его составляющих. Из всевозможных вариантов объединения на каждом этапе в процедуре Huffman выбирается тот, в котором получается минимальная стоимость. В приведенной ниже лемме показано, что задача о составлении оптимальных префиксных кодов обладает свойством оптимальной подструктуры. Лемма 16.3. Пусть дан алфавит С, в котором для каждого символа се С опре- делены частоты / [с]. Пусть х иу — два символа из алфавита С с минимальными частотами. Пусть С — алфавит, полученный из алфавита С путем удаления сим- волов х и у и добавления нового символа z, так что С = С — {х,у} U {z}. По определению частоты / в алфавите С совпадают с частотами в алфавите С, за исключением частоты / [z] = f [x] + / [у]. Пусть Т" tex> — произвольное дерево, представляющее оптимальный префиксный код для алфавита С <tex>C'</tex> Тогда дерево Г<tex>T</tex>, полученное из дерева Т" <tex>T'</tex> путем замены листа <tex>z </tex> внутренним узлом с дочерними элементами х <tex>x</tex> и у<tex>y</tex>, представляет оптимальный префиксный код для алфавита С<tex>C</tex>. Доказательство. |proof=Сначала покажем, что стоимость В <tex>B(ГT) </tex> дерева Г можно выра- зить <tex>T</tex> может быть выражена через стоимость В <tex>B(Т"T') </tex> дерева Т", рассматривая стоимости компонентов из уравнения A6.5)<tex>T'</tex>. Для каждого символа се С — <tex>c \in C \backslash \{хx,уy \} выполняется соотношение 466 Часть IV. Усовершенствованные методы разработки и анализа Aт {с</tex> верно <tex>d_T(C) = йтd_{T' (с)}</tex>, следовательнозначит, /<tex>f[сc]Aтd_T(сc) = /f[c]d^d_{T'}(c)</tex>. Поскольку dr Так как <tex>d_T(#x) = = dr d_T(уy) = drd_{T' B:} (z) + 1</tex>, получаем соотношение то/ <tex>f[хx] dT d_T(хx) + f [уy] dT d_T(уy) = (/ f[хx] + f [y])(d_{уT'}(z) + 1) = f[z]d_{dT> T'}(z) + 1(f[x] + f[y]) = </tex> из которого чего следует равенство , что <tex> B(T) = B(T')+f[x) ] + f[y] </tex> илиИЛИ <tex> B{(T')=B(T)-f[x]-f[y]. </tex> Докажем лемму методом от противного. Предположим, что дерево Т <tex>T</tex> не представ- ляет представляет оптимальный префиксный код для алфавита С <tex>C</tex>. Тогда существует дерево Т"<tex>T''</tex> такое, для которого справедливо неравенство Вчто <tex>B(Т"T'') < В{ТB(T)</tex>. Согласно лемме 16.2(1), х элементы <tex>x</tex> и у без потери общности <tex>y</tex> можно считать дочерними элементами одного и того же узла. Пусть дерево Т"<tex>T''' </tex> получено из дерева Т" путем замены <tex>T''</tex> заменой элементов х <tex>x</tex> и у <tex>y</tex> листом <tex>z </tex> с частотой / <tex>f[z] = / f[хx] + f [уy]</tex>. Тогда можно записать:  <tex>B(T"''')=B{(T"'')-f[x}] -f{[y}] <B(T)-f[x}] -f[y} ] = B(T')</tex>,  что противоречит предположению о том, что дерево Т<tex>T' </tex> представляет оптимальный префиксный код для алфавита С<tex>C'</tex>. Таким образомЗначит, наше предположение о том, что дерево Г должно представлять <tex>T</tex> не представляет оптимальный префиксный код для алфавита С<tex>C</tex>, неверно, что и доказывает лемму. ? }} {{Теорема 16.4. Процедура Huffman |id=th1|statement=Алгоритм Хаффмана дает оптимальный префиксный код. Доказательство. |proof=Справедливость теоремы непосредственно следует из лемм 16(1) и (2)}} == См.также ==*[[Оптимальное_хранение_словаря_в_алгоритме_Хаффмана | Оптимальное хранение словаря в алгоритме Хаффмана]] == Источники информации == * Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ — 2 -е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4и 16*[http://en.wikipedia.org/wiki/Huffman_coding Wikipedia — Huffman coding]*[http://ru.wikipedia.org/wiki/%C4%E2%EE%E8%F7%ED%EE%E5_%E4%E5%F0%E5%E2%EE Википедия — Бинарное дерево]*[http://ru.3wikipedia.org/wiki/Префиксный_код Википедия — Префиксный код] [[Категория: Дискретная математика и алгоритмы]] [[Категория:Алгоритмы сжатия]]