Статистическое компрессирование аудио сигналов. Вологдин Э.И. - 25 стр.

UptoLike

ВУЗ: 

СПбГУТ | Санкт-Петербург

Составители: 

Рубрика: 

25
Объединяются два символа алфавита с наименьшими вероятностями
4
a
и
5
a
, и
создается вспомогательный символ
45
a
, которому приписывается вероятность 0,2,
равная сумме вероятностей выбранных символов. Далее этот новый символ уча-
ствует на равных в построении дерева.
Объединяются следующие два символа алфавита с наименьшими вероятностями
3
a
и
45
a
, (из них один новый), и создается вспомогательный символ
345
a
. Ему
приписывается вероятность 0,4 , равная сумме вероятностей выбранных символов .
Объединяются два символа алфавита с наименьшими вероятностями
2
a
и
345
a
, , и
создается вспомогательный символ
2345
a
. Ему приписывается вероятность 0,6, рав-
ная сумме вероятностей выбранных символов .
Наконец объединяются два оставшихся символа
1
a
и
2345
a
, заменяем их
вспомогательным символом
12345
a
с вероятностью 1. Это корень дерева.
Для создания кодовых комбинаций символов произвольно приписываем 1 бит верхней
ветке и 0 бит нижней ветке дерева для каждой пары ветвей дерева. В результате по-
лучаем следующие коды: 0, 10, 111, 1101 и 1100 . Средняя длина этого кода 2,2 бита на
символ, а энтропия равна 2,12 бита на символ.
Некоторый произвол в построении дерева позволяет получить множество кодов
Хаффмана с одинаковой средней длиной. На рис.22 показано, как можно объединить
символы по другому алгоритму и получить иной код Хаффмана. Средняя длина этого ко-
да также равна 2,2 бит/символ, но лучшим является код с наименьшей дисперсией. Дис-
персия показывает, насколько сильно откланяется длина кодовых комбинаций
от сред-
него значения
L
и рассчитывается по формуле
2
1
()
n
ii
i
D p l L
. (22)
Дисперсия кода на рис.22.а) равна 1,36 , а дисперсия кода на рис.22.в) существенно
меньше, и равна 0,16 . Когда на дереве имеются более двух символов с наименьшей ве-
роятностью, следует объединять символы с наибольшей и наименьшей вероятностью, это
сокращает общую дисперсию кода .
Интересен результат преобразования обычного двоичного 8-разрядного кода с алфа-
витом из 256 символов длиной 8 бит (байт) в код Хаффмана. При этом в кодовую таблицу
входят:
4 - 2 разрядных кода;
8 - 3 разрядных кодов;
16 - 4 разрядных кодов;
32 - 5 разрядных кода;
64 - 6 разрядных кодов;
128 - 7 разрядных кодов;
2 - 8 разрядных кода.
В итоге мы имеем также 256 различных комбинаций, которыми можно кодировать
байт. Из этих комбинаций лишь 2 по длине равны 8 битам. Если мы сложим число битов,
которые представляют все эти кодовые комбинации, то в итоге получим 1554 бит или 195
байтов. Так в результате кодирования 256 байт сжаты до 195, и получен выигрыш макси-
мально 33%, это без учета информации, находящейся в таблице кодирования. Некоторые
кодовые комбинации , такие как 10000000 и 01111111, сжимаются в 4 раза.
Заметим, что если символы алфавита равновероятны, то применение кодов перемен-
ной длины не дает никаких преимуществ. Это объясняется тем, что при размере алфави-
та, определяемого значением
2
n
, получаются коды фиксированной длины. В других слу-
чаях коды весьма близки к кодам с фиксированной длиной. В табл.4. в качестве примера
приведены средняя длина и дисперсии таких кодов Хаффмана с алфавитом от 5 до 8 сим-

Страницы