1.4. Кодирование Хаффмана

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

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

Лучше всего проиллюстрировать этот алгоритм на простом примере. Имеется пять символов с вероятностями, заданными на рис. 1.3а.

Рис. 1.3. Коды Хаффмана.

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

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

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

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

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

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

Средняя длина этого кода равна  бит/символ. Очень важно то, что кодов Хаффмана бывает много. Некоторые шаги алгоритма выбирались произвольным образом, поскольку было больше символов с минимальной вероятностью. На рис. 1.3b показано, как можно объединить символы по-другому и получить иной код Хаффмана (11, 01, 00, 101 и 100). Средняя длина равна  бит/символ как и у предыдущего кода.

Пример: Дано 8 символов А, В, С, D, Е, F, G и H с вероятностями 1/30, 1/30, 1/30, 2/30, 3/30, 5/30, 5/30 и 12/30. На рис. 1.4а,b,с изображены три дерева кодов Хаффмана высоты 5 и 6 для этого алфавита.

Рис. 1.4. Три дерева Хаффмана для восьми символов.

Средняя длина этих кодов (в битах на символ) равна

,

,

.

Пример: На рис. 1.4d показано другое дерево высоты 4 для восьми символов из предыдущего примера. Следующий анализ показывает, что соответствующий ему код переменной длины плохой, хотя его длина меньше 4.

(Анализ.) После объединения символов А, В, С, D, Е, F и G остаются символы ABEF (с вероятностью 10/30), CDG (с вероятностью 8/30) и H (с вероятностью 12/30). Символы ABEF и CDG имеют наименьшую вероятность, поэтому их необходимо было слить в один, но вместо этого были объединены символы CDG и H. Полученное дерево не является деревом Хаффмана.

Таким образом, некоторый произвол в построении дерева позволяет получать разные коды Хаффмана с одинаковой средней длиной. Напрашивается вопрос: «Какой код Хаффмана, построенный для данного алфавита, является наилучшим?» Ответ будет простым, хотя и неочевидным: лучшим будет код с наименьшей дисперсией.

Дисперсия показывает насколько сильно отклоняются длины индивидуальных кодов от их средней величины (это понятие разъясняется в любом учебнике по статистике). Дисперсия кода 1.3а равна , а для кода 1.3b .

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

Если кодер просто записывает сжатый файл на диск, то дисперсия кода не имеет значения. Коды Хаффмана с малой дисперсией более предпочтительны только в случае, если кодер будет передавать этот сжатый файл по линиям связи. В этом случае, код с большой дисперсией заставляет кодер генерировать биты с переменной скоростью. Обычно данные передаются по каналам связи с постоянной скоростью, поэтому кодер будет использовать буфер. Биты сжатого файла помещаются в буфер по мере их генерации и подаются в канал с постоянной скоростью для передачи. Легко видеть, что код с нулевой дисперсией будет подаваться в буфер с постоянной скоростью, поэтому понадобится короткий буфер, а большая дисперсия кода потребует использование длинного буфера.

Следующее утверждение можно иногда найти в литературе по сжатию информации: длина кода Хаффмана символа  с вероятностью  всегда не превосходит . На самом деле, не смотря на справедливость этого утверждения во многих примерах, в общем случае оно не верно. Я весьма признателен Гаю Блелоку, который указал мне на это обстоятельство и сообщил пример кода, приведенного в табл. 1.5. Во второй строке этой таблицы стоит символ с кодом длины 3 бита, в то время как .

Табл. 1.5. Пример кода Хаффмана.

Длина кода символа , конечно, зависит от его вероятности . Однако она также неявно зависит от размера алфавита. В большом алфавите вероятности символов малы, поэтому коды Хаффмана имеют большую длину. В маленьком алфавите наблюдается обратная картина. Интуитивно это понятно, поскольку для малого алфавита требуется всего несколько кодов, поэтому все они коротки, а большому алфавиту необходимо много кодов и некоторые из них должны быть длинными.

