Код Хаффмана

Тема 4. Кодирование информации

Лекция 6 .Сжатие информации

Учебные вопросы:

  1. Код Хаффмана
  2. Арифметическое кодирование
  3. Алгоритмы сжатия

Код Хаффмана

Хаффмановское кодирование появилось в 1952 году.Главное его предназначение заключалось в упаковке текстовых файлов - для другого он мало приспособлен. Имеет довольно простую реализацию, так что его вполне удобно использовать в устройствах имеющих слабые микропроцессоры. Код Хаффмана является префиксным, то есть в таком коде ни одна комбинация не совпадает с началом более длинной комбинации, а это позволяет обеспечить однозначное декодирование без введения разделительных символов.

Код Хаффмана строится следующим образом: буквы располагают в порядке убывания их вероятностей. Складывают вероятности двух последних букв, и ряд переписывают снова с учетом новой вероятности (суммы). Далее повторяют операцию, пока не получится 1. Нижнюю букву всегда кодируют нулем, а верхнюю – единицей. .

Он также учитывает статистические свойства сигналов, при которых вероятности появления букв p1, р2, …рк не равные между собой, поэтому H < log n.

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

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

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

исходный поток АБАБАБАВАБВГ = 12 байт

выходной поток Пусть символы кодируются как

А=1

Б=01

В=001

Г=000

тогда будет 101101101101001101001000 = 25 бит = 3 байт + 1 бит

 

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

 

Граф - это совокупность множества углов и соединяющих их дуг .Направленные графы могут быть циклическими.

 

Дерево - граф, обладающий следующими свойствами:

ни в один из углов не входит более одной дуги;

только в один узел (он называется корнем) не входит ни одной дуги;

перемещаясь от корня по дугам, можно попасть в любой узел.

 

Лист дерева - это узел, из которого не выходит ни одной дуги. Два листа, имеющие общий узел, называются родственными.

 

Двоичное дерево - дерево, у которого из каждого угла выходит только две дуги.

 

H- дерево - двоичное дерево кодирования, у которого каждый узел имеет вес, причем вес родителя равен сумме весов детей.

 

Входной алфавит - совокупность всех символов.

 

Алгоритм Хаффмана: