Алгоритм Хаффмена для символьных групп

Кодирование по алгоритму Хаффмена

Международный консультативный комитет по телефонии и телеграфии (CCITT) разработал серию протоколов для факсимильной передачи изображений. Эти протоколы основываются на алгоритме, предложенном Д. Хаффменом в 1952г., и используются для обработки черно-белых изображений.

Метод Хаффмена строит таблицы кодов, базирующихся на частоте повторения элементов. Чем чаще встречается тот или иной элемент, тем короче будет заменяющий его код.

Степень сжатия 2:1 и 3:1.

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

//Этот алгоритм разрабатывался для факсовых передач черно-белых изображений передачи данных. Также называется кодирование по алгоритму Хаффмана.

Он является неадаптивным, то есть не настраивается для кодирования каждого реестра оптимальным образом , используется фиксирование таблицы кодовых значений , которые были выбраны заранее для представления данных в степень сжатия по этим алгоритмам 5:1-8:1.

Кодирование:

Кодировщик определяет длину пиксельных групп в строке развертке и выводит двоичное кодовое слово, представляющее длину и цвет группы . Кодированное слова берутся из таблицы значений представляемых группами белых и черных пикселей. Двоичное кодовое слово по этому алгоритму бывает переменной длины. Размер каждого слова определяется на основе статистически усредненной частоты черно-белых групп, появляется в течение печатных документов. Длины групп, встречающиеся наиболее часто, присваивается наименьшее кодированное слово , чем длины групп, которые появляются менее часто.//

Подсчитаем вхождение каждого символа в файл и получим следующие характеристики

Файл длиной 100 байт, имеет различные символы, длина каждого 1 байт.

на 100 символов

Сначала рассматриваются те символы, которые имеют самую низкую частоту вхождений.

Например D и F или D и A. Для них формируется узел, частота вхождения которого равна сумме частот вхождений этих символов.

A B C D E F

10 20 30 5 25 10

| | | | | |

| | | |______|______|

| | | 15 |

|_____|_____|_________| |

| 25 |___________|

|___| 55

45 |

|__________|

Если из вершины дерева идти по левой ветке, то присваиваем значение 0, по правой – 1.

C 10 E 11 B 00 A 010 F 0111 D 0110

Базируется на частоте повторений величин: чем чаще встречается величина, тем короче будет её код.

Существует целая группа протоколов, разработанных с использованием алгоритма Хаффмена. За счет модификации этого алгоритма достигается степень сжатия 4:1 и 5:1.

//7.12.04 Лекция 10//