Главная arrow Двоичный код arrow Метод Хаффмена
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Метод Хаффмена Печать

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

Исходное множество символов упорядочивается по не возрастанию частоты и выполняются следующие шаги:

1) объединение частот:

·                    две последние частоты списка складываются, а соответствующие символы исключаются из списка;

·                    оставшийся после исключения символов список пополняется суммой частот и вновь упорядочивается;

·                    предыдущие шаги повторяются до тех пор, пока ни получится единица в результате суммирования и список ни уменьшится до одного символа;

2) построение кодового дерева:

·                    строится двоичное кодовое дерево: корнем его является вершина, полученная в результате объединения частот, равная 1; листьями – исходные вершины; остальные вершины соответствуют либо суммарным, либо исходным частотам, причем для каждой вершины левая подчиненная вершина соответствует большему слагаемому, а правая – меньшему; ребра дерева связывают вершины-суммы с вершинами-слагаемыми. Структура дерева показывает, как происходило объединение частот;

·                    ребра дерева кодируются: каждое левое кодируется единицей, каждое правое – нулем;

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

Пример 1. Даны символы a, b, c, d с частотами fa = 0,5; fb = 0,25; fc = 0,125; fd= 0,125. Построить эффективный код методом Хаффмена.

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

Исходные символы

Частоты fs

Этапы объединения

первый

второй

третий

a

0,5

0,5

0,5

1

b

0,25

0,25

0,5

 

c

0,125

0,25

 

 

d

0,125

 

 

 

2) построение кодового дерева:

3) формирование кода:

a        -        1;

b        -        01;

c        -        001;

d        -        000.

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