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

Определение

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

Коды или Алгоритм Хаффмана (Huffman codes) — широко распространенный и очень эффективный метод сжатия данных, который, в зависимости от характеристик этих данных, обычно позволяет сэкономить от 20% до 90% объема.

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

Построение кода Хаффмана

Хаффман изобрел жадный алгоритм, позволяющий составить оптимальный префиксный код, который получил название код Хаффмана. Доказательство корректности этого алгоритма основывается на свойстве жадного выбора и оптимальной подструктуре. Вместо того чтобы демонстрировать, что эти свойства выполняются, а затем разрабатывать псевдокод, сначала мы представим псевдокод. Это поможет прояснить, как алгоритм осуществляет жадный выбор. В приведенном ниже псевдокоде предполагается, что [math]C[/math] — множество, состоящее из [math]n[/math] символов, и что каждый из символов [math]c\in C[/math] — объект с определенной частотой [math]f(c)[/math]. В алгоритме строится дерево [math]T[/math], соответствующее оптимальному коду, причем построение идет в восходящем направлении. Процесс построения начинается с множества, состоящего из [math]|C|[/math] листьев, после чего последовательно выполняется [math]|C|-1[/math] операций "слияния", в результате которых образуется конечное дерево. Для идентификации двух наименее часто встречающихся объектов, подлежащих слиянию, используется очередь с приоритетами [math]Q[/math], ключами в которой являются частоты [math]f[/math]. В результате слияния двух объектов образуется новый объект, частота появления которого является суммой частот объединенных объектов:

Huffman([math]C[/math])
[math]n \gets |C|[/math]
[math]Q \gets C[/math]
for [math]i \gets 1[/math] to [math]n - 1[/math]

do Выделить память для узла [math]z[/math]

left[[math] z[/math]][math] \gets x \gets[/math] Extract_Min([math] Q[/math])

right[[math]z[/math]][math]\gets y \gets [/math] Extract_Min([math]Q[/math])

[math]f[z] \gets f[x]+f[y][/math]

Insert([math]Q[/math], [math]z[/math] )

return Extract_Min([math]Q[/math] ) [math] \rhd [/math] Возврат корня дерева

Пример работы алгоритма

На каждом этапе показано содержимое очереди, элементы которой рассортированы в порядке возрастания их частот. На каждом шаге работы алгоритма объединяются два объекта (дерева) с самыми низкими частотами. Листья изображены в виде прямоугольников, в каждом из которых указана буква и соответствующая ей частота. Внутренние узлы представлены кругами, содержащими сумму частот дочерних узлов. Ребро, соединяющее внутренний узел с левым дочерним узлом, имеет метку 0, а ребро, соединяющее его с правым дочерним узлом, — метку 1. Слово кода для буквы образуется последовательностью меток на ребрах, соединяющих корень с листом, представляющим эту букву. По скольку данное множество содержит шесть букв, размер исходной очереди равен 6(часть а рисунка), а для построения дерева требуется пять слияний. Промежуточные этапы изображены в частях б-д. Конечное дерево (е) представляет оптимальный префиксный код. Как уже говорилось, слово кода для буквы — это последовательность меток на пути от корня к листу с этой буквой.
В строке 2 инициализируется очередь с приоритетами [math]Q[/math], состоящая из элементов множества [math]С[/math]. Цикл for в строках 3-8 поочередно извлекает по два узла, [math]x[/math] и [math]у[/math], которые характеризуются в очереди наименьшими частотами, и заменяет их в очереди новым узлом, представляющим объединение упомянутых выше элементов. Частота появления [math]z[/math] вычисляется в строке 7 как сумма частот [math]x[/math] и [math]y[/math]. Узел [math]x[/math] является левым дочерним узлом [math]z[/math], а [math]y[/math] — его правым дочерним узлом. (Этот порядок является произвольным; перестановка левого и правого дочерних узлов приводит к созданию другого кода с той же стоимостью.) После [math]n - 1[/math] объединений в очереди остается один узел — корень дерева кодов, который возвращается в строке 9.

Оценка времени работы

При анализе времени работы алгоритма Хаффмана предполагается, что [math]Q[/math] реализована как бинарная неубывающая пирамида. Для множества [math]C[/math], состоящего из [math]n[/math] символов, инициализацию очереди [math]Q[/math] в строке 2 можно выполнить за время [math]O(n)[/math]. Цикл for в строках 3-8 выполняется ровно [math]n - 1[/math] раз, и поскольку для каждой операции над пирамидой требуется время[math]O(lg(n))[/math], вклад цикла во время работы алгоритма равен [math]O(n \cdot lg(n))[/math]. Таким образом, полное время работы процедуры Huffman с входным множеством, состоящим из [math]n[/math] символов, равно [math]O(n \cdot lg(n))[/math].

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

