|
Читайте также: |
Метод Хаффмана производит идеальное сжатие (то есть сжимает данные до их энтропии), если вероятности символов точно равны отрицательным степеням 2. Алгоритм начинается с составлении списка символов алфавита в порядке убывания их вероятности. Затем от корня строится дерево, листьями которого являются эти символы. Это делается по шагам, причём на каждом шаге выбираются два символа с наименьшими вероятностями, добавляются наверх частичного дерева, удаляются из списка и заменяются вспомогательным символом, представляющим эти два символа. Вспомогательному символу приписывается вероятность, равная сумме вероятностей выбранных на данном шаге символов. Когда список сокращается до одного вспомогательного символа, представляющего весь алгоритм, дерево объявляется построенным. Завершается алгоритм спуском по дереву и построением кодов всех символов.
Приведём пример. Пусть имеется алфавит из пяти символов a 1, a 2, a 3, a 4, a 5 с вероятностями соответственно 0,4, 0,2, 0,2, 0,1, 0,1. Символы объединяются в пары в следующем порядке:
1) a 4 объединяется с a 5, после чего оба символа заменяются комбинированным символом a 45 с вероятностью 0,2;
2) наименьшую вероятность имеют теперь символы a 2, a 3, a 45; произвольно выбираем a 3 и a 45, объединяем их и заменяем вспомогательным символом a 345 c вероятностью 0,4;
3) теперь имеется три символа a 1, a 2, a 345 с вероятностями 0,4, 0,2 и 0,4, поэтому выбираем и объединяем символы a 2 и a 345 в вспомогательный символ a 2345 с вероятностью 0,6;
4) объединяем два оставшихся символа a 1 и a 2345 и заменяем на a 12345 с вероятностью 1.
Дерево построено. Полученное дерево приведено на рис.12.1а. Для назначения кодов произвольно приписываем бит 1 верхней ветке и бит 0 нижней ветке дерева для каждой пары. Получаем следующие коды: 1, 01, 111, 1101, 1100.
| 
|
| а | б |
| Рис.12.1. Деревья кодов Хаффмана |
Средняя длина кода равна 0,4∙1+0,2∙2+0,2∙3+0,1∙4+0,1∙5 = 2,2 бит/символ. Важно то, что кодов Хаффмана может быть много. Некоторые шаги алгоритма выбирались произвольно, поскольку было несколько символов с минимальной вероятностью. На рис.12.1б показано, как можно объединить символы по-другому и и получить иной код Хаффмана (11, 01, 00, 101, 100). Средняя длина этого кода также равна 2,2 бит/символ.
Следовательно, некоторый произвол в построении дерева позволяет получать разные коды Хаффмана с одинаковой средней длиной. Из всех возможных кодов следует выбирать код с наименьшей дисперсией. Дисперсия показывает, насколько сильно отклоняются длины индивидуальных кодов от их средней длины. Для кода 12.1а дисперсия равна
D = 0,4(1-2,2)2+0,2(2-2,2)2+0,2(3-2,2)2+0,1(4-2,2)2+0,1(4-2,2)2 = 1,36,
а для кода 12.1б:
D = 0,4(2-2,2)2+0,2(2-2,2)2+0,2(2-2,2)2+0,1(3-2,2)2+0,1(3-2,2)2 = 0,16.
Поэтому код 12.1б является предпочтительным. По деревьям кодов можно понять, как выбрать нужный путь построения кода. На рис.12.1а символ a 45 сливается с символом a 3, в то время как на рис.12.1б он сливается с a 1. Правило будет такое: когда на дереве имеется более двух узлов с наименьшими вероятностям, следует объединять символы с наибольшей и наименьшей вероятностью – это сокращает общую дисперсию кода.
Если кодер просто записывает сжаты данные на диск, то дисперсия кода не имеет значения. Коды Хаффмана с малой дисперсией предпочтительны только в том случае, если сжатый файл будет передаваться по линиям связи. В этом случае код с большой дисперсией заставляет кодер генерировать биты с переменной скоростью. Обычно данные передаются по каналам связи с постоянной скоростью, поэтому кодер будет использовать буфер. Биты сжатого файла помещаются в буфер по мере их генерации и подаются в канал с постоянной скоростью для передачи. Легко видеть, что код с нулевой дисперсией будет подаваться в буфер с постоянной скоростью, поэтому понадобится короткий буфер, а большая дисперсия кода потребует использования длинного буфера.
Рассмотрим алфавит, в котором все символы равновероятны. Дерево кодирования для такого алфавита из пяти символов приведено на рис.12.2. Видно, что получившийся код (0, 111, 110, 101, 100) очень близок к коду фиксированной длины. Если бы количество символов в алфавите было бы степенью 2, то в результате кодирования получился бы код фиксированной длины. Получается, что применение метода Хаффмана для кодирования равновероятных символов практически не приносит выигрыша.
|
| Рис. 12.2. Дерево кодирования для равновероятных символов |
Метод Хаффмана не работает и в случае двухсимвольного алфавита. В таком алфавите одному символу придётся присвоить код 0, а другому – код 1. Метод Хаффмана не может присвоить одному символу код короче одного бита. Если исходные данные состоят из индивидуальных битов (как в случае монохромного изображения) то возможно представление нескольких бит (4 или 8) в виде одного символа нового недвоичного алфавита (из 16 или 256 символов).
Дата добавления: 2015-01-05; просмотров: 45 | Поможем написать вашу работу | Нарушение авторских прав |