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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Выполнен тикет 5.1 + загружена новая картинка и приведен новый пример + приведены английские термины)
м (rollbackEdits.php mass rollback)
 
(не показано 5 промежуточных версий 4 участников)
Строка 5: Строка 5:
 
{{Определение  
 
{{Определение  
 
|definition=
 
|definition=
Пусть <tex>A=\{a_{1},a_{2},...,a_{n}\}</tex> — алфавит из n различных символов, <tex>W=\{w_{1},w_{2},...,w_{n}\}</tex> — соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов <tex>C=\{c_{1},c_{2},...,c_{n}\}</tex>, где <tex>c_{i}</tex> является кодом для символа <tex>a_{i}</tex>, такой, что:
+
Пусть <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>, такой, что:
  
1. <tex>c_{i}</tex> не является префиксом для <tex>c_{j}</tex>, при <tex>i \ne j</tex>
+
:* <tex>c_{i}</tex> не является префиксом для <tex>c_{j}</tex>, при <tex>i \ne j</tex>,
  
2. Сумма <tex>\sum\limits_{i \in [1, n]} w_{i}\cdot c_{i}</tex> минимальна. (<tex>|c_{i}|</tex> — длина кода <tex>c_{i}</tex>)
+
:* cумма <tex>\sum\limits_{i \in [1, n]} w_{i}\cdot |c_{i}|</tex> минимальна (<tex>|c_{i}|</tex> — длина кода <tex>c_{i}</tex>),
  
 
называется '''кодом Хаффмана'''.
 
называется '''кодом Хаффмана'''.
 
}}
 
}}
 +
 
== Алгоритм построения бинарного кода Хаффмана ==
 
== Алгоритм построения бинарного кода Хаффмана ==
  
Построение кода Хаффмана сводится к построению соответствующего бинарного дерева по следующему алгоритму:
+
Построение кода Хаффмана сводится к построению соответствующего [[ Двоичная_куча | бинарного дерева]] по следующему алгоритму:
  
* Составим [[Список | список]] кодируемых символов, при этом будем рассматривать один символ как дерево, состоящее из одного элемента c весом, равным частоте появления символа в строке.
+
# Составим [[Список | список]] кодируемых символов, при этом будем рассматривать один символ как дерево, состоящее из одного элемента c весом, равным частоте появления символа в строке.
* Из списка выберем два узла с наименьшим весом.
+
# Из списка выберем два узла с наименьшим весом.
* Сформируем новый узел с весом, равным сумме весов выбранных узлов, и присоединим к нему два выбранных узла в качестве детей.
+
# Сформируем новый узел с весом, равным сумме весов выбранных узлов, и присоединим к нему два выбранных узла в качестве детей.
* Добавим к списку только что сформированный узел вместо двух объединенных узлов.
+
# Добавим к списку только что сформированный узел вместо двух объединенных узлов.
* Если в списке больше одного узла, то повторим пункты со второго по пятый.
+
# Если в списке больше одного узла, то повторим пункты со второго по пятый.
  
 
=== Время работы ===
 
=== Время работы ===
Строка 28: Строка 29:
 
=== Пример ===
 
=== Пример ===
  
[[Файл:Huffman_abracadabra.jpg|400px|thumb|right|Дерево Хаффмана для строки "<tex>abracadabra</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>abracadabra</tex>. Тогда алфавит будет <tex>A= \{a, b, r, c, d\} </tex>, а набор весов (частота появления символов алфавита в кодируемом слове) <tex>W=\{5, 2, 2, 1, 1\}</tex>:
  
 
В дереве Хаффмана будет <tex>5</tex> узлов:
 
В дереве Хаффмана будет <tex>5</tex> узлов:
Строка 48: Строка 49:
 
|}
 
|}
  
Затем опять объединим в один узел два минимальных по весу узла: <tex>r</tex> и <tex>cd</tex>:
+
Затем опять объединим в один узел два минимальных по весу узла {{---}} <tex>r</tex> и <tex>cd</tex>:
  
 
{| class="wikitable"
 
{| class="wikitable"
Строка 64: Строка 65:
 
|}
 
|}
  
На последнем шаге объединим два узла <tex>brcd</tex> и <tex>a</tex>.
+
На последнем шаге объединим два узла {{---}} <tex>brcd</tex> и <tex>a</tex>:
  
 
{| class="wikitable"
 
{| class="wikitable"
Строка 72: Строка 73:
 
|}
 
|}
  
Остался один узел, значит, мы пришли к корню дерева Хаффмана (смотри рисунок). Теперь для каждого символа выберем кодовое слово: бинарную последовательность, обозначающую путь по дереву к этому символу от корня :
+
Остался один узел, значит, мы пришли к корню дерева Хаффмана (смотри рисунок). Теперь для каждого символа выберем кодовое слово (бинарная последовательность, обозначающая путь по дереву к этому символу от корня):
  
 
{| class="wikitable"
 
{| class="wikitable"
Строка 80: Строка 81:
 
|}
 
|}
  
Таким образом, закодированное слово "<tex>abracadabra</tex>" будет выглядеть как <tex>01110101000010010111010</tex>. Длина закодированного слова {{---}} <tex>23</tex> бита. Стоит заметить, что если бы мы использовали алгоритм кодирования с одинаковой длиной всех кодовых слов (англ. ''Constant length coding''), то закодированная строка заняла бы <tex>33</tex> бита, что существенно больше.
+
Таким образом, закодированное слово <tex>abracadabra</tex> будет выглядеть как <tex>01110101000010010111010</tex>. Длина закодированного слова {{---}} <tex>23</tex> бита. Стоит заметить, что если бы мы использовали алгоритм кодирования с одинаковой длиной всех кодовых слов, то закодированное слово заняло бы <tex>33</tex> бита, что существенно больше.
  
 
== Корректность алгоритма Хаффмана ==
 
== Корректность алгоритма Хаффмана ==
Строка 136: Строка 137:
 
Справедливость теоремы непосредственно следует из лемм (1) и (2)
 
Справедливость теоремы непосредственно следует из лемм (1) и (2)
 
}}
 
}}
 +
 +
== См. также ==
 +
*[[Оптимальное_хранение_словаря_в_алгоритме_Хаффмана | Оптимальное хранение словаря в алгоритме Хаффмана]]
  
 
== Источники информации ==
 
== Источники информации ==
Строка 146: Строка 150:
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
  
[[Категория: Алгоритмы сжатия ]]
+
[[Категория:Алгоритмы сжатия]]

Текущая версия на 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]

См. также

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