Изменения
Нет описания правки
'''Алгоритм Хаффмана'''Алгоритм Хаффмана(англ. ''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>, такой, что:
называется '''кодом Хаффмана'''.
}}
== Алгоритм построения бинарного кода Хаффмана ==
Построение кода Хаффмана сводится к построению соответствующего [[ Двоичная_куча | бинарного дерева ]] по следующему алгоритму:
{| class="wikitable"! Узел || a || b || r || с || d|-| Вес || 5 || 2 || 2 || 1 || 1|} По алгоритму возьмем два символа с наименьшей частотой {{---}} это <div styletex>c</tex> и <tex>d</tex>. Сформируем из них новый узел <tex>cd</tex> весом <tex>2</tex> и добавим его к списку узлов: {| class="float:right; margin:0;padding:0;wikitable"! Узел || a || b || r || cd |-| Вес || 5 || 2 || 2 || 2|} Затем опять объединим в один узел два минимальных по весу узла {{---}} <tex>r</tex> и <tex>cd</tex>: {| borderclass="0wikitable"! Узел | [[Файл:Huffman1.png|150pxa ||rightrcd |thumb|Обрабатываем b |-| Вес || 5 || 4 || 2 |} Еще раз повторим эту же операцию, но для узлов <tex>rcd</tex> и c]]<tex>b</tex>: {| class="wikitable"! Узел || brcd || a|-|[[Файл:Huffman2.pngВес |150px|right6 |thumb|Получившееся дерево]] 5
|}
На последнем шаге объединим два узла {{---}} <tex>brcd</divtex> и <tex>a</tex>В основу алгоритма Хаффмана положена идея: кодировать более коротко те символы, которые встречаются чаще, а те, которые встречаются реже кодировать длиннее. Для построения кода Хаффмана нам необходима таблица частот символов. Рассмотрим пример построения кода на простой строке '''''abacaba'''''
{| class="wikitable"
! a || b || c Узел ||abrcd
|-
| 4 || 2 || 1 Вес ||11
|}
{| class="wikitable"
! Символ || a || b || c r || с ||d
|-
| Код || 0 || 11 || 10 101 || 1000 ||1001
|}
Таким образом, закодированное слово <tex>abracadabra</tex> будет выглядеть как <tex>01110101000010010111010</tex>. Длина закодированного слова {{---}} <tex>23</tex> бита. Стоит заметить, что если бы мы использовали алгоритм кодирования с одинаковой длиной всех кодовых слов, то закодированное слово заняло бы <tex>33</tex> бита, что существенно больше.
== Корректность алгоритма Хаффмана ==
{{Лемма
Тогда для алфавита <tex>C</tex> существует оптимальный префиксный код, кодовые слова символов <tex>x</tex> и <tex>y</tex> в котором имеют одинаковую максимальную длину и отличаются лишь последним битом.
|proof=
Пусть символы <tex>a</tex> и <tex>b</tex> — два символа, представленные листьями с общим родительским узлом, которые имеют общий родительский узел и находятся на максимальной глубине дерева <tex>T</tex>.Предположим, что <tex>f[a] \leqslant f[b]</tex> и <tex>f[x] \leqslant f[y]</tex>. Так как <tex>f[x]</tex> и <tex>f[y]</tex> — две наименьшие частоты, а <tex>f[a]</tex> и <tex>f[b]</tex> — две произвольные частоты, то выполняются отношения <tex>f[x] \leqslant f[a]</tex> и <tex>f[y] \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_Tleqslant B(C) - \sum\limits_{c \in C} f(c)d_{T'}(C)= \\ \\=(f[a] - f[x])(d_T(a) - d_T(x)) \ge 0 ,</tex> поскольку величины . С другой стороны, <tex>f[a] - f[x]T</tex> и — оптимальное дерево, поэтому должно выполняться неравенство <tex>d_TB(aT) - d_T\leqslant B(xT'')</tex> неотрицательны. Величина <tex>f[a] - f[x]</tex> неотрицательнаОтсюда следует, потому что х — лист с минимальной частотой, величина <tex>d_TB(aT) - d_T= B(xT'')</tex> неотрицательна. Значит, потому что <tex>aT''</tex> — лист на максимальной глубине дерево, представляющее оптимальный префиксный код, в дереве котором символы <tex>Tx</tex>. Аналогично, перестановка листьев и <tex>y</tex> имеют одинаковую максимальную длину, что и <tex>b</tex> не приведет к увеличению стоимости, поэтому величина <tex>B(T') - B(T'')</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] < B(T) - f[x] - f[y] = B(T')</tex>.,
}}
}}
== Литература См. также ==*[[Оптимальное_хранение_словаря_в_алгоритме_Хаффмана | Оптимальное хранение словаря в алгоритме Хаффмана]] == Источники информации == * Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн . Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — Сс. 1296459. — 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/Префиксный_код Википедия — Префиксный код] [[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы сжатия ]]