Изменения

Для примера возьмём слово ''"Миссисипи"''== Определение == {{Определение |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>AC= \{c_{1},c_{2}, \ldots ,c_{n}\}</tex>, где <tex>c_{i}</tex> является кодом для символа <tex>a_{i}</tex>, такой, что: :* <tex>c_{i}</tex> не является префиксом для <tex>c_{j}</tex> , при <tex>i \ne j</tex>, :* cумма <tex>\sum\limits_{i \in [1, n]} w_{i}\cdot |c_{i}|</tex> минимальна (<tex>|c_{i}|</tex> — длина кода <tex>c_{i}</tex>), называется '''кодом Хаффмана'''.}} == Алгоритм построения бинарного кода Хаффмана == Построение кода Хаффмана сводится к построению соответствующего [[ Двоичная_куча | бинарного дерева]] по следующему алгоритму: # Составим [[Список | список]] кодируемых символов, при этом будем рассматривать один символ как дерево, состоящее из одного элемента c весом, равным частоте появления символа в строке.# Из списка выберем два узла с наименьшим весом.# Сформируем новый узел с весом, равным сумме весов выбранных узлов, иприсоединим к нему два выбранных узла в качестве детей.# Добавим к списку только что сформированный узел вместо двух объединенных узлов.# Если в списке больше одного узла, мто повторим пункты со второго по пятый. === Время работы ===Если сортировать элементы после каждого суммирования или использовать [[Приоритетные_очереди | приоритетную очередь]], пто алгоритм будет работать за время <tex>O(N \log N)</tex>.Такую асимптотику можно [[Алгоритм_Хаффмана_за_O(n) |улучшить до <tex>O(N)</tex>]], с'' используя обычные массивы. === Пример === [[Файл:Huffman_abracadabra.jpg|400px|thumb|right|Дерево Хаффмана для слова <tex>abracadabra</tex>]] Закодируем слово <tex>abracadabra</tex>. Тогда алфавит будет <tex>A= \{a, b, r, c, 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>:

Соответствующая ему таблица кодовНа последнем шаге объединим два узла {{---}} <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> бита. Стоит заметить, что если бы мы использовали алгоритм кодирования с одинаковой длиной всех кодовых слов, то закодированное слово заняло бы <tex>33</tex> бита, что существенно больше. == Корректность алгоритма Хаффмана == Чтобы доказать корректность алгоритма Хаффмана, покажем, что в задаче о построении оптимального префиксного кода проявляются свойства жадного выбора и оптимальной подструктуры. В сформулированной ниже лемме показано соблюдение свойства жадного выбора. {{Лемма|id=lemma1|about=1|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>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(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'') \leqslant B(T)</tex>. С другой стороны, <tex>T</tex> — оптимальное дерево, поэтому должно выполняться неравенство <tex>B(T) \leqslant 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 \in C \backslash \{x, y \}</tex> верно <tex>d_T(C) = d_{T'}</tex>, значит, <tex>f[c]d_T(c) = f[c]d_{T'}(c)</tex>. Так как <tex>d_T(x) = d_T(y) = d_{T'} (z) + 1</tex>, то <tex>f[x]d_T(x) + f[y]d_T(y) = (f[x] + f[y])(d_{T'}(z) + 1) = f[z]d_{T'}(z) + (f[x] + f[y])</tex> из чего следует, что <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>C</tex>, неверно, что и доказывает лемму.}} {{Теорема|id=th1|statement=Алгоритм Хаффмана дает оптимальный префиксный код. |proof=Справедливость теоремы непосредственно следует из лемм (1) и (2)}} == См. также ==*[[Оптимальное_хранение_словаря_в_алгоритме_Хаффмана | Оптимальное хранение словаря в алгоритме Хаффмана]] == Источники информации == * Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ — 2 бита-е изд. — М.: «Вильямс», длина закодированного слова составила бы 18 бит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/Префиксный_код Википедия — Префиксный код] [[Категория: Дискретная математика и алгоритмы]] [[Категория:Алгоритмы сжатия]]