Алгоритм Хаффмана — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 49 промежуточных версий 16 участников)
Строка 1: Строка 1:
 +
'''Алгоритм Хаффмана''' (англ. ''Huffman's algorithm'') — алгоритм [[Задача_об_оптимальном_префиксном_коде_с_сохранением_порядка._Монотонность_точки_разреза | оптимального префиксного кодирования]] алфавита. Был разработан в 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. Используется во многих программах сжатия данных, например, PKZIP 2, LZH и др.
 +
 
== Определение ==
 
== Определение ==
 +
 
{{Определение  
 
{{Определение  
 
|definition=
 
|definition=
'''Коды''' или '''Алгоритм Хаффмана''' ('''Huffman codes''') — широко распространенный и очень эффективный метод сжатия данных, который, в зависимости от характеристик этих данных, обычно позволяет сэкономить от 20% до 90% объема.}}
+
Пусть <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> узлов:
  
== Построение кода Хаффмана ==
 
 
В основу алгоритма Хаффмана положена идея: кодировать более коротко те символы, которые встречаются чаще, а те, которые встречаются реже кодировать длиннее. Для построения кода Хаффмана нам необходима таблица частот символов. Рассмотрим пример построения кода на простой строке '''''abacaba'''''<br>
 
 
{| class="wikitable"
 
{| class="wikitable"
! a || b || c ||
+
! Узел ||  a || b ||  r  || с  || d
 
|-
 
|-
| 4 || 2 || 1 ||
+
| Вес || 5 || 2 || 2 || 1 || 1
 
|}
 
|}
Следующим шагом будет построение дерева, где вершины - "символы", а пути до них соответствуют их префиксным кодам. 
 
Для этого на каждом шаге будем брать два символа с минимальной частотой вхождения, и объединять их в новые так называемые "символы" с частотой равной сумме частот тех символов, которые мы объединяли.
 
В примере мы объединим символы b и с в символ bc с частотой 3.
 
  
Хаффман изобрел жадный алгоритм, позволяющий составить оптимальный префиксный код, который получил название код Хаффмана. Доказательство корректности этого алгоритма основывается на свойстве жадного выбора и оптимальной подструктуре. Вместо того чтобы демонстрировать, что эти свойства выполняются, а затем разрабатывать псевдокод, сначала мы представим псевдокод. Это поможет прояснить, как алгоритм осуществляет жадный выбор. В приведенном ниже псевдокоде предполагается, что <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>. В результате слияния двух объектов образуется новый объект, частота появления которого является суммой частот объединенных объектов:
+
По алгоритму возьмем два символа с наименьшей частотой {{---}} это <tex>c</tex> и <tex>d</tex>. Сформируем из них новый узел <tex>cd</tex> весом <tex>2</tex> и добавим его к списку узлов:
<br><br>
+
 
'''Huffman(<tex>C</tex>)''' <br>
+
{| class="wikitable"
<tex>n \gets |C|</tex>  <br>
+
! Узел || a || b || r || cd
<tex>Q \gets C</tex> <br>
+
|-
'''for''' <tex>i \gets 1</tex> '''to''' <tex>n - 1</tex> <br>
+
| Вес || 5 || 2 || 2 || 2
:'''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>r</tex> и <tex>cd</tex>:
::<tex>f[z] \gets f[x]+f[y]</tex>
+
 
::Insert(<tex>Q</tex>, <tex>z</tex> ) <br>
+
{| class="wikitable"
'''return''' Extract_Min(<tex>Q</tex> ) <tex> \rhd </tex>  Возврат корня дерева <br><br>
+
! Узел || a || rcd || b
=== Пример работы алгоритма ===
+
|-
[[Файл:Huffman.jpg]]<br>
+
| Вес || 5 || 4 || 2
На каждом этапе показано содержимое очереди, элементы которой рассортированы в порядке возрастания их частот. На каждом шаге работы алгоритма объединяются два объекта (дерева) с самыми низкими частотами. Листья изображены в виде прямоугольников, в каждом из которых указана буква и соответствующая ей частота. Внутренние узлы представлены кругами, содержащими сумму частот дочерних узлов. Ребро, соединяющее внутренний узел с левым дочерним узлом, имеет метку 0, а ребро, соединяющее его с правым дочерним узлом, — метку 1. Слово кода для буквы образуется последовательностью меток на ребрах, соединяющих корень с листом, представляющим эту букву. По скольку данное множество содержит шесть букв, размер исходной очереди равен 6(часть ''а'' рисунка), а для построения дерева требуется пять слияний. Промежуточные этапы изображены в частях ''б-д''. Конечное дерево (''е'') представляет оптимальный префиксный код. Как уже говорилось, слово кода для буквы — это последовательность меток на пути от корня к листу с этой буквой.<br>
+
|}
В строке 2 инициализируется очередь с приоритетами <tex>Q</tex>, состоящая из элементов множества <tex>С</tex>. Цикл '''for''' в строках 3-8 поочередно извлекает по два узла, <tex>x</tex> и <tex>у</tex>, которые характеризуются в очереди наименьшими частотами, и заменяет их в очереди новым узлом, представляющим объединение упомянутых выше элементов. Частота появления <tex>z</tex> вычисляется в строке 7 как сумма частот <tex>x</tex> и <tex>y</tex>. Узел <tex>x</tex> является левым дочерним узлом <tex>z</tex>, а <tex>y</tex> — его правым дочерним узлом. (Этот порядок является произвольным; перестановка левого и правого дочерних узлов приводит к созданию другого кода с той же стоимостью.) После <tex>n - 1</tex> объединений в очереди остается один узел — корень дерева кодов, который возвращается в строке 9.
+
 
=== Оценка времени работы ===
+
Еще раз повторим эту же операцию, но для узлов <tex>rcd</tex> и <tex>b</tex>:
При анализе времени работы алгоритма Хаффмана предполагается, что <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))</tex>. Таким образом, полное время работы процедуры Huffman с входным множеством, состоящим из <tex>n</tex> символов, равно <tex>O(n \cdot lg(n))</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> бита, что существенно больше.
  
 
== Корректность алгоритма Хаффмана ==
 
== Корректность алгоритма Хаффмана ==
+
 
Чтобы доказать корректность жадного алгоритма Huffman, покажем, что в задаче о построении оптимального префиксного кода проявляются свойства жадного выбора и оптимальной подструктуры. В сформулированной ниже лемме показано соблюдение свойства жадного выбора.  
+
Чтобы доказать корректность алгоритма Хаффмана, покажем, что в задаче о построении оптимального префиксного кода проявляются свойства жадного выбора и оптимальной подструктуры. В сформулированной ниже лемме показано соблюдение свойства жадного выбора.
  
 
{{Лемма
 
{{Лемма
 
|id=lemma1
 
|id=lemma1
 
|about=1
 
|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> в котором имеют одинаковую длину и отличаются лишь последним битом.  
+
|statement=
|proof=Идея доказательства состоит в том, чтобы взять дерево <tex>T</tex>, представляющее произвольный оптимальный префиксный код, и преобразовать его в дерево, представляющее другой оптимальный префиксный код, в котором символы <tex>x</tex> и <tex>y</tex> являются листьями с общим родительским узлом, причем в новом дереве эти листья находятся на максимальной глубине. Пусть <tex>a</tex> и <tex>b</tex> — два символа, представленные листьями с общим родительским узлом, которые находятся на максимальной глубине дерева <tex>T</tex>. Предположим без потери общности, что <tex>f[a] \le f[b]</tex> и <tex>f[x] \le f[y]</tex>. Поскольку <tex>f[x]</tex> и <tex>f[y]</tex> — две самые маленькие частоты (в указанном порядке), <tex>f[a]</tex> и <tex>f[b]</tex> — две произвольные частоты, то выполняются соотношения <tex>f[x] \le f[a]</tex> и <tex>f[y] \le f[b]</tex>. В результате перестановки в дереве <tex>T</tex> листьев <tex>a</tex> и <tex>x</tex> получается дерево <tex>T'</tex>, а при последующей перестановке в дереве V листьев <tex>b</tex> и <tex>y</tex> получается дерево <tex>T''</tex>. Разность стоимостей деревьев Т и Т" равна <br>
+
Пусть <tex>C</tex> — алфавит, каждый символ <tex>c \in C</tex> которого встречается с частотой <tex>f[c]</tex>. Пусть <tex>x</tex> и <tex>y</tex> — два символа алфавита <tex>C</tex> с самыми низкими частотами.
<tex>B(T) - B(T') = \sum_{c \in C} f(c)d_T(C) - \sum_{c \in C} f(c)d_{T'}(C) =</tex><br><tex> = (f[a] - f[x])(d_T(a) - d_T(x)) \ge 0</tex>,<br>
+
 
поскольку величины <tex>f[a] - f[x]</tex> и <tex>d_T(a) - d_T(x)</tex> неотрицательны. Величина <tex>f[a] - f[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 B(T'')</tex>, и поскольку <tex>T</tex> — оптимальное дерево, то должно также выполняться неравенство <tex>B(T'') \le B(T')</tex>, откуда следует, что <tex>B(T') = B(T'')</tex>. Таким образом, <tex>T''</tex> — оптимальное дерево, в котором <tex>x</tex> и <tex>y</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'')</tex>. Отсюда следует, что <tex>B(T) = B(T'')</tex>. Значит, <tex>T''</tex> — дерево, представляющее оптимальный префиксный код, в котором символы <tex>x</tex> и <tex>y</tex> имеют одинаковую максимальную длину, что и доказывает лемму.
 
}}
 
}}
+
 
 
{{Лемма
 
{{Лемма
|id=lemma2.
+
|id=lemma2
 
|about=2
 
|about=2
|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 {х,у} \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>.  
+
|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 C - {x,y}</tex> выполняется соотношение <tex>d_T(C) = d_{T'}(c)</tex>, следовательно, <tex>f[c]d_T(C) = f[c]d_{T'}(c)</tex>. Поскольку <tex>d_T(x) = d_{T}(y) = d_{t'}(z) + 1</tex>, получаем соотношение<br>
+
|proof=
<tex>f[x]d_T(x) + f[y]d_{T}(y) = (f[x] + f[y])(d_{T'}(z) + 1) = f[z]d_{T'}(z) + (f[x] + f[y])</tex>
+
Сначала покажем, что стоимость <tex>B(T)</tex> дерева <tex>T</tex> может быть выражена через стоимость <tex>B(T')</tex> дерева <tex>T'</tex>. Для каждого символа <tex>c \in C \backslash \{x, y \}</tex> верно <tex>d_T(C) = d_{T'}</tex>, значит, <tex>f[c]d_T(c) = f[c]d_{T'}(c)</tex>. Так как <tex>d_T(x) = d_T(y) = d_{T'} (z) + 1</tex>, то
<br>
+
 
из которого следует равенство <br>
+
<tex>f[x]d_T(x) + f[y]d_T(y) = (f[x] + f[y])(d_{T'}(z) + 1) = f[z]d_{T'}(z) + (f[x] + f[y])</tex>
<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] </tex>
<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>.
+
или
 +
 
 +
<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>. Согласно лемме (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.3.
 
Доказательство.
 
 
{{Теорема
 
{{Теорема
 
|id=th1
 
|id=th1
 
|statement=
 
|statement=
Процедура Huffman дает оптимальный префиксный код.  
+
Алгоритм Хаффмана дает оптимальный префиксный код.  
 
|proof=
 
|proof=
 
Справедливость теоремы непосредственно следует из лемм (1) и (2)
 
Справедливость теоремы непосредственно следует из лемм (1) и (2)
 
}}
 
}}
  
== Литература ==
+
== См. также ==
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — С. 1296. — ISBN 5-8489-0857-4
+
*[[Оптимальное_хранение_словаря_в_алгоритме_Хаффмана | Оптимальное хранение словаря в алгоритме Хаффмана]]
 +
 
 +
== Источники информации ==
 +
 
 +
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4
 +
*[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.wikipedia.org/wiki/Префиксный_код Википедия — Префиксный код]
 +
 
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
 
 +
[[Категория:Алгоритмы сжатия]]

Текущая версия на 19:41, 4 сентября 2022

Алгоритм Хаффмана (англ. Huffman's algorithm) — алгоритм оптимального префиксного кодирования алфавита. Был разработан в 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. Используется во многих программах сжатия данных, например, PKZIP 2, LZH и др.

Определение

Определение:
Пусть [math]A=\{a_{1},a_{2}, \ldots ,a_{n}\}[/math] — алфавит из [math]n[/math] различных символов, [math]W=\{w_{1},w_{2}, \ldots ,w_{n}\}[/math] — соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов [math]C=\{c_{1},c_{2}, \ldots ,c_{n}\}[/math], где [math]c_{i}[/math] является кодом для символа [math]a_{i}[/math], такой, что:
  • [math]c_{i}[/math] не является префиксом для [math]c_{j}[/math], при [math]i \ne j[/math],
  • cумма [math]\sum\limits_{i \in [1, n]} w_{i}\cdot |c_{i}|[/math] минимальна ([math]|c_{i}|[/math] — длина кода [math]c_{i}[/math]),
называется кодом Хаффмана.


Алгоритм построения бинарного кода Хаффмана

Построение кода Хаффмана сводится к построению соответствующего бинарного дерева по следующему алгоритму:

  1. Составим список кодируемых символов, при этом будем рассматривать один символ как дерево, состоящее из одного элемента c весом, равным частоте появления символа в строке.
  2. Из списка выберем два узла с наименьшим весом.
  3. Сформируем новый узел с весом, равным сумме весов выбранных узлов, и присоединим к нему два выбранных узла в качестве детей.
  4. Добавим к списку только что сформированный узел вместо двух объединенных узлов.
  5. Если в списке больше одного узла, то повторим пункты со второго по пятый.

Время работы

Если сортировать элементы после каждого суммирования или использовать приоритетную очередь, то алгоритм будет работать за время [math]O(N \log N)[/math].Такую асимптотику можно улучшить до [math]O(N)[/math], используя обычные массивы.

Пример

Дерево Хаффмана для слова [math]abracadabra[/math]

Закодируем слово [math]abracadabra[/math]. Тогда алфавит будет [math]A= \{a, b, r, c, d\} [/math], а набор весов (частота появления символов алфавита в кодируемом слове) [math]W=\{5, 2, 2, 1, 1\}[/math]:

В дереве Хаффмана будет [math]5[/math] узлов:

Узел a b r с d
Вес 5 2 2 1 1

По алгоритму возьмем два символа с наименьшей частотой — это [math]c[/math] и [math]d[/math]. Сформируем из них новый узел [math]cd[/math] весом [math]2[/math] и добавим его к списку узлов:

Узел a b r cd
Вес 5 2 2 2

Затем опять объединим в один узел два минимальных по весу узла — [math]r[/math] и [math]cd[/math]:

Узел a rcd b
Вес 5 4 2

Еще раз повторим эту же операцию, но для узлов [math]rcd[/math] и [math]b[/math]:

Узел brcd a
Вес 6 5

На последнем шаге объединим два узла — [math]brcd[/math] и [math]a[/math]:

Узел abrcd
Вес 11

Остался один узел, значит, мы пришли к корню дерева Хаффмана (смотри рисунок). Теперь для каждого символа выберем кодовое слово (бинарная последовательность, обозначающая путь по дереву к этому символу от корня):

Символ a b r с d
Код 0 11 101 1000 1001

Таким образом, закодированное слово [math]abracadabra[/math] будет выглядеть как [math]01110101000010010111010[/math]. Длина закодированного слова — [math]23[/math] бита. Стоит заметить, что если бы мы использовали алгоритм кодирования с одинаковой длиной всех кодовых слов, то закодированное слово заняло бы [math]33[/math] бита, что существенно больше.

Корректность алгоритма Хаффмана

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

Лемма (1):
Пусть [math]C[/math] — алфавит, каждый символ [math]c \in C[/math] которого встречается с частотой [math]f[c][/math]. Пусть [math]x[/math] и [math]y[/math] — два символа алфавита [math]C[/math] с самыми низкими частотами. Тогда для алфавита [math]C[/math] существует оптимальный префиксный код, кодовые слова символов [math]x[/math] и [math]y[/math] в котором имеют одинаковую максимальную длину и отличаются лишь последним битом.
Доказательство:
[math]\triangleright[/math]

Возьмем дерево [math]T[/math], представляющее произвольный оптимальный префиксный код для алфавита [math]C[/math]. Преобразуем его в дерево, представляющее другой оптимальный префиксный код, в котором символы [math]x[/math] и [math]y[/math] — листья с общим родительским узлом, находящиеся на максимальной глубине.

Пусть символы [math]a[/math] и [math]b[/math] имеют общий родительский узел и находятся на максимальной глубине дерева [math]T[/math]. Предположим, что [math]f[a] \leqslant f[b][/math] и [math]f[x] \leqslant f[y][/math]. Так как [math]f[x][/math] и [math]f[y][/math] — две наименьшие частоты, а [math]f[a][/math] и [math]f[b][/math] — две произвольные частоты, то выполняются отношения [math]f[x] \leqslant f[a][/math] и [math]f[y] \leqslant f[b][/math]. Пусть дерево [math]T'[/math] — дерево, полученное из [math]T[/math] путем перестановки листьев [math]a[/math] и [math]x[/math], а дерево [math]T''[/math] — дерево полученное из [math]T'[/math] перестановкой листьев [math]b[/math] и [math]y[/math]. Разность стоимостей деревьев [math]T[/math] и [math]T'[/math] равна:

[math]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)),[/math]

что больше либо равно [math]0[/math], так как величины [math]f[a] - f[x][/math] и [math]d_T(a) - d_T(x)[/math] неотрицательны. Величина [math]f[a] - f[x][/math] неотрицательна, потому что [math]x[/math] — лист с минимальной частотой, а величина [math]d_T(a) - d_T(x)[/math] является неотрицательной, так как лист [math]a[/math] находится на максимальной глубине в дереве [math]T[/math]. Точно так же перестановка листьев [math]y[/math] и [math]b[/math] не будет приводить к увеличению стоимости. Таким образом, разность [math]B(T') - B(T'')[/math] тоже будет неотрицательной.

Таким образом, выполняется неравенство [math]B(T'') \leqslant B(T)[/math]. С другой стороны, [math]T[/math] — оптимальное дерево, поэтому должно выполняться неравенство [math]B(T) \leqslant B(T'')[/math]. Отсюда следует, что [math]B(T) = B(T'')[/math]. Значит, [math]T''[/math] — дерево, представляющее оптимальный префиксный код, в котором символы [math]x[/math] и [math]y[/math] имеют одинаковую максимальную длину, что и доказывает лемму.
[math]\triangleleft[/math]
Лемма (2):
Пусть дан алфавит [math]C[/math], в котором для каждого символа [math]c \in C[/math] определены частоты [math]f[c][/math]. Пусть [math]x[/math] и [math]y[/math] — два символа из алфавита [math]C[/math] с минимальными частотами. Пусть [math]C'[/math] — алфавит, полученный из алфавита [math]C[/math] путем удаления символов [math]x[/math] и [math]y[/math] и добавления нового символа [math]z[/math], так что [math]C' = C \backslash \{ x, y \} \cup {z}[/math]. По определению частоты [math]f[/math] в алфавите [math]C'[/math] совпадают с частотами в алфавите [math]C[/math], за исключением частоты [math]f[z] = f[x] + f[y][/math]. Пусть [math]T'[/math] — произвольное дерево, представляющее оптимальный префиксный код для алфавита [math]C'[/math] Тогда дерево [math]T[/math], полученное из дерева [math]T'[/math] путем замены листа [math]z[/math] внутренним узлом с дочерними элементами [math]x[/math] и [math]y[/math], представляет оптимальный префиксный код для алфавита [math]C[/math].
Доказательство:
[math]\triangleright[/math]

Сначала покажем, что стоимость [math]B(T)[/math] дерева [math]T[/math] может быть выражена через стоимость [math]B(T')[/math] дерева [math]T'[/math]. Для каждого символа [math]c \in C \backslash \{x, y \}[/math] верно [math]d_T(C) = d_{T'}[/math], значит, [math]f[c]d_T(c) = f[c]d_{T'}(c)[/math]. Так как [math]d_T(x) = d_T(y) = d_{T'} (z) + 1[/math], то

[math]f[x]d_T(x) + f[y]d_T(y) = (f[x] + f[y])(d_{T'}(z) + 1) = f[z]d_{T'}(z) + (f[x] + f[y])[/math]

из чего следует, что

[math] B(T) = B(T') + f[x] + f[y] [/math]

или

[math] B(T') = B(T) - f[x] - f[y] [/math]

Докажем лемму от противного. Предположим, что дерево [math]T[/math] не представляет оптимальный префиксный код для алфавита [math]C[/math]. Тогда существует дерево [math]T''[/math] такое, что [math]B(T'') \lt B(T)[/math]. Согласно лемме (1), элементы [math]x[/math] и [math]y[/math] можно считать дочерними элементами одного узла. Пусть дерево [math]T'''[/math] получено из дерева [math]T''[/math] заменой элементов [math]x[/math] и [math]y[/math] листом [math]z[/math] с частотой [math]f[z] = f[x] + f[y][/math]. Тогда

[math]B(T''') = B(T'') - f[x] - f[y] \lt B(T) - f[x] - f[y] = B(T')[/math],

что противоречит предположению о том, что дерево [math]T'[/math] представляет оптимальный префиксный код для алфавита [math]C'[/math]. Значит, наше предположение о том, что дерево [math]T[/math] не представляет оптимальный префиксный код для алфавита [math]C[/math], неверно, что и доказывает лемму.
[math]\triangleleft[/math]
Теорема:
Алгоритм Хаффмана дает оптимальный префиксный код.
Доказательство:
[math]\triangleright[/math]
Справедливость теоремы непосредственно следует из лемм (1) и (2)
[math]\triangleleft[/math]

См. также

Источники информации