Изменения

'''Алгоритм Хаффмана'''Алгоритм Хаффмана(англ. ''Huffman's algorithm'' ) — алгоритм [[Задача_об_оптимальном_префиксном_коде_с_сохранением_порядка._Монотонность_точки_разреза | оптимального префиксного кодирования ]] алфавита. Это один из классических алгоритмов, известных с 60-х годов. Использует только частоту появления одинаковых байт Был разработан в изображении1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. Сопоставляет символам входного потока, которые встречаются большее число разИспользуется во многих программах сжатия данных, цепочку бит меньшей длины. Инапример, напротивPKZIP 2, встречающимся редко — цепочку большей длиныLZH и др.

Пусть <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>, такой, что:

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>),

Построение == Алгоритм построения бинарного кода Хаффмана сводится к построению соответствующего бинарного дерева по следующему алгоритму:==

2# Составим [[Список | список]] кодируемых символов, при этом будем рассматривать один символ как дерево, состоящее из одного элемента c весом, равным частоте появления символа в строке. # Из списка выберем два узла с наименьшим весом.# Сформируем новый узел с весом, равным сумме весов выбранных узлов, и присоединим к нему два выбранных узла в качестве детей.# Добавим к списку только что сформированный узел вместо двух объединенных узлов.# Если в списке больше одного узла, то повторим пункты со второго по пятый.

3=== Время работы ===Если сортировать элементы после каждого суммирования или использовать [[Приоритетные_очереди | приоритетную очередь]], то алгоритм будет работать за время <tex>O(N \log N)</tex>. Сформируем новый узел с весом, равным сумме весов выбранных узловТакую асимптотику можно [[Алгоритм_Хаффмана_за_O(n) |улучшить до <tex>O(N)</tex>]], и присоединим к нему два выбранных узла в качестве дочернихиспользуя обычные массивы.

5. Если в списке больше одного узла, то повторить пункты со второго по пятый[[Файл:Huffman_abracadabra.jpg|400px|thumb|right|Дерево Хаффмана для слова <tex>abracadabra</tex>]]

Закодируем слово <tex>abracadabra</tex>. Тогда алфавит будет <tex>A=\{a, b, r, c, d\} </tex>, а набор весов (частота появления символов алфавита в кодируемом слове) <tex>W= Пример ==\{5, 2, 2, 1, 1\}</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>W=\{4, 1, 1, 3\}2</tex>и добавим его к списку узлов:

! Узел || и a || м b || п r || сcd

| Вес || 4 5 || 1 2 || 1 2 || 32

По алгоритму возьмем Затем опять объединим в один узел два символа с наименьшей частотой минимальных по весу узла {{---}} это ''м'' и ''п''. Сформируем из них новый узел ''мп'' весом 2 <tex>r</tex> и добавим его к списку узлов<tex>cd</tex>:

! Узел || и a || мп rcd || с b

| Вес || 5 || 4 || 2 || 3

Затем объединим в один узел узлы ''мп'' Еще раз повторим эту же операцию, но для узлов <tex>rcd</tex> и ''c''<tex>b</tex>:

! Узел || и brcd || мпс a

| Вес || 4 6 || 5

И, наконец, объединяем На последнем шаге объединим два узла ''{{---}} <tex>brcd</tex> и'' и ''мпс''. Итак, мы получили дерево Хаффмана и соответствующую ему таблицу кодов<tex>a</tex>:

! Символ Узел || и || м || п || сabrcd

| Код || 0 || 100 || 101 Вес || 11

Остался один узел, значит, мы пришли к корню дерева Хаффмана (смотри рисунок). Теперь для каждого символа выберем кодовое слово (бинарная последовательность, обозначающая путь по дереву к этому символу от корня): {| class="wikitable"! Символ || a || b || r || с || d|-| Код || 0 || 11 || 101 || 1000 || 1001|} Таким образом, закодированное слово ''"миссисипи"'' <tex>abracadabra</tex> будет выглядеть как ''"1000111101101010"''<tex>01110101000010010111010</tex>. Длина закодированного слова {{---}} 16 бит<tex>23</tex> бита. Стоит заметить, что если бы мы использовали для алгоритм кодирования каждого символа из четырёх по 2 с одинаковой длиной всех кодовых слов, то закодированное слово заняло бы <tex>33</tex> бита, длина закодированного слова составила бы 18 битчто существенно больше.

Чтобы доказать корректность алгоритма Хаффмана, покажем, что в задаче о построении оптимального префиксного кода проявляются свойства жадного выбора и оптимальной подструктуры. В сформулированной ниже лемме показано соблюдение свойства жадного выбора.

Пусть символы <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'') \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> имеют одинаковую максимальную длину, что и доказывает лемму.

== Литература См. также ==*[[Оптимальное_хранение_словаря_в_алгоритме_Хаффмана | Оптимальное хранение словаря в алгоритме Хаффмана]] == Источники информации == * Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн . Алгоритмы: построение и анализ — 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/Префиксный_код Википедия — Префиксный код]

[[Категория: Хеширование Алгоритмы сжатия]]