Рис. 1.6. Код Хаффмана для английского алфавита.

На рис. 1.6 показан код Хаффмана для всех 26 букв английского алфавита.

Случай алфавита, в котором символы равновероятны, особенно интересен. На рис. 1.7 приведены коды Хаффмана для алфавита с 5, 6, 7 и 8 равновероятными символами. Если размер алфавита  является степенью 2, то получаются просто коды фиксированной длины. В других случаях коды весьма близки к кодам с фиксированной длиной. Это означает, что использование кодов переменной длины не дает никаких преимуществ. В табл. 1.8 приведены коды, их средние длины и дисперсии.

Рис. 1.7. Коды Хаффмана с равными вероятностями.

Тот факт, что данные с равновероятными символами не сжимаются методом Хаффмана может означать, что строки таких символов являются совершенно случайными. Однако, есть примеры строк, в которых все символы равновероятны, но не являются случайными, и их можно сжимать. Хорошим примером является последовательность , в которой каждый символ встречается длинными сериями. Такую строку можно сжать методом RLE, но не методом Хаффмана. (Буквосочетание RLE означает «run-length encoding», т.е. «кодирование длин серий». Этот простой метод сам по себе мало эффективен, но его можно использовать в алгоритмах сжатия со многими этапами, см. [Salomon, 2000).)

Табл. 1.8. Коды Хаффмана для 5 8 символов.

Заметим, что метод Хаффмана не работает в случае двухсимвольного алфавита. В таком алфавите одному символу придется присвоить код 0, а другому 1. Метод Хаффмана не может присвоить одному символу код короче одного бита. Если исходные данные (источник) состоят из индивидуальных битов, как в случае двухуровневого (монохромного) изображения, то возможно представление нескольких бит (4 или 8) в виде одного символа нового недвоичного алфавита (из 16 или 256 символов). Проблема при таком подходе заключается в том, что исходные битовые данные могли иметь определенные статистические корреляционные свойства, которые могли быть утеряны при объединении битов в символы. При сканировании монохромного рисунка или диаграммы по строкам пикселы будут чаще встречаться длинными последовательностями одного цвета, а не быстрым чередованием черных и белых. В итоге получится файл, начинающийся с 1 или 0 (с вероятностью 1/2). За нулем с большой вероятностью следует нуль, а за единицей единица. На рис. 1.9 изображен конечный автомат, иллюстрирующий эту ситуацию. Если биты объединять в группы, скажем, по 8 разрядов, то биты внутри группы будут коррелированы, но сами группы не будут иметь корреляцию с исходными пикселами. Если входной файл содержит, например, две соседние группы 00011100 и 00001110, то они будут кодироваться независимо, игнорируя корреляцию последних нулей первой группы и начальных нулей второй. Выбор длинных групп улучшает положение, но увеличивает число возможных групп, что влечет за собой увеличение памяти для хранения таблицы кодов и удлиняет время создания этой таблицы. (Напомним, что если группа длины  увеличивается до длины , то число групп растет экспоненциально с  до ).

Рис. 1.9. Конечный автомат.

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

Давид Хаффман (1925-1999)           

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

(Анализ.) Двоичная запись 127 равна 01111111, а 128 - 10000000. Половина пикселов поверхности будет нулем, а вторая половина единицей. В самом плохом случае область будет походить на шахматную доску, то есть, иметь много серий длины 1. В этом случае каждая серия требует кода в 1 бит, что ведет к одному кодовому биту на пиксел на область, или 8 кодовых битов на пиксел для всего изображения. Это приводит к полному отсутствию сжатия. А коду Хаффмана для такого изображения понадобится всего два кода (поскольку имеется всего два разных пиксела), и они могут быть длины 1. Это приводит к одному кодовому биту на пиксел, то есть к восьмикратному сжатию.