Алгоритм Хаффмана

Алгоритм Хаффмана — алгоритм оптимального префиксного кодирования алфавита. Это один из классических алгоритмов, известных с 60-х годов. Использует только частоту появления одинаковых байт в изображении. Сопоставляет символам входного потока, которые встречаются большее число раз, цепочку бит меньшей длины. И, напротив, встречающимся редко — цепочку большей длины.

Определение

Определение:

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

Алгоритм

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

1. Составим список кодируемых символов, при этом будем рассматривать один символ как дерево, состоящее из одного элемента, весом, равным частоте появления символа в тексте.

2. Из списка выберем два узла с наименьшим весом.

3. Сформируем новый узел с весом, равным сумме весов выбранных узлов, и присоединим к нему два выбранных узла в качестве дочерних.

4. Добавим к списку только что сформированный узел.

5. Если в списке больше одного узла, то повторить п.2-п.5.

Пример

Обрабатываем b и c

Получившееся дерево

В основу алгоритма Хаффмана положена идея: кодировать более коротко те символы, которые встречаются чаще, а те, которые встречаются реже кодировать длиннее. Для построения кода Хаффмана нам необходима таблица частот символов. Рассмотрим пример построения кода на простой строке abacaba

a	b	c
4	2	1

Следующим шагом будет построение дерева, где вершины - "символы", а пути до них соответствуют их префиксным кодам. Для этого на каждом шаге будем брать два символа с минимальной частотой вхождения, и объединять их в новые так называемые символы с частотой равной сумме частот тех, которые мы объединяли, а также соединять их рёбрами, образуя таким образом дерево(см. рисунок). Выбирать минимальные два символа будем из всех символов, исключая те, которые мы уже выбирали. В примере мы объединим символы b и с в символ bc с частотой 3. Далее объединим a и bc в символ abc, получив тем самым дерево. Теперь пути от корня (abc) до листьев и есть Коды Хаффмана(каждому ребру соответствует либо 1 либо 0)

a	b	c
0	11	10

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

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

Лемма (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]x[/math] и [math]y[/math] являются листьями с общим родительским узлом, причем в новом дереве эти листья находятся на максимальной глубине. Пусть [math]a[/math] и [math]b[/math] — два символа, представленные листьями с общим родительским узлом, которые находятся на максимальной глубине дерева [math]T[/math]. Предположим без потери общности, что [math]f[a] \le f[b][/math] и [math]f[x] \le f[y][/math]. Поскольку [math]f[x][/math] и [math]f[y][/math] — две самые маленькие частоты (в указанном порядке), [math]f[a][/math] и [math]f[b][/math] — две произвольные частоты, то выполняются соотношения [math]f[x] \le f[a][/math] и [math]f[y] \le f[b][/math]. В результате перестановки в дереве [math]T[/math] листьев [math]a[/math] и [math]x[/math] получается дерево [math]T'[/math], а при последующей перестановке в дереве V листьев [math]b[/math] и [math]y[/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)) \ge 0 ,[/math] поскольку величины [math]f[a] - f[x][/math] и [math]d_T(a) - d_T(x)[/math] неотрицательны. Величина [math]f[a] - f[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') \le B(T'')[/math], и поскольку [math]T[/math] — оптимальное дерево, то должно также выполняться неравенство [math]B(T'') \le 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 \le C - {x,y}[/math] выполняется соотношение [math]d_T(C) = d_{T'}(c)[/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]

Литература

• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — С. 1296. — ISBN 5-8489-0857-4