1.4. Кодирование ХаффманаКодирование Хаффмана является простым алгоритмом для построения кодов переменной длины, имеющих минимальную среднюю длину. Этот весьма популярный алгоритм служит основой многих компьютерных программ сжатия текстовой и графической информации. Некоторые из них используют непосредственно алгоритм Хаффмана, а другие берут его в качестве одной из ступеней многоуровневого процесса сжатия. Метод Хаффмана [Huffman 52] производит идеальное сжатие (то есть, сжимает данные до их энтропии), если вероятности символов точно равны отрицательным степеням числа 2. Алгоритм начинает строить кодовое дерево снизу вверх, затем скользит вниз по дереву, чтобы построить каждый индивидуальный код справа налево (от самого младшего бита к самому старшему). Начиная с работ Д.Хаффмана 1952 года, этот алгоритм являлся предметом многих исследований. (Последнее утверждение из § 3.8.1 показывает, что наилучший код переменной длины можно иногда получить без этого алгоритма.) Алгоритм начинается составлением списка символов алфавита в порядке убывания их вероятностей. Затем от корня строится дерево, листьями которого служат эти символы. Это делается по шагам, причем на каждом шаге выбираются два символа с наименьшими вероятностями, добавляются наверх частичного дерева, удаляются из списка и заменяются вспомогательным символом, представляющим эти два символа. Вспомогательному символу приписывается вероятность, равная сумме вероятностей, выбранных на этом шаге символов. Когда список сокращается до одного вспомогательного символа, представляющего весь алфавит, дерево объявляется построенным. Завершается алгоритм спуском по дереву и построением кодов всех символов. Лучше всего проиллюстрировать этот алгоритм на простом примере. Имеется пять символов с вероятностями, заданными на рис. 1.3а. Рис. 1.3. Коды Хаффмана. Символы объединяются в пары в следующем порядке: 1. 2. Осталось четыре символа, 3. Теперь имеется три символа 4. Наконец, объединяем два оставшихся символа Дерево построено. Оно изображено на рис. 1.3а, «лежа на боку», с корнем справа и пятью листьями слева. Для назначения кодов мы произвольно приписываем бит 1 верхней ветке и бит 0 нижней ветке дерева для каждой пары. В результате получаем следующие коды: 0, 10, 111, 1101 и 1100. Распределение битов по краям - произвольное. Средняя длина этого кода равна Пример: Дано 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.3а символ Если кодер просто записывает сжатый файл на диск, то дисперсия кода не имеет значения. Коды Хаффмана с малой дисперсией более предпочтительны только в случае, если кодер будет передавать этот сжатый файл по линиям связи. В этом случае, код с большой дисперсией заставляет кодер генерировать биты с переменной скоростью. Обычно данные передаются по каналам связи с постоянной скоростью, поэтому кодер будет использовать буфер. Биты сжатого файла помещаются в буфер по мере их генерации и подаются в канал с постоянной скоростью для передачи. Легко видеть, что код с нулевой дисперсией будет подаваться в буфер с постоянной скоростью, поэтому понадобится короткий буфер, а большая дисперсия кода потребует использование длинного буфера. Следующее утверждение можно иногда найти в литературе по сжатию информации: длина кода Хаффмана символа
Табл. 1.5. Пример кода Хаффмана. Длина кода символа Рис. 1.6. Код Хаффмана для английского алфавита. На рис. 1.6 показан код Хаффмана для всех 26 букв английского алфавита. Случай алфавита, в котором символы равновероятны, особенно интересен. На рис. 1.7 приведены коды Хаффмана для алфавита с 5, 6, 7 и 8 равновероятными символами. Если размер алфавита Рис. 1.7. Коды Хаффмана с равными вероятностями. Тот факт, что данные с равновероятными символами не сжимаются методом Хаффмана может означать, что строки таких символов являются совершенно случайными. Однако, есть примеры строк, в которых все символы равновероятны, но не являются случайными, и их можно сжимать. Хорошим примером является последовательность Табл. 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. Это приводит к одному кодовому биту на пиксел, то есть к восьмикратному сжатию.
|