Изменения

Пусть <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('''Huffman codes'''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, обычно позволяет сэкономить от 20% до 90% объема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>C</tex> — множество, состоящее из <tex>n</tex> символов, и что каждый из символов <tex>c\in C</tex> — объект с определенной частотой <tex>f(c)</tex>. В алгоритме строится дерево <tex>T</tex>, соответствующее оптимальному коду, причем построение идет в восходящем направлении. Процесс построения начинается с множества, состоящего из <tex>|C|</tex> листьев, после чего последовательно выполняется <tex>|C|-1</tex> операций "слияния", в результате которых образуется конечное дерево. Для идентификации двух наименее часто встречающихся объектов, подлежащих слиянию, используется очередь с приоритетами <tex>Q</tex>, ключами в которой являются частоты <tex>f</tex>. В результате слияния двух объектов образуется новый объект, частота появления которого является суммой частот объединенных объектов:<br><br>'''Huffman(<tex>C</tex>)''' <br><tex>n \gets |C|</tex> <br><tex>Q \gets C</tex> <br>'''for''' <tex>i \gets 1</tex> '''to''' <tex>n - 1</tex> <br>:'''do''' Выделить память для узла <tex>z</tex> <br>::left[<tex> z</tex>]<tex> \gets x \gets</tex> Extract_Min(<tex> Q</tex>)<br> ::right[<tex>z</tex>]<tex>\gets y \gets </tex> Extract_Min(<tex>Q</tex>) <br>::<tex>f[z] \gets f[x]+f[y]</tex> ::Insert(<tex>Q</tex>, <tex>z</tex> ) <br>'''return''' Extract_Min(<tex>Q</tex> ) <tex> \rhd </tex> Возврат корня дерева <br><br>=== Пример работы алгоритма ===[[Файл:Huffman.jpg]]<br>На каждом этапе показано содержимое очереди, элементы которой рассортированы в порядке возрастания их частот. На каждом шаге работы алгоритма объединяются два объекта (дерева) с самыми низкими частотами. Листья изображены в виде прямоугольников, в каждом из которых указана буква и соответствующая ей частота. Внутренние узлы представлены кругами, содержащими сумму частот дочерних узлов. Ребро, соединяющее внутренний узел с левым дочерним узлом, имеет метку 0, а ребро, соединяющее его с правым дочерним узлом, — метку 1. Слово кода для буквы образуется последовательностью меток на ребрах, соединяющих корень с листом, представляющим эту букву. По скольку данное множество содержит шесть букв, размер исходной очереди равен 6(часть ''а'' рисунка), а для построения дерева требуется пять слияний. Промежуточные этапы изображены в частях ''б-д''. Конечное дерево (''е'') представляет оптимальный префиксный код. Как уже говорилосьТаким образом, закодированное слово кода для буквы — это последовательность меток на пути от корня к листу с этой буквой.<br> В строке 2 инициализируется очередь с приоритетами <tex>Q</tex>, состоящая из элементов множества <tex>С</tex>. Цикл '''for''' в строках 3-8 поочередно извлекает по два узла, <tex>x</tex> и <tex>уabracadabra</tex>, которые характеризуются в очереди наименьшими частотами, и заменяет их в очереди новым узлом, представляющим объединение упомянутых выше элементов. Частота появления <tex>z</tex> вычисляется в строке 7 будет выглядеть как сумма частот <tex>x</tex> и <tex>y01110101000010010111010</tex>. Узел <tex>x</tex> является левым дочерним узлом <tex>z</tex>, а <tex>y</tex> — его правым дочерним узлом. (Этот порядок является произвольным; перестановка левого и правого дочерних узлов приводит к созданию другого кода с той же стоимостью.) После <tex>n Длина закодированного слова {{- 1</tex> объединений в очереди остается один узел — корень дерева кодов, который возвращается в строке 9.=== Оценка времени работы ===При анализе времени работы алгоритма Хаффмана предполагается, что <tex>Q</tex> реализована как бинарная неубывающая пирамида. Для множества <tex>C</tex>, состоящего из <tex>n</tex> символов, инициализацию очереди <tex>Q</tex> в строке 2 можно выполнить за время <tex>O(n)</tex>. Цикл for в строках 3-8 выполняется ровно <tex>n - 1}} </tex> раз, и поскольку для каждой операции над пирамидой требуется время<tex>O(lg(n))</tex>, вклад цикла во время работы алгоритма равен <tex>O(n \cdot lg(n))23</tex>бита. Таким образомСтоит заметить, полное время работы процедуры Huffman что если бы мы использовали алгоритм кодирования с входным множествомодинаковой длиной всех кодовых слов, состоящим из то закодированное слово заняло бы <tex>n33</tex> символовбита, равно <tex>O(n \cdot lg(n))</tex>что существенно больше.

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

|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] \le leqslant f[b]</tex> и <tex>f[x] \le leqslant f[y]</tex>. Поскольку Так как <tex>f[x]</tex> и <tex>f[y]</tex> — две самые маленькие наименьшие частоты (в указанном порядке), а <tex>f[a]</tex> и <tex>f[b]</tex> — две произвольные частоты, то выполняются соотношения отношения <tex>f[x] \le leqslant f[a]</tex> и <tex>f[y] \le leqslant f[b]</tex>. В результате перестановки в дереве Пусть дерево <tex>T'</tex> — дерево, полученное из <tex>T</tex> путем перестановки листьев <tex>a</tex> и <tex>x</tex> получается , а дерево <tex>T''</tex> — дерево полученное из <tex>T'</tex>, а при последующей перестановке в дереве V перестановкой листьев <tex>b</tex> и <tex>y</tex> получается дерево . Разность стоимостей деревьев <tex>T''</tex>. Разность стоимостей деревьев Т и Т" равна <brtex>T'</tex>равна: <tex>B(T) - B(T') = \sum_sum\limits_{c \in C} f(c)d_T(Cc) - \sum_sum\limits_{c \in C} f(c)d_{T'}(Cc) =</tex><br><tex> = (f[a] - f[x])(d_T(a) - d_T(x)) \ge ,</tex> что больше либо равно <tex>0</tex>,<br> поскольку так как величины <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'') \le leqslant B(T'')</tex>. С другой стороны, и поскольку <tex>T</tex> — оптимальное дерево, то поэтому должно также выполняться неравенство <tex>B(T'') \le leqslant B(T'')</tex>, откуда . Отсюда следует, что <tex>B(T') = B(T'')</tex>. Таким образомЗначит, <tex>T''</tex> — оптимальное дерево, представляющее оптимальный префиксный код, в котором символы <tex>x</tex> и <tex>y</tex> — находящиеся на максимальной глубине дочерние листья одного и того же узлаимеют одинаковую максимальную длину, что и доказывает лемму.

