Алгоритм Хаффмана — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Корректность алгоритма Хаффмана: зачем русскими буквами в формуле? :()
(Корректность алгоритма Хаффмана)
Строка 33: Строка 33:
 
|id=lemma1
 
|id=lemma1
 
|about=1
 
|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> в котором имеют одинаковую длину и отличаются лишь последним битом.  
+
|statement=
|proof=Идея доказательства состоит в том, чтобы взять дерево <tex>T</tex>, представляющее произвольный оптимальный префиксный код, и преобразовать его в дерево, представляющее другой оптимальный префиксный код, в котором символы <tex>x</tex> и <tex>y</tex> являются листьями с общим родительским узлом, причем в новом дереве эти листья находятся на максимальной глубине. Пусть <tex>a</tex> и <tex>b</tex> — два символа, представленные листьями с общим родительским узлом, которые находятся на максимальной глубине дерева <tex>T</tex>. Предположим без потери общности, что <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>, а при последующей перестановке в дереве V листьев <tex>b</tex> и <tex>y</tex> получается дерево <tex>T''</tex>. Разность стоимостей деревьев Т и Т" равна <br>
+
Пусть <tex>C</tex> — алфавит, каждый символ <tex>c \in C</tex> которого встречается с частотой <tex>f[c]</tex>. Пусть <tex>x</tex> и <tex>y</tex> — два символа алфавита <tex>C</tex> с самыми низкими частотами.
<tex>B(T) - B(T') = \sum_{c \in C} f(c)d_T(C) - \sum_{c \in C} f(c)d_{T'}(C) =</tex><br><tex> = (f[a] - f[x])(d_T(a) - d_T(x)) \ge 0</tex>,<br>
+
 
поскольку величины  <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> — находящиеся на максимальной глубине дочерние листья одного и того же узла, что и доказывает лемму.
+
Тогда для алфавита <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>. Предположим без потери общности, что <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>, а при последующей перестановке в дереве V листьев <tex>b</tex> и <tex>y</tex> получается дерево <tex>T''</tex>. Разность стоимостей деревьев Т и Т" равна
 +
 
 +
<tex>B(T) - B(T') = \sum_{c \in C} f(c)d_T(C) - \sum_{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]</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.
+
|id=lemma2
 
|about=2
 
|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>.  
 
|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>.  
Строка 47: Строка 58:
 
<br>
 
<br>
 
из которого следует равенство <br>
 
из которого следует равенство <br>
<tex> B(T) = B(T') + f[x] + f[y] </tex> <br>
+
<tex> B(T) = B(T') + f[x] + f[y] </tex>
ИЛИ <br>
+
 
<tex> B(T') = B(T) - f[x] - f[y] </tex>. <br>
+
ИЛИ
 +
 
 +
<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> 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>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>.   
 
что противоречит предположению о том, что дерево <tex>T'</tex> представляет оптимальный префиксный код для алфавита <tex>C'</tex>. Таким образом, дерево <tex>T</tex> должно представлять оптимальный префиксный код для алфавита <tex>C</tex>.   
 
}}
 
}}
 +
 
