Лекция 4. Оптимальное кодирование (метод Хаффмана)

Этот метод имеет два преимущества по сравнению с методом Шеннона-Фано: он устраняет неоднозначность кодирования, возникающую из-за примерного равенства сумм частот при разделении списка на две части (линия деления проводится неоднозначно), и имеет, в общем случае, большую эффективность кода. Исходное множество символов упорядочивается по невозрастанию частот, после чего выполняются следующие шаги:

• 1) объединение частот:
  • — две последние частоты списка складываются, а соответствующие символы исключаются из списка;
  • — оставшийся после исключения символов список пополняется суммой частот и вновь упорядочивается;
  • — предыдущие шаги повторяются до тех пор, пока ни получится единица в результате суммирования и список ни уменьшится до одного символа.
• 2) построение кодового дерева:
  • — строится двоичное кодовое дерево: корнем его является вершина, полученная в результате объединения частот, равная 1, листьями — исходные вершины;
  • — остальные вершины соответствуют либо суммарным, либо исходным частотам, причем для каждой вершины левая подчиненная вершина соответствует большему слагаемому, а правая — меньшему;
  • — ребра дерева связывают вершины-суммы с вершинами-слагаемыми.

Структура дерева показывает, как происходило объединение частот. Ребра дерева кодируются: каждое левое кодируется единицей, каждое правое — нулём.

3) формирование кода: для получения кодов листьев (исходных кодируемых символов) продвигаются от корня к нужной вершине и «собирают» веса проходимых рёбер.

Рассмотрим пример.

Даны символы a, b, c, d с частотами p (a) = 0,5; p (b) = 0,25; p© = 0,125; p (d)= 0,125. Построить эффективный код методом Хаффмана.

1) объединение частот (результат объединения двух последних частот в списке выделен в правом соседнем столбце штриховкой).

• 2) Построение кодового дерева.
• 3) формирование кода:

K (a) = 1; K (b) = 01; K© = 001; K (d) = 000.

Как видно, полученные коды совпадают с теми, что были сформированы методом Шеннона-Фано, следовательно, они имеют одинаковую эффективность.

Повышение эффективности кодирования Повысить эффективность кодирования можно, строя код не для символа, а для блоков из n символов, причем частота блока рассчитывается как произведение частот символов, входящих в блок. Рассмотрим этот тезис на примере.

Даны символы a и b с частотами, соответственно, 0,9 и 0,1. Построить эффективный код методом Шеннона-Фано для блоков из двух символов (n = 2). Сформируем список возможных блоков и их частот. При этом частоту блока будем рассчитывать как произведение частот символов, входящих в блок. Тогда имеем:

Блоки символов Частоты блоков.

aa 0,81.

ab 0,09.

ba 0,09.

bb 0,01.

Построение кода сведём в таблицу:

Таким образом, получены коды:

K (aa) = 1; K (ab) = 01; K (ba) = 001; K (bb) = 000.

Определим эффективность построенного кода. Для этого рассчитаем сначала показатель эффективности для блока символов:

I_{ср. блока} = 0,81*1 + 0,09*2 + 0,09*3 + 0,01*3 = 1,28.

Поскольку в блоке 2 символа (n=2), для одного символа.

I_ср =I_{ср. блока}/2 = 1,28/2 = 0,64.

При посимвольном кодировании для эффективного кода потребуется по одному двоичному разряду, т. е. на (1−0,64)=0,36 бита больше. В самом деле, применение метода Шеннона-Фано для отдельных символов даёт результат, представленный в следующей таблице: