Изменения

Пусть <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>), называется '''Коды''' или '''Алгоритм кодом Хаффмана''' ('''Huffman codes''') — широко распространенный и очень эф- фективный метод сжатия данных, который, в зависимости от характеристик этих данных, обычно позволяет сэкономить от 20% до 90% объема.

== Построение Алгоритм построения бинарного кода Хаффмана == Хаффман изобрел жадный алгоритмПостроение кода Хаффмана сводится к построению соответствующего [[ Двоичная_куча | бинарного дерева]] по следующему алгоритму: # Составим [[Список | список]] кодируемых символов, при этом будем рассматривать один символ как дерево, позволяющий составить оптимальный префиксный кодсостоящее из одного элемента c весом, который получил название код Хаффманаравным частоте появления символа в строке.# Из списка выберем два узла с наименьшим весом. Доказательство корректности этого алгоритма основывается на свойстве жадного выбора # Сформируем новый узел с весом, равным сумме весов выбранных узлов, и оптимальной подструктуреприсоединим к нему два выбранных узла в качестве детей. Вместо того чтобы демонстрировать, # Добавим к списку только что эти свойства выполняютсясформированный узел вместо двух объединенных узлов.# Если в списке больше одного узла, а затем разрабатывать псевдокод, сначала мы представим псевдокодто повторим пункты со второго по пятый. Это поможет прояснить === Время работы ===Если сортировать элементы после каждого суммирования или использовать [[Приоритетные_очереди | приоритетную очередь]], как то алгоритм осуществляет жадный выбор. В приведенном ниже псевдокоде предполагается, что будет работать за время <tex>CO(N \log N)</tex> — множество, состоящее из .Такую асимптотику можно [[Алгоритм_Хаффмана_за_O(n) |улучшить до <tex>nO(N)</tex> символов]], и что каждый из символов используя обычные массивы. === Пример === [[Файл:Huffman_abracadabra.jpg|400px|thumb|right|Дерево Хаффмана для слова <tex>c\in Cabracadabra</tex> — объект с определенной частотой ]] Закодируем слово <tex>f(c)abracadabra</tex>. В алгоритме строится дерево Тогда алфавит будет <tex>T</tex>A= \{a, b, соответствующее оптимальному кодуr, причем построение идет в восходящем направлении. Процесс построения начинается с множестваc, состоящего из <tex>|C|d\} </tex> листьев, после чего последовательно выполняется а набор весов (частота появления символов алфавита в кодируемом слове) <tex>|C|-1</tex> операций "слияния"W=\{5, в результате которых образуется конечное дерево. Для идентификации двух наименее часто встречающихся объектов2, подлежащих слиянию2, используется очередь с приоритетами <tex>Q</tex>1, ключами в которой являются частоты <tex>f1\}</tex>. В результате слияния двух объектов образуется новый объект, частота появления которого является суммой частот объединенных объектов:<br><br>'''Huffman(В дереве Хаффмана будет <tex>C5</tex>)''' <br>узлов: {| class="wikitable"<tex>n \gets ! Узел || a || b || r || с |C|</tex> <br>d<tex>Q \gets C</tex> <br>|-'''for''' <tex>i \gets | Вес || 5 || 2 || 2 || 1</tex> '''to''' <tex>n - || 1</tex> <br>:'''do''' Выделить память для узла |} По алгоритму возьмем два символа с наименьшей частотой {{---}} это <tex>zc</tex> <br>::left[и <tex> zd</tex>]. Сформируем из них новый узел <tex> \gets x \getscd</tex> Extract_Min(весом <tex> Q2</tex>)<br> и добавим его к списку узлов: {| class="wikitable"! Узел || a || b || r || cd |-| Вес || 5 || 2 || 2 || 2|} ::right[Затем опять объединим в один узел два минимальных по весу узла {{---}} <tex>zr</tex>]и <tex>\gets y \gets cd</tex> Extract_Min(<tex>Q</tex>) <br>: {| class="wikitable"! Узел || a || rcd || b |-| Вес || 5 || 4 || 2 |}::<tex>f[z] \gets f[x]+f[y]</tex> ::Insert(Еще раз повторим эту же операцию, но для узлов <tex>Qrcd</tex>, и <tex>zb</tex> ) <br>: {| class="wikitable"! Узел || brcd || a|-| Вес || 6 || 5 |} '''return''' Extract_Min(На последнем шаге объединим два узла {{---}} <tex>Qbrcd</tex> ) и <tex> \rhd a</tex> Возврат корня дерева <br><br>: {| class=== Пример работы алгоритма ==="wikitable"! Узел || abrcd|-| Вес || 11|}[[Файл:Huffman.jpg]]<br>На каждом этапе показано содержимое очереди, элементы которой рассортированы в порядке возрастания их частот. На каждом шаге работы алгоритма объединяются два объекта (дерева) с самыми низкими частотами. Листья изображены в виде прямоугольников, в каждом из которых указана буква и соответствующая ей частота. Внутренние узлы представлены кругами, содержащими сумму частот дочерних узлов. Ребро, соединяющее внутренний Остался один узел с левым дочерним узлом, имеет метку 0значит, а ребро, соединяющее его с правым дочерним узлом, — метку 1. Слово кода для буквы образуется последовательностью меток на ребрах, соединяющих корень с листом, представляющим эту букву. По скольку данное множество содержит шесть букв, размер исходной очереди равен 6(часть а рисунка), а для построения мы пришли к корню дерева требуется пять слияний. Промежуточные этапы изображены в частях б-д. Конечное дерево Хаффмана (есмотри рисунок) представляет оптимальный префиксный код. Как уже говорилось, Теперь для каждого символа выберем кодовое слово кода для буквы — это (бинарная последовательность меток на пути , обозначающая путь по дереву к этому символу от корня к листу ): {| class="wikitable"! Символ || a || b || r || с этой буквой. В строке 2 инициализируется очередь с приоритетами Q, состоящая из элементов множества С. Цикл for в строках 3|| d|-8 поочередно извлекает по два узла, х и у, которые характеризуются в очереди наименьшими частотами, и заменяет их в очереди новым узлом z, представляющим объединение упомянутых выше элементов. Частота появления z вычисляется в строке 7 как сумма частот х и у. Узел х является левым дочерним узлом z, а у — его правым дочерним узлом. (Этот порядок является произвольным; перестановка левого и правого дочерних узлов приводит к созданию другого кода с той же стоимостью.) После п — 1 объединений в очереди остается один узел — корень дерева кодов| Код || 0 || 11 || 101 || 1000 || 1001|} Таким образом, который возвращается в строке 9. При анализе времени работы алгоритма Хаффмана предполагается, что Q реализована закодированное слово <tex>abracadabra</tex> будет выглядеть как бинарная неубывающая пирамида (см<tex>01110101000010010111010</tex>. главу 6). Для множества С, состоящего из п символов, инициализацию очереди Q в строке 2 можно выполнить 464 Часть IV. Усовершенствованные методы разработки и анализа за время О (п) с помощью процедуры Build_Min_Heap из раздела 6.3. Цикл for в строках 3Длина закодированного слова {{---8 выполняется ровно и — 1 раз, и поскольку для каждой операции над пирамидой требуется время О (lgn), вклад цикла во время работы алгоритма равен O(nlgn)}} <tex>23</tex> бита. Таким образомСтоит заметить, полное время работы процедуры Huffman что если бы мы использовали алгоритм кодирования с входным множествомодинаковой длиной всех кодовых слов, состоящим из п символовто закодированное слово заняло бы <tex>33</tex> бита, равно О (nlgn)что существенно больше.

