Кодовые деревья, коды Хаффмана.

Кодовое дерево для последнего примера:

Построение кода и кодового дерева по Фано на примере:

Построение кода по кодовому дереву методом Хаффмана на примере:

Дерево строится снизу. Выписываются концевые вершины дерева с их частотами:

Берутся две вершины с самыми маленькими значениями частот и над ними создается вершина с суммой этих частот:

Вершины с самыми маленькими частотами далее при построении дерева не принимаются во внимание, их заменила суммарная вершина, которая теперь становится одной из самых маленьких по частоте из оставшихся вершин. Соединяем эту вершину с другой вершиной с наименьшим значением частоты, строя над ними новую вершину с суммарной частотой.

Далее снова находим пары вершин с меньшими частотами и строим над ними вершины с суммарными частотами:

Ищем среди полученных новых и тех вершин, которые еще не участвовали в построении новых, пары с наименьшими значениями частот, и над ними строим суммарные вершины. При этом каждую левую ветку помечаем нулем, а каждую правую единицей:

Продолжая этот процесс в итоге получаем дерево:

Это кодовое дерево порождает следующий код для заданных сообщений:

Рассмотрим следующий пример.

Построим коды по Фано и по Хаффману и сравним их цены и избыточности:

По Фано:

0.4 0.15 0.15 0.15 0.15

________ _______________

0.55 0 0.45 1

00 01 10 110 111 L=0.4*2+0.3*2+0.3*3=0.8+1.5=2.3 I=2.17 δ=0.056

00 01 100 101 11

По Хаффману:

/ \

/ 0.6

/ / \

/ 0.3 0.3

/ / \ / \

0.4 0.15 0.15 0.15 0.15

0 100 101 110 111 L=0.4+0.6*3=2.2 δ=0.013

Как видим, код по Хаффману получился более экономным, чем код по Фано (цена и избыточность у него меньше).

Задача 3. Построить код Хаффмана для рассмотренного выше примера со следующим распределением вероятностей для семи сообщений:

И сравнить цену и избыточность полученного кода с построенным выше кодом Фано.

ПРИМЕР

1 1 0 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 0 0 0 1 0 0 1 0 1 0 0

-------------- ----------- -------- ----------- -------- -----------