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

Алгоритм работает по схеме:

1. последовательность символов предварительно просматривается и производится подсчёт количества вхождений любого символа в эту последовательность;

2. на основе полученных данных строится таблица распределения вхождений любого символа в эту последовательность;

3. полученная таблица сортируется по невозрастанию количества вхождений символов в последовательность;

4. таблица, полученная на третьем этапе, используется для построения двоичного дерева;

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

При декодировании побитно просматривается входящая строка и, в соответствии с двоичным деревом, составляются коды символов и записываются в выходной поток.

Недостатки метода:

• процесс кодирования требует двух проходов по строчке;

• для декодирования требуется передавать вместе с потоком выходных данных описание модели кодирования, т.е. двоичное дерево – поэтому размер сжатых данных может превышать размер исходных данных (в особенности для коротких строк);

• код наиболее часто встречающегося символа занимает 1 бит, а код 256 символа – 256 бит, т.е. 32байта. Наименьший код, в соответствии с алгоритмом Хаффмана, имеет длину 1 бит, хотя теоретически можно представить 1 символ меньшим количеством бит.

0