Изменения

Перейти к: навигация, поиск

Алгоритм Хаффмана

1772 байта добавлено, 15:14, 27 марта 2016
Нет описания правки
'''Алгоритм Хаффмана'''Алгоритм Хаффмана(англ. ''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>, такой, что:
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>),
называется '''кодом Хаффмана'''.
}}
== Алгоритм построения бинарного кода Хаффмана ==
Построение кода Хаффмана сводится к построению соответствующего [[ Двоичная_куча | бинарного дерева ]] по следующему алгоритму:
1. # Составим [[Список | список ]] кодируемых символов, при этом будем рассматривать один символ как дерево, состоящее из одного элемента, c весом, равным частоте появления символа в текстестроке.# Из списка выберем два узла с наименьшим весом.# Сформируем новый узел с весом, равным сумме весов выбранных узлов, и присоединим к нему два выбранных узла в качестве детей.# Добавим к списку только что сформированный узел вместо двух объединенных узлов.# Если в списке больше одного узла, то повторим пункты со второго по пятый.
2=== Время работы ===Если сортировать элементы после каждого суммирования или использовать [[Приоритетные_очереди | приоритетную очередь]], то алгоритм будет работать за время <tex>O(N \log N)</tex>. Из списка выберем два узла с наименьшим весомТакую асимптотику можно [[Алгоритм_Хаффмана_за_O(n) |улучшить до <tex>O(N)</tex>]], используя обычные массивы.
3. Сформируем новый узел с весом, равным сумме весов выбранных узлов, и присоединим к нему два выбранных узла в качестве дочерних.=== Пример ===
4. Добавим к списку только что сформированный узел[[Файл:Huffman_abracadabra.jpg|400px|thumb|right|Дерево Хаффмана для слова <tex>abracadabra</tex>]]
5Закодируем слово <tex>abracadabra</tex>. Если Тогда алфавит будет <tex>A= \{a, b, r, c, d\} </tex>, а набор весов (частота появления символов алфавита в списке больше одного узлакодируемом слове) <tex>W=\{5, 2, то повторить п.2---п.5., 1, 1\}</tex>:
== Пример ==В дереве Хаффмана будет <tex>5</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
|}
Следующим шагом будет построение дерева, где вершины - "символы", а пути до них соответствуют их префиксным кодам. Для этого на каждом шаге будем брать два символа с минимальной частотой вхожденияОстался один узел, и объединять их в новые так называемые символы с частотой равной сумме частот техзначит, которые мы объединяли, а также соединять их рёбрами, образуя таким образом деревопришли к корню дерева Хаффмана (см. смотри рисунок). Выбирать минимальные два Теперь для каждого символа будем из всех символов, исключая те, которые мы уже выбирали. В примере мы объединим символы b и с в символ bc с частотой 3. Далее объединим a и bc в символ abcвыберем кодовое слово (бинарная последовательность, получив тем самым дерево. Теперь пути обозначающая путь по дереву к этому символу от корня (abc) до листьев и есть Коды Хаффмана(каждому ребру соответствует либо 1 либо 0) :
{| 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>T</tex>, представляющее произвольный оптимальный префиксный код, и преобразовать для алфавита <tex>C</tex>. Преобразуем его в дерево, представляющее другой оптимальный префиксный код, в котором символы <tex>x</tex> и <tex>y</tex> являются листьями — листья с общим родительским узлом, причем в новом дереве эти листья находятся находящиеся на максимальной глубине.
Пусть символы <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[a] (c)d_T(c) - \sum\limits_{c \le in C} f(c)d_{T'}(c) = (f[ba]</tex> и <tex>- f[x] \le f[y])(d_T(a) - d_T(x)),</tex>.
Поскольку что больше либо равно <tex>f[x]0</tex> и <tex>f[y]</tex> — две самые маленькие частоты (в указанном порядке), так как величины <tex>f[a]</tex> и <tex>- f[bx]</tex> — две произвольные частоты, то выполняются соотношения и <tex>f[d_T(a) - d_T(x] \le f[a])</tex> и неотрицательны. Величина <tex>f[ya] \le - f[bx]</tex>. В результате перестановки в дереве неотрицательна, потому что <tex>Tx</tex> листьев — лист с минимальной частотой, а величина <tex>d_T(a) - d_T(x)</tex> и является неотрицательной, так как лист <tex>xa</tex> получается дерево находится на максимальной глубине в дереве <tex>T'</tex>, а при последующей перестановке в дереве V . Точно так же перестановка листьев <tex>by</tex> и <tex>yb</tex> получается дерево не будет приводить к увеличению стоимости. Таким образом, разность <tex>B(T') - B(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> неотрицательнадоказывает лемму.}}
Таким образом, выполняется неравенство <tex>B(T') \le B(T'')</tex>, и поскольку <tex>T</tex> — оптимальное дерево, то должно также выполняться неравенство <tex>B(T'') \le B(T')</tex>, откуда следует, что <tex>B(T') = B(T'')</tex>. Таким образом, <tex>T''</tex> — оптимальное дерево, в котором <tex>x</tex> и <tex>y</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] </tex> Докажем лемму от противного. Предположим, что дерево <tex>T</tex> не представляет оптимальный префиксный код для алфавита <tex>C</tex>. Тогда существует дерево <tex>T''</tex> такое, что <tex>B(T'') < B(T)</tex>. Согласно лемме (1), элементы <tex>x</tex> и <tex>y</tex> можно считать дочерними элементами одного узла. Пусть дерево <tex>T'''</tex> получено из дерева <tex>T''</tex> заменой элементов <tex>x</tex> и <tex>y</tex> листом <tex>z</tex> с частотой <tex>f[z] = f[x] + f[y]</tex>. Тогда
<tex> B(T''') = B(T'') - f[x] - f[y] < B(T) - f[x] - f[y] = B(T')</tex>.,
Докажем лемму методом от противного. Предположим, дерево <tex> T </tex> не представляет оптимальный префиксный код для алфавита <tex> C </tex>. Тогда существует дерево <tex> T'' </tex>, для которого справедливо неравенство <tex> B(T'') < B(T) </tex>. Согласно лемме (1), <tex>x</tex> и <tex>y</tex> без потери общности можно считать дочерними элементами одного и того же узла. Пусть дерево <tex>T'''</tex> получено из дерева <tex>T''</tex> путем замены элементов <tex>x</tex> и <tex>y</tex> листом <tex>z</tex> с частотой <tex>f[z] = f[x] + f[y] </tex>. Тогда можно записать:<br> <tex>B(T''') = B(T'') - f[x] - f[y] < B(T) - f[x] -f[y] = B(T')</tex>,<br> что противоречит предположению о том, что дерево <tex>T'</tex> представляет оптимальный префиксный код для алфавита <tex>C'</tex>. Таким образомЗначит, наше предположение о том, что дерево <tex>T</tex> должно представлять не представляет оптимальный префиксный код для алфавита <tex>C</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/Префиксный_код Википедия — Префиксный код] [[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы сжатия ]]
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/15376...52904»

Навигация