Изменения

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

Пусть <tex>A=\{a_{1},a_{2},...,a_{n}\}</tex> — алфавит из n различных символов, <tex>W=\{w_{1},w_{2},...,w_{n}\}</tex> — соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов <tex>C=\{c_{1},c_{2},...,c_{n}\}</tex>, где <tex>c_{i}</tex> является кодом для символа <tex>a_{i}</tex>, такой, что:

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

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

[[Файл:MississippiHuffman_abracadabra.pngjpg|400px|thumb|right|Дерево Хаффмана для слова ''строки "миссисипи<tex>abracadabra</tex>"'']]

Для примера возьмём Закодируем слово ''" миссисипи<tex>abracadabra</tex>"''. Тогда алфавит будет <tex>A= \{</tex> ''иa, b, мr, пc, с'' <tex>d\} </tex>, а набор весов (частота появления символов алфавита в кодируемой строке) <tex>W=\{45, 2, 2, 1, 1, 3\}</tex>: В дереве Хаффмана будет <tex>5</tex> узлов:

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

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

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

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

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

Затем опять объединим в один узел узлы ''мп'' два минимальных по весу узла: <tex>r</tex> и ''c''<tex>cd</tex>:

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

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

ИЕще раз повторим эту же операцию, наконец, объединяем два узла ''и'' и ''мпс''. Итак, мы получили дерево Хаффмана но для узлов <tex>rcd</tex> и соответствующую ему таблицу кодов<tex>b</tex>:

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

| Код Вес || 0 6 || 100 || 101 || 115

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