|id=lemma2.

|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 \} \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> дерева <tex>T'</tex>. Для каждого символа <tex>c \le in C - \backslash \{x,y\}</tex> выполняется соотношение верно <tex>d_T(C) = d_{T'}(c)</tex>, следовательнозначит, <tex>f[c]d_T(Cc) = f[c]d_{T'}(c)</tex>. Поскольку Так как <tex>d_T(x) = d_{T}d_T(y) = d_{tT'}(z) + 1</tex>, получаем соотношение<br>то <tex>f[x]d_T(x) + f[y]d_{T}d_T(y) = (f[x] + f[y])(d_{T'}(z) + 1) = f[z]d_{T'}(z) + (f[x] + f[y])</tex><br>из которого чего следует равенство <br>, что <tex> B(T) = B(T') + f[x] + f[y] </tex> <br>ИЛИ <br>или <tex> B(T') = B(T) - f[x] - f[y] </tex>. <br> Докажем лемму методом от противного. Предположим, что дерево <tex> T </tex> не представляет оптимальный префиксный код для алфавита <tex> C </tex>. Тогда существует дерево <tex> T'' </tex>такое, для которого справедливо неравенство что <tex> B(T'') < B(T) </tex>. Согласно лемме (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>. Тогда можно записать:<br>  <tex>B(T''') = B(T'') - f[x] - f[y] < B(T) - f[x] -f[y] = B(T')</tex>,<br>  что противоречит предположению о том, что дерево <tex>T'</tex> представляет оптимальный префиксный код для алфавита <tex>C'</tex>. Таким образомЗначит, наше предположение о том, что дерево <tex>T</tex> должно представлять не представляет оптимальный префиксный код для алфавита <tex>C</tex>, неверно, что и доказывает лемму.

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