Изменения

'''Алгоритм Хаффмана''Алгоритм Хаффмана' (англ. ''Huffman's algorithm'' ) — алгоритм [[Задача_об_оптимальном_префиксном_коде_с_сохранением_порядка._Монотонность_точки_разреза | оптимального префиксного кодирования ]] алфавита. Был разработан в 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>2</tex>Wи добавим его к списку узлов: {| class=\"wikitable"! Узел || a || b || r || cd |-| Вес || 5 || 2 || 2 || 2|} Затем опять объединим в один узел два минимальных по весу узла {{4, 1, 1, 3\---}}<tex>r</tex> и <tex>cd</tex>:

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

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

По алгоритму возьмем два символа с наименьшей частотой {{---}} это ''м'' Еще раз повторим эту же операцию, но для узлов <tex>rcd</tex> и ''п''. Сформируем из них новый узел ''мп'' весом 2 и добавим его к списку узлов<tex>b</tex>:

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

| Вес || 4 6 || 2 || 35

Затем На последнем шаге объединим в один узел узлы ''мп'' два узла {{---}} <tex>brcd</tex> и ''c''<tex>a</tex>:

! Узел || и || мпс abrcd

| Вес || 4 || 5 11

ИОстался один узел, наконецзначит, объединяем два узла ''и'' и ''мпс''мы пришли к корню дерева Хаффмана (смотри рисунок). ИтакТеперь для каждого символа выберем кодовое слово (бинарная последовательность, мы получили дерево Хаффмана и соответствующую ему таблицу кодовобозначающая путь по дереву к этому символу от корня):

! Символ || и 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>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Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы://ruпостроение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с.wikipedia459.org/wiki/Алгоритм_Хаффмана Википедия — Алгоритм Хаффмана]ISBN 5-8489-0857-4

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