Чтобы доказать корректность жадного алгоритма HuffmanХаффмана, покажем, что в за- даче задаче о построении оптимального префиксного кода проявляются свойства жадного выбора и оптимальной подструктуры. В сформулированной ниже лемме показано соблюдение свойства жадного выбора.  {{Лемма 16.2. |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[6b] </tex> — две произвольные частоты, то выполняются соотношения отношения <tex>f[x]^\leqslant f [аa] </tex> и / <tex>f[уy] ^ / \leqslant f[6b]</tex>. Как показано на рис. 16.5Пусть дерево <tex>T'</tex> — дерево, в результате полученное из <tex>T</tex> путем перестановки в дереве Т листьев а <tex>a</tex> и х получается дерево Т"<tex>x</tex>, а при последующей перестановке в дереве V дерево <tex>T''</tex> — дерево полученное из <tex>T'</tex> перестановкой листьев Ь <tex>b</tex> и у получается дерево Т". Согласно уравнению A6<tex>y</tex>.5), разность Разность стоимостей деревьев Т <tex>T</tex> и Т" <tex>T'</tex> равна :В<tex>B(ТT)-В B(ГT') = ?/\sum\limits_{c \in C} f(c)dr d_T(сc) - ?/\sum\limits_{c \in C} f(c)d_{T'}(fev (сc) = сес сес = f [x] dT (х) + f [a] dT (а) - f [x] dT, (х) - / [a] dT> (а) = = / [х] dT d_T(х) + / [a] dT (а) - / [х] dT d_T(аx)) - ,</tex> что больше либо равно <tex>0</ [а] dT (x) = = (tex>, так как величины <tex>f[a]-f[x})(dT]</tex> и <tex>d_T(a)-dTd_T(x))</tex>0, поскольку величины / [а]-/ [х] и йт (aj—dr (x) неотрицательны. Величина / <tex>f[аa] — - f [хx] </tex> неотрицательна, потому что х <tex>x</tex> — лист с минимальной частотой, а величина <tex>d_T(оa) — dr - d_T(x) неотрицательна</tex> является неотрицательной, потому что а — так как лист <tex>a</tex> находится на максимальной глубине Глава 16. Жадные алгоритмы 465 Рис. 16.5. Иллюстрация ключевых этапов доказательства леммы 16.2 в дереве Т<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''), откуда </tex>. Отсюда следует, что В {Т"<tex>B(T) = В B(ТT'')</tex>. Таким образомЗначит, Т" <tex>T''</tex> — оптимальное дерево, представляющее оптимальный префиксный код, в котором х символы <tex>x</tex> и у — находящиеся на максимальной глубине дочерние листья одного и того же узла<tex>y</tex> имеют одинаковую максимальную длину, что и доказывает лемму. д Из леммы 16.2 следует, что процесс построения оптимального дерева путем объединения узлов без потери общности можно начать с жадного выбора, при }}котором объединению подлежат два символа с наименьшими частотами. Почему такой выбор будет жадным? Стоимость объединения можно рассматривать как {{Леммасумму частот входящих в него элементов. В упражнении 16.3-3 предлагается |id=lemma2показать, что полная стоимость сконструированного таким образом дерева равна |about=2сумме стоимостей его составляющих. Из всевозможных вариантов объединения на каждом этапе в процедуре Huffman выбирается тот, в котором получается минимальная стоимость. В приведенной ниже лемме показано, что задача о составлении оптимальных префиксных кодов обладает свойством оптимальной подструктуры. Лемма 16.3. |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>C</tex> путем удаления сим- волов х символов <tex>x</tex> и у <tex>y</tex> и добавления нового символа <tex>z</tex>, так что С <tex>C' = С — C \backslash \{хx,уy \} U \cup {z}</tex>. По определению частоты <tex>f</ tex> в алфавите С <tex>C'</tex> совпадают с частотами в алфавите С<tex>C</tex>, за исключением частоты / <tex>f[z] = f [x] + / f[уy]</tex>. Пусть Т" <tex>T'</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>, неверно, что и доказывает лемму. ? }} 

Процедура Huffman Алгоритм Хаффмана дает оптимальный префиксный код.

Справедливость теоремы непосредственно следует из лемм (1 ) и (2)