|
|
| Строка 1: |
Строка 1: |
| − | '''''Алгоритм Хаффмана''''' — алгоритм оптимального префиксного кодирования алфавита. Это один из классических алгоритмов, известных с 60-х годов. Использует только частоту появления одинаковых байт в изображении. Сопоставляет символам входного потока, которые встречаются большее число раз, цепочку бит меньшей длины. И, напротив, встречающимся редко — цепочку большей длины.
| |
| − |
| |
| − | == Определение ==
| |
| − |
| |
| − | {{Определение
| |
| − | |definition=
| |
| − | Пусть <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>, такой, что:
| |
| − |
| |
| − | 1.<tex>c_{i}</tex> не является префиксом для <tex>c_{j}</tex>, при <tex>i != j</tex>
| |
| − |
| |
| − | 2.<tex>\sum\limits_{i \in [1, n]} w_{i}\cdot c_{i}</tex> минимальна. (<tex>|c_{i}|</tex> - длина кода <tex>c_{i}</tex>)
| |
| − |
| |
| − | называется '''кодом Хаффмана'''.
| |
| − | }}
| |
| − |
| |
| − | == Алгоритм ==
| |
| − |
| |
| − | Построение кода Хаффмана сводится к построению соответствующего бинарного дерева по следующему алгоритму:
| |
| − |
| |
| − | 1. Составим список кодируемых символов, при этом будем рассматривать один символ как дерево, состоящее из одного элемента, весом, равным частоте появления символа в тексте.
| |
| − |
| |
| − | 2. Из списка выберем два узла с наименьшим весом.
| |
| − |
| |
| − | 3. Сформируем новый узел с весом, равным сумме весов выбранных узлов, и присоединим к нему два выбранных узла в качестве дочерних.
| |
| − |
| |
| − | 4. Добавим к списку только что сформированный узел.
| |
| − |
| |
| − | 5. Если в списке больше одного узла, то повторить п.2-п.5.
| |
| − |
| |
| | == Пример == | | == Пример == |
| | | | |
| − | <div style="float:right; margin:0;padding:0;">
| + | Для примера возьмём слово ''"Миссисипи"''. Тогда алфавит будет <tex>A= \{</tex> ''и, м, п, с'' <tex>\} </tex>, а набор весов <tex>W=\{4, 1, 1, 3\}</tex>: |
| − | {| border="0" | |
| − | | [[Файл:Huffman1.png|150px|right|thumb|Обрабатываем b и c]]||[[Файл:Huffman2.png|150px|right|thumb|Получившееся дерево]]
| |
| − | |}
| |
| − | </div> | |
| − | В основу алгоритма Хаффмана положена идея: кодировать более коротко те символы, которые встречаются чаще, а те, которые встречаются реже кодировать длиннее. Для построения кода Хаффмана нам необходима таблица частот символов. Рассмотрим пример построения кода на простой строке '''''abacaba'''''
| |
| | | | |
| | {| class="wikitable" | | {| class="wikitable" |
| − | ! a || b || c || | + | ! Узел || и || м || п || с |
| | |- | | |- |
| − | | 4 || 2 || 1 || | + | | Вес || 4 || 1 || 1 || 3 |
| | |} | | |} |
| | | | |
| − | Следующим шагом будет построение дерева, где вершины - "символы", а пути до них соответствуют их префиксным кодам.
| + | По алгоритму возьмем два символа с наименьшей частотой - это ''м'' и ''п''. Сформируем из них новый узел ''мп'' весом 2 и добавим его к списку узлов: |
| − | Для этого на каждом шаге будем брать два символа с минимальной частотой вхождения, и объединять их в новые так называемые символы с частотой равной сумме частот тех, которые мы объединяли, а также соединять их рёбрами, образуя таким образом дерево(см. рисунок). Выбирать минимальные два символа будем из всех символов, исключая те, которые мы уже выбирали.
| |
| − | В примере мы объединим символы b и с в символ bc с частотой 3. Далее объединим a и bc в символ abc, получив тем самым дерево. Теперь пути от корня (abc) до листьев и есть Коды Хаффмана(каждому ребру соответствует либо 1 либо 0)
| |
| | | | |
| | {| class="wikitable" | | {| class="wikitable" |
| − | ! a || b || c || | + | ! Узел || и || мп || с |
| | |- | | |- |
| − | | 0 || 11 || 10 || | + | | Вес || 4 || 2 || 3 |
| | |} | | |} |
| | | | |
| − | == Корректность алгоритма Хаффмана ==
| + | Затем объединим в один узел узлы ''мп'' и ''c'': |
| − |
| |
| − | Чтобы доказать корректность алгоритма Хаффмана, покажем, что в задаче о построении оптимального префиксного кода проявляются свойства жадного выбора и оптимальной подструктуры. В сформулированной ниже лемме показано соблюдение свойства жадного выбора.
| |
| | | | |
| − | {{Лемма | + | {| class="wikitable" |
| − | |id=lemma1 | + | ! Узел || и || мпс |
| − | |about=1 | + | |- |
| − | |statement= | + | | Вес || 4 || 5 |
| − | Пусть <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>x</tex> и <tex>y</tex> являются листьями с общим родительским узлом, причем в новом дереве эти листья находятся на максимальной глубине.
| |
| | | | |
| − | Пусть <tex>a</tex> и <tex>b</tex> — два символа, представленные листьями с общим родительским узлом, которые находятся на максимальной глубине дерева <tex>T</tex>.
| + | <small>Конечно же, здесь будет нормальная картинка</small> |
| | | | |
| − | Предположим без потери общности, что <tex>f[a] \le f[b]</tex> и <tex>f[x] \le f[y]</tex>.
| + | Соответствующая ему таблица кодов: |
| | | | |
| − | Поскольку <tex>f[x]</tex> и <tex>f[y]</tex> — две самые маленькие частоты (в указанном порядке), <tex>f[a]</tex> и <tex>f[b]</tex> — две произвольные частоты, то выполняются соотношения <tex>f[x] \le f[a]</tex> и <tex>f[y] \le f[b]</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>. Разность стоимостей деревьев Т и Т" равна
| + | {| class="wikitable" |
| − | | + | ! Символ || и || м || п || с |
| − | <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)) \ge 0 ,</tex>
| + | | Код || 0 || 100 || 101 || 11 |
| − | | + | |} |
| − | поскольку величины <tex>f[a] - f[x]</tex> и <tex>d_T(a) - d_T(x)</tex> неотрицательны. Величина <tex>f[a] - f[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') \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 C \backslash \{x,y\}</tex> выполняется соотношение <tex>d_T(C) = d_{T'}(c)</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>, получаем соотношение<br> | |
| − | <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>
| |
| − | <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>. Тогда можно записать:<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>.
| |
| − | }}
| |
| − | | |
| − | {{Теорема
| |
| − | |id=th1 | |
| − | |statement= | |
| − | Алгоритм Хаффмана дает оптимальный префиксный код.
| |
| − | |proof= | |
| − | Справедливость теоремы непосредственно следует из лемм (1) и (2)
| |
| − | }} | |
| − | | |
| − | == Литература ==
| |
| − | * Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — С. 1296. — ISBN 5-8489-0857-4
| |
| | | | |
| − | [[Категория: Алгоритмы сжатия ]]
| + | Таким образом, закодированное слово ''"миссисипи"'' будет выглядеть как ''"1000111101101010"''. Длина закодированного слова - 16 бит. Стоит заметить, что если бы мы использовали для кодирования каждого символа из четырёх по 2 бита, длина закодированного слова составила бы 18 бит. |
Пример
Для примера возьмём слово "Миссисипи". Тогда алфавит будет [math]A= \{[/math] и, м, п, с [math]\} [/math], а набор весов [math]W=\{4, 1, 1, 3\}[/math]:
По алгоритму возьмем два символа с наименьшей частотой - это м и п. Сформируем из них новый узел мп весом 2 и добавим его к списку узлов:
Затем объединим в один узел узлы мп и c:
И, наконец, объединяем два узла и и мпс. Итак, мы получили дерево:
Конечно же, здесь будет нормальная картинка
Соответствующая ему таблица кодов:
| Символ |
и |
м |
п |
с
|
| Код |
0 |
100 |
101 |
11
|
Таким образом, закодированное слово "миссисипи" будет выглядеть как "1000111101101010". Длина закодированного слова - 16 бит. Стоит заметить, что если бы мы использовали для кодирования каждого символа из четырёх по 2 бита, длина закодированного слова составила бы 18 бит.
