скачать doc
1.6. Доказательство оптимальности кода Хаффмана
Лемма 1. Пусть w1 w2 … wn 1 wn. Существует такой оптимальный префиксный код, что l1 l2 … ln 1 ln.
Доказательство. Пусть C = {c1, c2,…, cn} – некоторый оптимальный префиксный код, а
префиксный код, полученный из C перестановкой i-го и j-го кодовых слов. Тогда 
и 
, а для 
имеем 
. Далее
Тогда из
следует li lj. Если же 
, то 
. За конечное число перестановок индексов i и j , удовлетворяющих условию , можно получить требуемое неравенство для li и lj.Лемма 2. Пусть w1 w2 … wn 1 wn. Существует такой оптимальный префиксный код C, что l1 l2 … ln 1 = ln, и кодовые слова
и 
различаются в точности последним символом.Доказательство. Пусть C – некоторый оптимальный префиксный код, в котором l1 l2 … ln 1 ln (лемма 1), и пусть сn = (сn(1), сn(2),…, сn(ln)). Рассмотрим два случая.
Случай 1: нет кодового слова (сn(1), сn(2),…, сn(ln 1), 1 сn(ln)). В терминах дерева это означает, что имеет место одна из двух ситуаций
Поскольку код префиксный, то узел отец (n) не представляет кодового слова. Тогда узел n можно «поднять» на место его отца и, следовательно, уменьшить величину ln , а тем самым и длину полного кода L = i=1..n wi li , что противоречит оптимальности кода C. Итак, случай 1 невозможен.
Случай 2: пусть для некоторого i1..n 1 существует кодовое слово сi = (сn(1), сn(2),…, сn(ln 1), 1 сn(ln)). Если i = n 1, то утверждение леммы справедливо. Если же i < n 1, то li = ln = ln 1. Переставим кодовые слова с номерами i и n 1 (перевесим листья дерева). При этом значение L = i=1..n wi li не изменится, а новый префиксный код будет обладать желаемым (по лемме) свойством. Лемма 2 доказана.
При формулировке следующего утверждения будут использованы обозначения Wn и
, как они определены в 1.4 при описании алгоритма Хаффмана. Кроме того, полную длину кода L будем записывать как функцию от набора весов Wn и кодового дерева Tn: L = L(Wn, Tn). Если Tn – оптимальное кодовое дерево (ОКД), то обозначим Lmin(Wn) = L(Wn, Tn). Утверждение. Пусть w1 w2 … wn 1 wn. Пусть
– ОКД для , т. е. 
. Пусть 
Тогда
– ОКД для Wn , т. е. 
.Доказательство. По построению дерева
справедливо
. (*)С другой стороны пусть Tn – некоторое ОКД для набора весов Wn , а
– такое ОКД для набора весов Wn , что удовлетворены все условия леммы 2, тогда
(**)где
– дерево, полученное из ОКД заменой поддерева из двух листьев с весами wn 1 и wn на лист с весом 
. Из неравенств (*) и (**) получаем требуемое равенство,завершая тем самым доказательство утверждения.
Фактически доказанное утверждение есть обоснование индуктивного перехода в доказательстве оптимальности дерева Хаффмана методом математической индукции. Действительно, мы показали, что из оптимальности предварительно построенного
следует оптимальность дерева .1.7. Неравенство Крафта
Оптимальное кодовое дерево определяет набор длин (l1, l2, …, ln) кодовых слов, минимизирующий L = i=1..n wi li и учитывающий требование префиксности кода. Рассмотрим это требование более формально. Оказывается, что на вопрос о том, для каких заданных длин (li)1n кодовых слов существует префиксный код, можно дать точный ответ, найденный Л. Крафтом (L.G. Kraft).
Утверждение (неравенство Крафта). Для того, чтобы существовал префиксный код с длинами кодовых слов l1, l2, …, ln , необходимо и достаточно выполнение неравенства
.Доказательство. 1) Необходимость (из существования префиксного кода следует неравенство Крафта). Рассмотрим кодовое дерево, соответствующее префиксному коду с длинами кодовых слов l1, l2, …, ln . Обозначим
число листьев на k-ом уровне (k = 0, 1,…, K, где K – максимальная длина кодового слова или высота кодового дерева). Очевидно, 
. Можно дать более точную оценку. Наличие листа на уровне i исключает 
узлов на уровне k (k i). Если на уровне i имеется 
листьев, то они «обрывают» поддеревья с 
узлов на уровне k. Следовательно, число узлов на уровне k не превосходит 
,а следовательно
.Отметим, что на последнем уровне неравенство «<» имеет место за счет того, что дерево может быть не строго бинарным, а код, соответственно, неполным. Разделив обе части полученного неравенства на
и сгруппировав слагаемые, получим
или
.Заменяя суммирование по уровням на суммирование по листьям, получаем
.2) Достаточность (из неравенства Крафта следует существование префиксного кода). Пусть выполняется неравенство Крафта. Переходя от суммирования по листьям к суммированию по уровням, получим
.Отсюда следует, что и для всех слагаемых выполняется
,и, следовательно, для всех k 1..K
. (***)Далее рассмотрим полное ровное дерево высоты K. Будем строить кодовое дерево по уровням от корня вниз, удаляя лишние узлы и ветки. Начнём с
, которое может принимать значения 0, 1, 2. Выберем в соответствии с l1, l2, …, ln . Рассмотрим 
. Очевидно, после нашего выбора на втором уровне останется 4 2 узлов, из которых нужно выбрать листьев. Поскольку в силу неравенства (***) имеем 
, то этот выбор возможен. Далее рассмотрим третий уровень. На нём свободных для выбора осталось 
узлов. Из неравенства (***) следует, что 
, т. е. опять-таки выбор 
листьев возможен. Повторяя этот процесс до k = K, получим требуемое кодовое дерево. Доказательство завершено.Теперь можно сформулировать задачу построения оптимального префиксного кода, как задачу нахождения такого набора
, который минимизирует 
при заданном наборе 
и при ограничениях: 1) 
целые и 
для 
; 2) (свойство префиксности).