{{Теорема
 
{{Теорема
 
|id=th1
 
|id=th1
 
|statement=
 
|statement=
Процедура Huffman дает оптимальный префиксный код.  
+
Алгоритм Хаффмана дает оптимальный префиксный код.  
 
|proof=
 
|proof=
 
Справедливость теоремы непосредственно следует из лемм (1) и (2)
 
Справедливость теоремы непосредственно следует из лемм (1) и (2)

Версия 21:43, 25 сентября 2011

Определение

Определение:
Коды или Алгоритм Хаффмана (Huffman codes) — широко распространенный и очень эффективный метод сжатия данных, который, в зависимости от характеристик этих данных, обычно позволяет сэкономить от 20% до 90% объема.

Рассматриваются данные, представляющие собой последовательность символов. В жадном алгоритме Хаффмана используется таблица, содержащая частоты появления тех или иных символов. С помощью этой таблицы определяется оптимальное представление каждого символа в виде бинарной строки.

Построение кода Хаффмана

Обрабатываем b и c
Получившееся дерево

В основу алгоритма Хаффмана положена идея: кодировать более коротко те символы, которые встречаются чаще, а те, которые встречаются реже кодировать длиннее. Для построения кода Хаффмана нам необходима таблица частот символов. Рассмотрим пример построения кода на простой строке abacaba

a b c
4 2 1

Следующим шагом будет построение дерева, где вершины - "символы", а пути до них соответствуют их префиксным кодам. Для этого на каждом шаге будем брать два символа с минимальной частотой вхождения, и объединять их в новые так называемые символы с частотой равной сумме частот тех, которые мы объединяли, а также соединять их рёбрами, образуя таким образом дерево(см. рисунок). Выбирать минимальные два символа будем из всех символов, исключая те, которые мы уже выбирали. В примере мы объединим символы b и с в символ bc с частотой 3. Далее объединим a и bc в символ abc, получив тем самым дерево. Теперь пути от корня (abc) до листьев и есть Коды Хаффмана(каждому ребру соответствует либо 1 либо 0)


a b c
0 11 10


Корректность алгоритма Хаффмана

Чтобы доказать корректность жадного алгоритма Huffman, покажем, что в задаче о построении оптимального префиксного кода проявляются свойства жадного выбора и оптимальной подструктуры. В сформулированной ниже лемме показано соблюдение свойства жадного выбора.

Лемма (1):
Пусть [math]C[/math] — алфавит, каждый символ [math]c \in C[/math] которого встречается с частотой [math]f[c][/math]. Пусть [math]x[/math] и [math]y[/math] — два символа алфавита [math]C[/math] с самыми низкими частотами. Тогда для алфавита [math]C[/math] существует оптимальный префиксный код, кодовые слова символов [math]x[/math] и [math]y[/math] в котором имеют одинаковую длину и отличаются лишь последним битом.
Доказательство:
[math]\triangleright[/math]

Идея доказательства состоит в том, чтобы взять дерево [math]T[/math], представляющее произвольный оптимальный префиксный код, и преобразовать его в дерево, представляющее другой оптимальный префиксный код, в котором символы [math]x[/math] и [math]y[/math] являются листьями с общим родительским узлом, причем в новом дереве эти листья находятся на максимальной глубине.

Пусть [math]a[/math] и [math]b[/math] — два символа, представленные листьями с общим родительским узлом, которые находятся на максимальной глубине дерева [math]T[/math]. Предположим без потери общности, что [math]f[a] \le f[b][/math] и [math]f[x] \le f[y][/math]. Поскольку [math]f[x][/math] и [math]f[y][/math] — две самые маленькие частоты (в указанном порядке), [math]f[a][/math] и [math]f[b][/math] — две произвольные частоты, то выполняются соотношения [math]f[x] \le f[a][/math] и [math]f[y] \le f[b][/math]. В результате перестановки в дереве [math]T[/math] листьев [math]a[/math] и [math]x[/math] получается дерево [math]T'[/math], а при последующей перестановке в дереве V листьев [math]b[/math] и [math]y[/math] получается дерево [math]T''[/math]. Разность стоимостей деревьев Т и Т" равна

[math]B(T) - B(T') = \sum_{c \in C} f(c)d_T(C) - \sum_{c \in C} f(c)d_{T'}(C)= \\ \\ =(f[a] - f[x])(d_T(a) - d_T(x)) \ge 0 ,[/math]

поскольку величины [math]f[a] - f[x][/math] и [math]d_T(a) - d_T(x)[/math] неотрицательны. Величина [math]f[a] - f[x][/math] неотрицательна, потому что х — лист с минимальной частотой, величина [math]d_T(a) - d_T(x)[/math] неотрицательна, потому что [math]a[/math] — лист на максимальной глубине в дереве [math]T[/math]. Аналогично, перестановка листьев [math]y[/math] и [math]b[/math] не приведет к увеличению стоимости, поэтому величина [math]B(T') - B(T'')[/math] неотрицательна.

Таким образом, выполняется неравенство [math]B(T') \le B(T'')[/math], и поскольку [math]T[/math] — оптимальное дерево, то должно также выполняться неравенство [math]B(T'') \le B(T')[/math], откуда следует, что [math]B(T') = B(T'')[/math]. Таким образом, [math]T''[/math] — оптимальное дерево, в котором [math]x[/math] и [math]y[/math] — находящиеся на максимальной глубине дочерние листья одного и того же узла, что и доказывает лемму.
[math]\triangleleft[/math]
Лемма (2):
Пусть дан алфавит [math]C[/math], в котором для каждого символа [math]c \in C[/math] определены частоты [math]f[c][/math]. Пусть [math]x[/math] и [math]y[/math] — два символа из алфавита [math]C[/math] с минимальными частотами. Пусть [math]C'[/math] — алфавит, полученный из алфавита [math]C[/math] путем удаления символов [math]x[/math] и [math]y[/math] и добавления нового символа [math]z[/math], так что [math]C' = C \backslash \{ x, y \} \cup {z}[/math]. По определению частоты [math]f[/math] в алфавите [math]C'[/math] совпадают с частотами в алфавите [math]C[/math], за исключением частоты [math]f[z] = f[x] + f[y][/math]. Пусть [math]T'[/math] — произвольное дерево, представляющее оптимальный префиксный код для алфавита [math]C'[/math] Тогда дерево [math]T[/math], полученное из дерева [math]T'[/math] путем замены листа [math]z[/math] внутренним узлом с дочерними элементами [math]x[/math] и [math]y[/math], представляет оптимальный префиксный код для алфавита [math]C[/math].
Доказательство:
[math]\triangleright[/math]

Сначала покажем, что стоимость [math]B(T)[/math] дерева [math]T[/math] можно выразить через стоимость [math]B(T')[/math] дерева [math]T'[/math]. Для каждого символа [math]c \le C - {x,y}[/math] выполняется соотношение [math]d_T(C) = d_{T'}(c)[/math], следовательно, [math]f[c]d_T(C) = f[c]d_{T'}(c)[/math]. Поскольку [math]d_T(x) = d_{T}(y) = d_{t'}(z) + 1[/math], получаем соотношение
[math]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])[/math]
из которого следует равенство
[math] B(T) = B(T') + f[x] + f[y] [/math]

ИЛИ

[math] B(T') = B(T) - f[x] - f[y] [/math].

Докажем лемму методом от противного. Предположим, дерево [math] T [/math] не представляет оптимальный префиксный код для алфавита [math] C [/math]. Тогда существует дерево [math] T'' [/math], для которого справедливо неравенство [math] B(T'') \lt B(T) [/math]. Согласно лемме (1), [math]x[/math] и [math]y[/math] без потери общности можно считать дочерними элементами одного и того же узла. Пусть дерево [math]T'''[/math] получено из дерева [math]T''[/math] путем замены элементов [math]x[/math] и [math]y[/math] листом [math]z[/math] с частотой [math]f[z] = f[x] + f[y] [/math]. Тогда можно записать:
[math]B(T''') = B(T'') - f[x] - f[y] \lt B(T) - f[x] -f[y] = B(T')[/math],

что противоречит предположению о том, что дерево [math]T'[/math] представляет оптимальный префиксный код для алфавита [math]C'[/math]. Таким образом, дерево [math]T[/math] должно представлять оптимальный префиксный код для алфавита [math]C[/math].
[math]\triangleleft[/math]
Теорема:
Алгоритм Хаффмана дает оптимальный префиксный код.
Доказательство:
[math]\triangleright[/math]
Справедливость теоремы непосредственно следует из лемм (1) и (2)
[math]\triangleleft[/math]

Литература

  • Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — С. 1296. — ISBN 5-8489-0857-4