Правильность алгоритма Хаффмена.

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

Лемма 8.1 Пусть в алфавите C любой символ c  C имеет частоту f[c]. Пусть x, y  C — два символа с наименьшими частотами. Тогда для C имеется оптимальный префиксный код, в котором последовательности битов, кодирующих x и y, имеют одинаковую длину и различаются только в последнем бите.

Доказательство. Рассмотрим произвольное оптимальное дерево префиксных кодов T. Покажем, что это дерево можно изменить так, чтобы листья, соответствующие x и y, были бы братьями, если они не были таковыми ранее. Это и докажет данную лемму.

Рассмотрим пару соседних листьев дерева T, находящуюся на максимальном расстоянии от корня. Символы, которые располагаются в этих листьях (b и c), имеют не меньшие частоты, чем x и y. Можно считать, что f[x] ≤ f[b] и f[y] ≤ f[с]. Далее совершим две операции с деревом T: поменяем местами символы b и x (получившееся дерево назовем T′), а затем символы c и y (получившееся дерево назовем T″). Покажем теперь, что дерево T″ также является оптимальным. Для этого нужно доказать, что B(T) ≥ B(T′) ≥ B(T″) (B — функция стоимости). При переходе от T к T′ в функции стоимости меняются только два слагаемых: f[b]d_T(b) + f[x]d_T(x) заменяется на f[b]d_T′(b) + f[x]d_T′(x), т. е. на f[b]d_T(x) + f[x]d_T(b). Получаем

B(T) − B(T′) = f[b]d_T(b) + f[x]d_T(x) − f[b]d_T(x) − f[x]d_T(b) = (f[b] − f[x])(d_T(b) − d_T(x)) ≥ 0.

Аналогично доказываем B(T′) ≥ B(T″), получаем B(T) ≥ B(T″), и поэтому дерево T″ также оптимально.

Покажем теперь, что выполнено свойство оптимальности для подзадач.

Пусть имеется алфавит C и два символа x, y  C, а C′ — алфавит, который получится из C, если выкинуть x и y и добавить новый символ z. Рассмотрим кодовые деревья для C, в которых x и y являются братьями. Получим, что каждому дереву для C соответствует одно кодовое дерево для C′, получающееся, если выбросить вершины x и y, а их общего родителя считать кодом символа z. При этом дереву для C′ соответствует два кодовых дерева для C.

Для каждого символа с  C фиксируем его частоту f[c]. Для символов из C′, кроме z (f[z] = f[x] + f[y]), частоты такие же, что и в C. Теперь можно сформулировать лемму.

Лемма 8.2 Стоимости соответствующих друг другу деревьев T и T′ (при описанном соответствии) отличаются на величину f[x] + f[y].

Доказательство. Понятно, что d_T(c) = d_T′(x) для всех с  C \ {x,y}, а d_T(x) = d_T(y) = d_T′(z) + 1. Получаем

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]).

откуда B(T) = B(T′) + f[x] + f[y].

Теперь сформулируем окончательную теорему.

Теорема 8.2 Жадный алгоритм Хаффмена строит оптимальный префиксный код.

Доказательство. Оптимальные кодовые деревья можно искать среди таких, у которых два наиболее редких символа (x и y) являются братьями (по лемме 1). Им соответствуют деревья для алфавита С′, в котором x и y слиты в z. Если считать, что f[z] = f[x] + f[y], то по лемме 2 нам остаётся найти оптимальное кодовое дерево для алфавита C′, а затем добавить к вершине z двух детей, помеченных символами x и y.