Алгоритм Хаффмана
Алгоритм Хаффмана — алгоритм оптимального префиксного кодирования алфавита. Был разработан в 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. Используется во многих программах сжатия данных, например, PKZIP 2, LZH и др.
Содержание
Определение
| Определение: |
| Пусть — алфавит из n различных символов, — соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов , такой, что:
1. не является префиксом для , при 2. Сумма минимальна. ( — длина кода ) называется кодом Хаффмана. |
Алгоритм
Построение кода Хаффмана сводится к построению соответствующего бинарного дерева по следующему алгоритму:
1. Составим список кодируемых символов, при этом будем рассматривать один символ как дерево, состоящее из одного элемента, весом, равным частоте появления символа в тексте.
2. Из списка выберем два узла с наименьшим весом.
3. Сформируем новый узел с весом, равным сумме весов выбранных узлов, и присоединим к нему два выбранных узла в качестве дочерних.
4. Добавим к списку только что сформированный узел.
5. Если в списке больше одного узла, то повторить пункты со второго по пятый.
Время работы
Если сортировать элементы после каждого суммирования или использовать очередь с приоритетами, то алгоритм будет работать за время .Такую асимптотику можно улучшить до , используя обычные массивы.
Пример
Для примера возьмём слово "Миссисипи". Тогда алфавит будет и, м, п, с , а набор весов :
| Узел | и | м | п | с |
|---|---|---|---|---|
| Вес | 4 | 1 | 1 | 3 |
По алгоритму возьмем два символа с наименьшей частотой — это м и п. Сформируем из них новый узел мп весом 2 и добавим его к списку узлов:
| Узел | и | мп | с |
|---|---|---|---|
| Вес | 4 | 2 | 3 |
Затем объединим в один узел узлы мп и c:
| Узел | и | мпс |
|---|---|---|
| Вес | 4 | 5 |
И, наконец, объединяем два узла и и мпс. Итак, мы получили дерево Хаффмана и соответствующую ему таблицу кодов:
| Символ | и | м | п | с |
|---|---|---|---|---|
| Код | 0 | 100 | 101 | 11 |
Таким образом, закодированное слово "миссисипи" будет выглядеть как "1000111101101010". Длина закодированного слова — 16 бит. Стоит заметить, что если бы мы использовали для кодирования каждого символа из четырёх по 2 бита, длина закодированного слова составила бы 18 бит.
Корректность алгоритма Хаффмана
Чтобы доказать корректность алгоритма Хаффмана, покажем, что в задаче о построении оптимального префиксного кода проявляются свойства жадного выбора и оптимальной подструктуры. В сформулированной ниже лемме показано соблюдение свойства жадного выбора.
| Лемма (1): |
Пусть — алфавит, каждый символ которого встречается с частотой . Пусть и — два символа алфавита с самыми низкими частотами.
Тогда для алфавита существует оптимальный префиксный код, кодовые слова символов и в котором имеют одинаковую максимальную длину и отличаются лишь последним битом. |
| Доказательство: |
|
Возьмем дерево , представляющее произвольный оптимальный префиксный код для алфавита . Преобразуем его в дерево, представляющее другой оптимальный префиксный код, в котором символы и — листья с общим родительским узлом, находящиеся на максимальной глубине. Пусть символы и имеют общий родительский узел и находятся на максимальной глубине дерева . Предположим, что и . Так как и — две наименьшие частоты, а и — две произвольные частоты, то выполняются отношения и . Пусть дерево — дерево, полученное из путем перестановки листьев и , а дерево — дерево полученное из перестановкой листьев и . Разность стоимостей деревьев и равна:
что больше либо равно , так как величины и неотрицательны. Величина неотрицательна, потому что — лист с минимальной частотой, а величина является неотрицательной, так как лист находится на максимальной глубине в дереве . Точно так же перестановка листьев и не будет приводить к увеличению стоимости. Таким образом, разность тоже будет неотрицательной. Таким образом, выполняется неравенство . С другой стороны, — оптимальное дерево, поэтому должно выполняться неравенство . Отсюда следует, что . Значит, — дерево, представляющее оптимальный префиксный код, в котором символы и имеют одинаковую максимальную длину, что и доказывает лемму. |
| Лемма (2): |
Пусть дан алфавит , в котором для каждого символа определены частоты . Пусть и — два символа из алфавита с минимальными частотами. Пусть — алфавит, полученный из алфавита путем удаления символов и и добавления нового символа , так что . По определению частоты в алфавите совпадают с частотами в алфавите , за исключением частоты . Пусть — произвольное дерево, представляющее оптимальный префиксный код для алфавита Тогда дерево , полученное из дерева путем замены листа внутренним узлом с дочерними элементами и , представляет оптимальный префиксный код для алфавита . |
| Доказательство: |
|
Сначала покажем, что стоимость дерева может быть выражена через стоимость дерева . Для каждого символа верно , значит, . Так как , то
из чего следует, что
или
Докажем лемму от противного. Предположим, что дерево не представляет оптимальный префиксный код для алфавита . Тогда существует дерево такое, что . Согласно лемме (1), элементы и можно считать дочерними элементами одного узла. Пусть дерево получено из дерева заменой элементов и листом с частотой . Тогда , что противоречит предположению о том, что дерево представляет оптимальный префиксный код для алфавита . Значит, наше предположение о том, что дерево не представляет оптимальный префиксный код для алфавита , неверно, что и доказывает лемму. |
| Теорема: |
Алгоритм Хаффмана дает оптимальный префиксный код. |
| Доказательство: |
| Справедливость теоремы непосредственно следует из лемм (1) и (2) |
Литература
- Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4
