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

Определение

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

Коды или Алгоритм Хаффмана (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])

1. [math]n \gets |C|[/math]
   
2. [math]Q \gets C[/math]
   
3. for [math]i \gets 1[/math] to [math]n - 1[/math]
   

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

1. left[z] «- х <- Extract_Min(Q)
   
2. right[z] <- у <- ExtractJMin(Q)
   
3. Insert(Q, z)
   
4. return Extract_Min(Q) > Возврат корня дерева
   

Для рассмотренного ранее примера алгоритм Хаффмана выводит результат, при- веденный на рис. 16.4. На каждом этапе показано содержимое очереди, элементы которой рассортированы в порядке возрастания их частот. На каждом шаге рабо- ты алгоритма объединяются два объекта (дерева) с самыми низкими частотами. Листья изображены в виде прямоугольников, в каждом из которых указана буква и соответствующая ей частота. Внутренние узлы представлены кругами* содер- жащими сумму частот дочерних узлов. Ребро, соединяющее внутренний узел с левым дочерним узлом, имеет метку 0, а ребро, соединяющее его с правым до- черним узлом, — метку 1. Слово кода для буквы образуется последовательностью меток на ребрах, соединяющих корень с листом, представляющим эту букву. По- Глава 16. Жадные алгоритмы 463 a) if-л] [^) I \у:\2\ <> П| |d IM |.,.4S| 6) Ki2) ЬИ в) ® ШЕ ® ШШ о/ \i о/ 1Ж11Ж1 о/ \> t 5 р ч л) ЕВЕ (inn) о ч \ I f7i2i |b 13 f) i Рис. 16.4. Этапы работы алгоритма Хаффмана для частот, заданных в табл. 16.1 сколысу данное множество содержит шесть букв, размер исходной очереди равен 6 (часть а рисунка), а для построения дерева требуется пять слияний. Промежуточ- ные этапы изображены в частях б-д. Конечное дерево (рис. 16.4е) представляет оптимальный префиксный код. Как уже говорилось, слово кода для буквы — это последовательность меток на пути от корня к листу с этой буквой. В строке 2 инициализируется очередь с приоритетами Q, состоящая из эле- ментов множества С. Цикл for в строках 3-8 поочередно извлекает по два узла, х и у, которые характеризуются в очереди наименьшими частотами, и заменяет их в очереди новым узлом z, представляющим объединение упомянутых выше элементов. Частота появления z вычисляется в строке 7 как сумма частот х и у. Узел х является левым дочерним узлом z, а у — его правым дочерним узлом. (Этот порядок является произвольным; перестановка левого и правого дочерних узлов приводит к созданию другого кода с той же стоимостью.) После п — 1 объедине- ний в очереди остается один узел — корень дерева кодов, который возвращается в строке 9. При анализе времени работы алгоритма Хаффмана предполагается, что Q реа- лизована как бинарная неубывающая пирамида (см. главу 6). Для множества С, со- стоящего из п символов, инициализацию очереди Q в строке 2 можно выполнить 464 Часть IV. Усовершенствованные методы разработки и анализа за время О (п) с помощью процедуры Build_Min_Heap из раздела 6.3. Цикл for в строках 3-8 выполняется ровно и — 1 раз, и поскольку для каждой операции над пирамидой требуется время О (lgn), вклад цикла во время работы алгорит- ма равен O(nlgn). Таким образом, полное время работы процедуры Huffman с входным множеством, состоящим из п символов, равно О (nlgn). Корректность алгоритма Хаффмана Чтобы доказать корректность жадного алгоритма Huffman, покажем, что в за- даче о построении оптимального префиксного кода проявляются свойства жадного выбора и оптимальной подструктуры. В сформулированной ниже лемме показано соблюдение свойства жадного выбора. Лемма 16.2. Пусть С — алфавит, каждый символ с€С которого встречается с ча- стотой / [с]. Пусть х и у — два символа алфавита С с самыми низкими частотами. Тогда для алфавита С существует оптимальный префиксный код, кодовые слова символов х и у в котором имеют одинаковую длину и отличаются лишь последним битом. Доказательство. Идея доказательства состоит в том, чтобы взять дерево Т, пред- ставляющее произвольный оптимальный префиксный код, и преобразовать его в дерево, представляющее другой оптимальный префиксный код, в котором сим- волы х и у являются листьями с общим родительским узлом, причем в новом дереве эти листья находятся на максимальной глубине. Пусть а и b — два символа, представленные листьями с общим родительским узлом, которые находятся на максимальной глубине дерева Т. Предположим без потери общности, что / [а] ^ / [Ь] и / [х] ^ / [у]. Поскольку / [х] и / [у] — две самые маленькие частоты (в указанном порядке), а / [а] и / [6] — две произвольные частоты, то выполняются соотношения f[x]^f [а] и / [у] ^ / [6]. Как показано на рис. 16.5, в результате перестановки в дереве Т листьев а и х получается дерево Т", а при последующей перестановке в дереве V листьев Ь и у получается дерево Т". Согласно уравнению A6.5), разность стоимостей деревьев Т и Т" равна В(Т)-В (Г') = ?/(c)dr (с) - ?/(c)(fev (с) = сес сес

/ [х] 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'), что противоречит предположению о том, что дерево Т' представляет оптимальный префиксный код для алфавита С. Таким образом, дерево Г должно представлять оптимальный префиксный код для алфавита С. ? Теорема 16.4. Процедура Huffman дает оптимальный префиксный код. Доказательство. Справедливость теоремы непосредственно следует из лемм 16.2 и 16.3.