Чтобы доказать корректность жадного алгоритма Huffman, покажем, что в за- даче о построении оптимального префиксного кода проявляются свойства жадного выбора и оптимальной подструктуры. В сформулированной ниже лемме показано соблюдение свойства жадного выбора. Лемма 16.2. Пусть С — алфавит, каждый символ с€С которого встречается с ча- стотой / [с]. Пусть х и у — два символа алфавита С с самыми низкими частотами. Тогда для алфавита С существует оптимальный префиксный код, кодовые слова символов х и у в котором имеют одинаковую длину и отличаются лишь последним битом. Доказательство. Идея доказательства состоит в том, чтобы взять дерево Т, пред- ставляющее произвольный оптимальный префиксный код, и преобразовать его в дерево, представляющее другой оптимальный префиксный код, в котором сим- волы х и у являются листьями с общим родительским узлом, причем в новом дереве эти листья находятся на максимальной глубине. Пусть а и b — два символа, представленные листьями с общим родительским узлом, которые находятся на максимальной глубине дерева Т. Предположим без потери общности, что / [а] ^ / [Ь] и / [х] ^ / [у]. Поскольку / [х] и / [у] — две самые маленькие частоты (в указанном порядке), а / [а] и / [6] — две произвольные частоты, то выполняются соотношения f[x]^f [а] и / [у] ^ / [6]. Как показано на рис. 16.5, в результате перестановки в дереве Т листьев а и х получается дерево Т", а при последующей перестановке в дереве V листьев Ь и у получается дерево Т". Согласно уравнению A6.5), разность стоимостей деревьев Т и Т" равна В(Т)-В (Г') = ?/(c)dr (с) - ?/(c)(fev (с) = сес сес = f [x] dT (х) + f [a] dT (а) - f [x] dT, (х) - / [a] dT> (а) = = / [х] dT (х) + / [a] dT (а) - / [х] dT (а) - / [а] dT (x) = = (f[a]-f[x})(dT(a)-dT(x))>0, поскольку величины / [а]-/ [х] и йт (aj—dr (x) неотрицательны. Величина / [а] — - f [х] неотрицательна, потому что х — лист с минимальной частотой, величина (о) — dr (x) неотрицательна, потому что а — лист на максимальной глубине Глава 16. Жадные алгоритмы 465 Рис. 16.5. Иллюстрация ключевых этапов доказательства леммы 16.2 в дереве Т. Аналогично, перестановка листьев у и b не приведет к увеличению стоимости, поэтому величина В (Т") — В (Т") неотрицательна. Таким образом, выполняется неравенство В (Г") ^ В (Т), и поскольку Т — оптимальное дерево, то должно также выполняться неравенство В (Т) < В (Т"), откуда следует, что В {Т") = В (Т). Таким образом, Т" — оптимальное дерево, в котором х и у — находящиеся на максимальной глубине дочерние листья одного и того же узла, что и доказывает лемму. д Из леммы 16.2 следует, что процесс построения оптимального дерева путем объединения узлов без потери общности можно начать с жадного выбора, при котором объединению подлежат два символа с наименьшими частотами. Почему такой выбор будет жадным? Стоимость объединения можно рассматривать как сумму частот входящих в него элементов. В упражнении 16.3-3 предлагается показать, что полная стоимость сконструированного таким образом дерева равна сумме стоимостей его составляющих. Из всевозможных вариантов объединения на каждом этапе в процедуре Huffman выбирается тот, в котором получается минимальная стоимость. В приведенной ниже лемме показано, что задача о составлении оптимальных префиксных кодов обладает свойством оптимальной подструктуры. Лемма 16.3. Пусть дан алфавит С, в котором для каждого символа се С опре- делены частоты / [с]. Пусть х иу — два символа из алфавита С с минимальными частотами. Пусть С — алфавит, полученный из алфавита С путем удаления сим- волов х и у и добавления нового символа z, так что С = С — {х,у} U {z}. По определению частоты / в алфавите С совпадают с частотами в алфавите С, за исключением частоты / [z] = f [x] + / [у]. Пусть Т" — произвольное дерево, представляющее оптимальный префиксный код для алфавита С Тогда дерево Г, полученное из дерева Т" путем замены листа z внутренним узлом с дочерними элементами х и у, представляет оптимальный префиксный код для алфавита С. Доказательство. Сначала покажем, что стоимость В (Г) дерева Г можно выра- зить через стоимость В (Т") дерева Т", рассматривая стоимости компонентов из уравнения A6.5). Для каждого символа се С — {х,у} выполняется соотношение 466 Часть IV. Усовершенствованные методы разработки и анализа Aт {с) = йт' (с), следовательно, /[с]Aт(с) = /[c]d^'(c). Поскольку dr (#) = = dr (у) = dr' B:) + 1, получаем соотношение / [х] dT (х) + f [у] dT (у) = (/ [х] + f {у}) {dT> (z) + 1) = из которого следует равенство B(T) = B(T')+f[x) ИЛИ B{T')=B(T)-f[x]-f[y]. Докажем лемму методом от противного. Предположим, дерево Т не представ- ляет оптимальный префиксный код для алфавита С Тогда существует дерево Т", для которого справедливо неравенство В(Т") < В{Т). Согласно лемме 16.2, х и у без потери общности можно считать дочерними элементами одного и того же узла. Пусть дерево Т"' получено из дерева Т" путем замены элементов х и у листом z с частотой / [z] = / [х] + f [у]. Тогда можно записать: B(T"')=B{T")-f[x}-f{y}<B(T)-f[x}-f[y} = B(T'), что противоречит предположению о том, что дерево Т' представляет оптимальный префиксный код для алфавита С. Таким образом, дерево Г должно представлять оптимальный префиксный код для алфавита С. ?

Теорема:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]