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

Кодирование Хаффмана является простым алгоритмом для построения кодов переменной длины, имеющих минимальную среднюю длину. Этот весьма популярный алгоритм служит основой многих компьютерных программ сжатия текстовой и графической информации. Некоторые из них используют непосредственно алгоритм Хаффмана, а другие берут его в качестве одной из ступеней многоуровневого процесса сжатия. Метод Хаффмана производит идеальное сжатие (то есть, сжимает данные до их энтропии) если вероятности символов точно равны отрицательным степеням числа 2[6].

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

Пример:

Пусть имеются пять отсчетов сигнала яркости с вероятностями, заданными на рис.

Отсчеты объединяются в пары в следующем порядке:

1. а4 объединяется с а5, и оба заменяются комбинированным значением а45 с вероятностью 0.2;

2. осталось четыре символа, a1с вероятностью 0.4, а также а2, а3 и а45 с вероятностями по 0.2. Произвольно выбираем а3 и а45, объединяем их и заменяем вспомогательным символом а345 свероятностью 0.4;

3. теперь имеется три символа a1, а2 и а345 с вероятностями 0.4, 0.2 и 0.4, соответственно. Выбираем и объединяем символы а2 и а345 во вспомогательный символ а2345 с вероятностью 0.6;

4. наконец, объединяем два оставшихся символа а1и а2345 и заменяем на а12345 с вероятностью 1.

Дерево построено. Оно изображено на рис. а , «лежа на боку», с корнем справа и пятью листьями слева. Для назначения кодов мы произвольно приписываем бит 1 верхней ветке и бит 0 нижней ветке дерева для каждой пары. В результате получаем следующие коды: 0, 10, 111, 1101 и 1100. Распределение битов по краям - произвольное.

Средняя длина этого кода равна 0.4 х 1 + 0.2 x 2 + 0.2 x 3 + 0.1 x 44 + 0.1 х 4 = 2.2 бит/символ. Очень важно то, что кодов Хаффмана бывает много. Некоторые шаги алгоритма выбирались произвольным образом, поскольку было больше символов с минимальной вероятностью. На рис. b показано, как можно объединить символы по-другому и получить иной код Хаффмана (11, 01, 00, 101 и 100). Средняя длина равна 0.4 х 2 + 0.2 х 2 4- 0.2 х 2 + 0.1 х 3 4- 0.1 х 3 = 2.2 бит/символ как и у предыдущего кода.

Алгоритм в лучшем случае сжимает информацию в 8 раз, в худшем случае коэффициент сжатия – 1. При кодировании требует в два раза больше времени, чем для декодирования. Но нужно помнить, что требуется также сохранять и таблицу перекодировки. Входит в состав всех известных архиваторов. Для сжатия изображения и видео как составная часть используется в таких известных алгоритмах, как JPEG, MPEG, Wavelet и др.