Метод Хаффмана

Этот алгоритм кодирования информации был предложен Д.А. Хаффманом в 1952 году. Хаффмановское кодирование (сжатие) – это широко используемый метод сжатия, присваивающий символам алфавита коды переменной длины основываясь на вероятностях появления этих символов.

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

Префиксный код – это код, в котором никакое кодовое слово не является префиксом любого другого кодового слова. Эти коды имеют переменную длину.

Оптимальный префиксный код – это префиксный код, имеющий минимальную среднюю длину.

Алгоритм Хаффмана можно разделить на два этапа.

1) Определение вероятности появления символов в исходном тексте.

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

2) Нахождение оптимального префиксного кода.

Далее находятся два символа a и b с наименьшими вероятностями появления и заменяются одним фиктивным символом x, который имеет вероятность появления, равную сумме вероятностей появления символов a и b. Затем, используя эту процедуру рекурсивно, находится оптимальный префиксный код для меньшего множества символов (где символы a и b заменены одним символом x). Код для исходного множества символов получается из кодов замещающих символов путем добавления 0 или 1 перед кодом замещающего символа, и эти два новых кода принимаются как коды заменяемых символов. Например, код символа a будет соответствовать коду x с добавленным нулем перед этим кодом, а для символа b перед кодом символа x будет добавлена единица.

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

Пример 1. Программная реализация метода Хаффмана.

#include "stdafx.h"

#include <iostream>

using namespace std;

void Expectancy();

long MinK();

void SumUp();

void BuildBits();

void OutputResult(char **Result);

void Clear();

const int MaxK = 1000;

long k[MaxK + 1], a[MaxK + 1], b[MaxK + 1];

char bits[MaxK + 1][40];

char sk[MaxK + 1];

bool Free[MaxK + 1];

char *res[256];

long i, j, n, m, kj, kk1, kk2;

char str[256];

int _tmain(int argc, _TCHAR* argv[]){

char *BinaryCode;

Clear();

cout << "Введите строку для кодирования : ";

cin >> str;

Expectancy();

SumUp();

BuildBits();

OutputResult(&BinaryCode);

cout << "Закодированная строка : " << endl;

cout << BinaryCode << endl;

system("pause");

return 0;

}

//описание функции обнуления данных в массивах

void Clear(){

for (i = 0; i < MaxK + 1; i++){

k[i] = a[i] = b[i] = 0;

sk[i] = 0;

Free[i] = true;

for (j = 0; j < 40; j++)

bits[i][j] = 0;

}

}

/*описание функции вычисления вероятности вхождения каждого символа в тексте*/

void Expectancy(){

long *s = new long[256];

for ( i = 0; i < 256; i++)

s[i] = 0;

for ( n = 0; n < strlen(str); n++ )

s[str[n]]++;

j = 0;

for ( i = 0; i < 256; i++)

if ( s[i] != 0 ){

j++;

k[j] = s[i];

sk[j] = i;

}

kj = j;

}

/*описание функции нахождения минимальной частоты символа в исходном тексте*/

long MinK(){

long min;

i = 1;

while ( !Free[i] && i < MaxK) i++;

min = k[i];

m = i;

for ( i = m + 1; i <= kk2; i++ )

if ( Free[i] && k[i] < min ){

min = k[i];

m = i;

}

Free[m] = false;

return min;

}

//описание функции подсчета суммарной частоты символов

void SumUp(){

long s1, s2, m1, m2;

for ( i = 1; i <= kj; i++ ){

Free[i] = true;

a[i] = 0;

b[i] = 0;

}

kk1 = kk2 = kj;

while (kk1 > 2){

s1 = MinK();

m1 = m;

s2 = MinK();

m2 = m;

kk2++;

k[kk2] = s1 + s2;

a[kk2] = m1;

b[kk2] = m2;

Free[kk2] = true;

kk1--;

}

}

//описание функции формирования префиксных кодов

void BuildBits(){

strcpy(bits[kk2],"1");

Free[kk2] = false;

strcpy(bits[a[kk2]],bits[kk2]);

strcat( bits[a[kk2]] , "0");

strcpy(bits[b[kk2]],bits[kk2]);

strcat( bits[b[kk2]] , "1");

i = MinK();

strcpy(bits[m],"0");

Free[m] = true;

strcpy(bits[a[m]],bits[m]);

strcat( bits[a[m]] , "0");

strcpy(bits[b[m]],bits[m]);

strcat( bits[b[m]] , "1");

for ( i = kk2 - 1; i > 0; i-- )

if ( !Free[i] ) {

strcpy(bits[a[i]],bits[i]);

strcat( bits[a[i]] , "0");

strcpy(bits[b[i]],bits[i]);

strcat( bits[b[i]] , "1");

}

}

//описание функции вывода данных

void OutputResult(char **Result){

(*Result) = new char[1000];

for (int t = 0; i < 1000 ;i++)

(*Result)[t] = 0;

for ( i = 1; i <= kj; i++ )

res[sk[i]] = bits[i];

for (i = 0; i < strlen(str); i++)

strcat( (*Result) , res[str[i]]);

}

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