1632
правки
Изменения
м
1. :* <tex>c_{i}</tex> не является префиксом для <tex>c_{j}</tex>, при <tex>i \ne j</tex>,
2. Сумма :* cумма <tex>\sum\limits_{i \in [1, n]} w_{i}\cdot |c_{i}|</tex> минимальна. (<tex>|c_{i}|</tex> — длина кода <tex>c_{i}</tex>),
== Алгоритм ==
Построение == Алгоритм построения бинарного кода Хаффмана сводится к построению соответствующего бинарного дерева по следующему алгоритму:==
1. Составим список кодируемых символов, при этом будем рассматривать один символ как дерево, состоящее из одного элемента, весом, равным частоте появления символа в тексте.Построение кода Хаффмана сводится к построению соответствующего [[ Двоичная_куча | бинарного дерева]] по следующему алгоритму:
2# Составим [[Список | список]] кодируемых символов, при этом будем рассматривать один символ как дерево, состоящее из одного элемента c весом, равным частоте появления символа в строке. # Из списка выберем два узла с наименьшим весом.# Сформируем новый узел с весом, равным сумме весов выбранных узлов, и присоединим к нему два выбранных узла в качестве детей.# Добавим к списку только что сформированный узел вместо двух объединенных узлов.# Если в списке больше одного узла, то повторим пункты со второго по пятый.
3=== Время работы ===Если сортировать элементы после каждого суммирования или использовать [[Приоритетные_очереди | приоритетную очередь]], то алгоритм будет работать за время <tex>O(N \log N)</tex>. Сформируем новый узел с весом, равным сумме весов выбранных узловТакую асимптотику можно [[Алгоритм_Хаффмана_за_O(n) |улучшить до <tex>O(N)</tex>]], и присоединим к нему два выбранных узла в качестве дочернихиспользуя обычные массивы.
4. Добавим к списку только что сформированный узел.=== Пример ===
5. Если в списке больше одного узла, то повторить пункты со второго по пятый[[Файл:Huffman_abracadabra.jpg|400px|thumb|right|Дерево Хаффмана для слова <tex>abracadabra</tex>]]
[[ФайлВ дереве Хаффмана будет <tex>5</tex> узлов:Mississippi.png|400px|thumb|right|Дерево Хаффмана для слова ''"Миссисипи"'']]
Для примера возьмём слово ''{| class="Миссисипиwikitable"''. Тогда алфавит будет ! Узел || a || b || r || с || d|-| Вес || 5 || 2 || 2 || 1 || 1|} По алгоритму возьмем два символа с наименьшей частотой {{---}} это <tex>A= \{c</tex> ''и, м, п, с'' <tex>\} d</tex>. Сформируем из них новый узел <tex>cd</tex>, а набор весов весом <tex>2</tex>Wи добавим его к списку узлов: {| class=\"wikitable"! Узел || a || b || r || cd |-| Вес || 5 || 2 || 2 || 2|} Затем опять объединим в один узел два минимальных по весу узла {{4, 1, 1, 3\---}}<tex>r</tex> и <tex>cd</tex>:
По алгоритму возьмем два символа с наименьшей частотой - это ''м'' Еще раз повторим эту же операцию, но для узлов <tex>rcd</tex> и ''п''. Сформируем из них новый узел ''мп'' весом 2 и добавим его к списку узлов<tex>b</tex>:
Затем На последнем шаге объединим в один узел узлы ''мп'' два узла {{---}} <tex>brcd</tex> и ''c''<tex>a</tex>:
ИОстался один узел, наконецзначит, объединяем два узла ''и'' и ''мпс''мы пришли к корню дерева Хаффмана (смотри рисунок). ИтакТеперь для каждого символа выберем кодовое слово (бинарная последовательность, мы получили дерево Хаффмана и соответствующую ему таблицу кодовобозначающая путь по дереву к этому символу от корня):
Чтобы доказать корректность алгоритма Хаффмана, покажем, что в задаче о построении оптимального префиксного кода проявляются свойства жадного выбора и оптимальной подструктуры. В сформулированной ниже лемме показано соблюдение свойства жадного выбора.
rollbackEdits.php mass rollback
'''Алгоритм Хаффмана'''Алгоритм Хаффмана(англ. ''Huffman's algorithm'' ) — алгоритм [[Задача_об_оптимальном_префиксном_коде_с_сохранением_порядка._Монотонность_точки_разреза | оптимального префиксного кодирования ]] алфавита. Это один из классических алгоритмов, известных с 60-х годов. Использует только частоту появления одинаковых байт Был разработан в изображении1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. Сопоставляет символам входного потока, которые встречаются большее число разИспользуется во многих программах сжатия данных, цепочку бит меньшей длины. Инапример, напротивPKZIP 2, встречающимся редко — цепочку большей длиныLZH и др.
== Определение ==
{{Определение
|definition=
Пусть <tex>A=\{a_{1},a_{2},...\ldots ,a_{n}\}</tex> — алфавит из <tex>n </tex> различных символов, <tex>W=\{w_{1},w_{2},...\ldots ,w_{n}\}</tex> — соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов <tex>C=\{c_{1},c_{2},...\ldots ,c_{n}\}</tex>, где <tex>c_{i}</tex> является кодом для символа <tex>a_{i}</tex>, такой, что:
называется '''кодом Хаффмана'''.
}}
Закодируем слово <tex>abracadabra</tex>. Тогда алфавит будет <tex>A=\{a, b, r, c, d\} </tex>, а набор весов (частота появления символов алфавита в кодируемом слове) <tex>W= Пример ==\{5, 2, 2, 1, 1\}</tex>:
{| class="wikitable"
! Узел || и a || м rcd || п || сb
|-
| Вес || 4 5 || 1 || 1 4 || 32
|}
{| class="wikitable"
! Узел || и brcd || мп || с a
|-
| Вес || 4 6 || 2 || 35
|}
{| class="wikitable"
! Узел || и || мпс abrcd
|-
| Вес || 4 || 5 11
|}
{| class="wikitable"
! Символ || и a || м b || п r || с|| d
|-
| Код || 0 || 100 11 || 101 || 111000 || 1001
|}
Таким образом, закодированное слово ''"миссисипи"'' <tex>abracadabra</tex> будет выглядеть как ''"1000111101101010"''<tex>01110101000010010111010</tex>. Длина закодированного слова {{- 16 бит--}} <tex>23</tex> бита. Стоит заметить, что если бы мы использовали для алгоритм кодирования каждого символа из четырёх по 2 с одинаковой длиной всех кодовых слов, то закодированное слово заняло бы <tex>33</tex> бита, длина закодированного слова составила бы 18 битчто существенно больше.
== Корректность алгоритма Хаффмана ==
{{Лемма
Тогда для алфавита <tex>C</tex> существует оптимальный префиксный код, кодовые слова символов <tex>x</tex> и <tex>y</tex> в котором имеют одинаковую максимальную длину и отличаются лишь последним битом.
|proof=
Возьмем дерево <tex>T</tex>, представляющее произвольный оптимальный префиксный код для алфавита <tex>C</tex>. Преобразуем его в дерево, представляющее другой оптимальный префиксный код, в котором символы <tex>x</tex> и <tex>y</tex> - — листья с общим родительским узлом, находящиеся на максимальной глубине.
Пусть символы <tex>a</tex> и <tex>b</tex> имеют общий родительский узел и находятся на максимальной глубине дерева <tex>T</tex>. Предположим, что <tex>f[a] \le leqslant f[b]</tex> и <tex>f[x] \le leqslant f[y]</tex>. Так как <tex>f[x]</tex> и <tex>f[y]</tex> - — две наименьшие частоты, а <tex>f[a]</tex> и <tex>f[b]</tex> - — две произвольные частоты, то выполняются отношения <tex>f[x] \le leqslant f[a]</tex> и <tex>f[y] \le leqslant f[b]</tex>. Пусть дерево <tex>T'</tex> - — дерево, полученное из <tex>T</tex> путем перестановки листьев <tex>a</tex> и <tex>x</tex>, а дерево <tex>T''</tex> - — дерево полученное из <tex>T'</tex> перестановкой листьев <tex>b</tex> и <tex>y</tex>. Разность стоимостей деревьев <tex>T</tex> и <tex>T'</tex> равна:
<tex>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)),</tex>
что больше либо равно <tex>0</tex>, так как величины <tex>f[a] - f[x]</tex> и <tex>d_T(a) - d_T(x)</tex> неотрицательны. Величина <tex>f[a] - f[x]</tex> неотрицательна, потому что <tex>x</tex> - — лист с минимальной частотой, а величина <tex>d_T(a) - d_T(x)</tex> является неотрицательной, так как лист <tex>a</tex> находится на максимальной глубине в дереве <tex>T</tex>. Точно так же перестановка листьев <tex>y</tex> и <tex>b</tex> не будет приводить к увеличению стоимости. Таким образом, разность <tex>B(T') - B(T'')</tex> тоже будет неотрицательной.
Таким образом, выполняется неравенство <tex>B(T'') \le leqslant B(T)</tex>. С другой стороны, <tex>T</tex> - — оптимальное дерево, поэтому должно выполняться неравенство <tex>B(T) \le leqslant B(T'')</tex>. Отсюда следует, что <tex>B(T) = B(T'')</tex>. Значит, <tex>T''</tex> - — дерево, представляющее оптимальный префиксный код, в котором символы <tex>x</tex> и <tex>y</tex> имеют одинаковую максимальную длину, что и доказывает лемму.
}}
{{Лемма
|id=lemma2
|about=2
|statement=Пусть дан алфавит <tex>C</tex>, в котором для каждого символа <tex>c \in C</tex> определены частоты <tex>f[c]</tex>. Пусть <tex>x</tex> и <tex>y</tex> — два символа из алфавита <tex>C</tex> с минимальными частотами. Пусть <tex>C'</tex> — алфавит, полученный из алфавита <tex>C</tex> путем удаления символов <tex>x</tex> и <tex>y</tex> и добавления нового символа <tex>z</tex>, так что <tex>C' = C \backslash \{ x, y \} \cup {z}</tex>. По определению частоты <tex>f</tex> в алфавите <tex>C'</tex> совпадают с частотами в алфавите <tex>C</tex>, за исключением частоты <tex>f[z] = f[x] + f[y]</tex>. Пусть <tex>T'</tex> — произвольное дерево, представляющее оптимальный префиксный код для алфавита <tex>C'</tex> Тогда дерево <tex>T</tex>, полученное из дерева <tex>T'</tex> путем замены листа <tex>z</tex> внутренним узлом с дочерними элементами <tex>x</tex> и <tex>y</tex>, представляет оптимальный префиксный код для алфавита <tex>C</tex>.
|proof=Сначала покажем, что стоимость <tex>B(T)</tex> дерева <tex>T</tex> можно выразить может быть выражена через стоимость <tex>B(T')</tex> дерева <tex>T'</tex>. Для каждого символа <tex>c \le in C \backslash \{x,y\}</tex> выполняется соотношение верно <tex>d_T(C) = d_{T'}(c)</tex>, следовательнозначит, <tex>f[c]d_T(Cc) = f[c]d_{T'}(c)</tex>. Поскольку Так как <tex>d_T(x) = d_{T}d_T(y) = d_{tT'}(z) + 1</tex>, получаем соотношение<br>то <tex>f[x]d_T(x) + f[y]d_{T}d_T(y) = (f[x] + f[y])(d_{T'}(z) + 1) = f[z]d_{T'}(z) + (f[x] + f[y])</tex><br>из которого чего следует равенство <br>, что
<tex> B(T) = B(T') + f[x] + f[y] </tex>
или
<tex> B(T') = B(T) - f[x] - f[y] </tex>.
Докажем лемму методом от противного. Предположим, что дерево <tex> T </tex> не представляет оптимальный префиксный код для алфавита <tex> C </tex>. Тогда существует дерево <tex> T'' </tex>такое, для которого справедливо неравенство что <tex> B(T'') < B(T) </tex>. Согласно лемме (1), элементы <tex>x</tex> и <tex>y</tex> без потери общности можно считать дочерними элементами одного и того же узла. Пусть дерево <tex>T'''</tex> получено из дерева <tex>T''</tex> путем замены заменой элементов <tex>x</tex> и <tex>y</tex> листом <tex>z</tex> с частотой <tex>f[z] = f[x] + f[y] </tex>. Тогда можно записать:<br> <tex>B(T''') = B(T'') - f[x] - f[y] < B(T) - f[x] -f[y] = B(T')</tex>,<br> что противоречит предположению о том, что дерево <tex>T'</tex> представляет оптимальный префиксный код для алфавита <tex>C'</tex>. Таким образомЗначит, наше предположение о том, что дерево <tex>T</tex> должно представлять не представляет оптимальный префиксный код для алфавита <tex>C</tex>, неверно, что и доказывает лемму.
}}
}}
== Литература См. также ==*[[Оптимальное_хранение_словаря_в_алгоритме_Хаффмана | Оптимальное хранение словаря в алгоритме Хаффмана]] == Источники информации == * Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн . Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4*[http://en.wikipedia.org/wiki/Huffman_coding Wikipedia — Huffman coding]*[http://ru.wikipedia.org/wiki/%C4%E2%EE%E8%F7%ED%EE%E5_%E4%E5%F0%E5%E2%EE Википедия — Бинарное дерево]*[http://ru.wikipedia.org/wiki/Префиксный_код Википедия — Префиксный код]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы сжатия ]]
