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

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

Определение

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

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

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

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

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

Время работы

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

Пример

Дерево Хаффмана для слова $abracadabra$

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

В дереве Хаффмана будет $5$ узлов:

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

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

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

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

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

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

Узел	brcd	a
Вес	6	5

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

Узел	abrcd
Вес	11

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

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

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

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

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

Лемма (1):

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

Доказательство:

$\triangleright$

Возьмем дерево $T$, представляющее произвольный оптимальный префиксный код для алфавита $C$. Преобразуем его в дерево, представляющее другой оптимальный префиксный код, в котором символы $x$ и $y$ — листья с общим родительским узлом, находящиеся на максимальной глубине. Пусть символы $a$ и $b$ имеют общий родительский узел и находятся на максимальной глубине дерева $T$. Предположим, что $f[a] \leqslant f[b]$ и $f[x] \leqslant f[y]$. Так как $f[x]$ и $f[y]$ — две наименьшие частоты, а $f[a]$ и $f[b]$ — две произвольные частоты, то выполняются отношения $f[x] \leqslant f[a]$ и $f[y] \leqslant f[b]$. Пусть дерево $T'$ — дерево, полученное из $T$ путем перестановки листьев $a$ и $x$, а дерево $T''$ — дерево полученное из $T'$ перестановкой листьев $b$ и $y$. Разность стоимостей деревьев $T$ и $T'$ равна: $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)),$ что больше либо равно $0$, так как величины $f[a] - f[x]$ и $d_T(a) - d_T(x)$ неотрицательны. Величина $f[a] - f[x]$ неотрицательна, потому что $x$ — лист с минимальной частотой, а величина $d_T(a) - d_T(x)$ является неотрицательной, так как лист $a$ находится на максимальной глубине в дереве $T$. Точно так же перестановка листьев $y$ и $b$ не будет приводить к увеличению стоимости. Таким образом, разность $B(T') - B(T'')$ тоже будет неотрицательной. Таким образом, выполняется неравенство $B(T'') \leqslant B(T)$. С другой стороны, $T$ — оптимальное дерево, поэтому должно выполняться неравенство $B(T) \leqslant B(T'')$. Отсюда следует, что $B(T) = B(T'')$. Значит, $T''$ — дерево, представляющее оптимальный префиксный код, в котором символы $x$ и $y$ имеют одинаковую максимальную длину, что и доказывает лемму.

$\triangleleft$

Лемма (2):

Пусть дан алфавит $C$, в котором для каждого символа $c \in C$ определены частоты $f[c]$. Пусть $x$ и $y$ — два символа из алфавита $C$ с минимальными частотами. Пусть $C'$ — алфавит, полученный из алфавита $C$ путем удаления символов $x$ и $y$ и добавления нового символа $z$, так что $C' = C \backslash \{ x, y \} \cup {z}$. По определению частоты $f$ в алфавите $C'$ совпадают с частотами в алфавите $C$, за исключением частоты $f[z] = f[x] + f[y]$. Пусть $T'$ — произвольное дерево, представляющее оптимальный префиксный код для алфавита $C'$ Тогда дерево $T$, полученное из дерева $T'$ путем замены листа $z$ внутренним узлом с дочерними элементами $x$ и $y$, представляет оптимальный префиксный код для алфавита $C$.

Доказательство:

$\triangleright$

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

$\triangleleft$

Теорема:

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

Доказательство:

$\triangleright$

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

$\triangleleft$

См. также

• Оптимальное хранение словаря в алгоритме Хаффмана

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

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