Изменения
Нет описания правки
'''Алгоритм Хаффмана''Алгоритм Хаффмана' (англ. ''Huffman's algorithm'' ) — алгоритм [[Задача_об_оптимальном_префиксном_коде_с_сохранением_порядка._Монотонность_точки_разреза | оптимального префиксного кодирования ]] алфавита. Был разработан в 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>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
|id=th1
|statement=
Алгоритм Хаффмана дает [[Задача_об_оптимальном_префиксном_коде_с_сохранением_порядка._Монотонность_точки_разреза | оптимальный префиксный код]].
|proof=
Справедливость теоремы непосредственно следует из лемм (1) и (2)
}}
== Литература См. также ==* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 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/Префиксный_код Википедия — Префиксный код]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы сжатия ]]