13.7.2. Код Хаффмана

Лекции по Теоретическим основам цифровой связи   

13. Кодирование источника

13.7.2. Код Хаффмана

Код Хаффмана (Huffman code) [20] — это свободный от префикса код, который может давать самую короткую среднюю длину кода  для данного входного алфавита. Самая короткая средняя длина кода для конкретного алфавита может быть значительно больше энтропии алфавита источника, и тогда эта невозможность выполнения обещанного сжатия данных будет связана с алфавитом, а не с методом кодирования. Часть алфавита может быть модифицирована для получения кода расширения, и тот же метод повторно применяется для достижения лучшего сжатия. Эффективность сжатия определяется коэффициентом сжатия. Эта мера равна отношению среднего числа бит на выборку до сжатия к среднему числу бит на выборку после сжатия.

Процедура кодирования Хаффмана может применяться для преобразования между любыми двумя алфавитами. Ниже будет продемонстрировано применение процедуры при произвольном входном алфавите и двоичном выходном алфавите.

Код Хаффмана генерируется как часть процесса образования дерева. Процесс начинается с перечисления входных символов алфавита наряду с их вероятностями (или относительными частотами) в порядке убывания частоты появления. Эти позиции таблицы соответствуют концам ветвей дерева, как изображено на рис. 13.34. Каждой ветви присваивается ее весовой коэффициент, равный вероятности этой ветви. Теперь процесс образует дерево, поддерживающее эти ветви. Два входа с самой низкой относительной частотой объединяются (на вершине ветви), чтобы образовать новую ветвь с их смешанной вероятностью. После каждого объединения новая ветвь и оставшиеся ветви переупорядочиваются (если необходимо), чтобы убедиться, что сокращенная таблица сохраняет убывающую вероятность появления. Это переупорядочение называется методом пузырька [21]. Во время переупорядочения после каждого объединения поднимается ("всплывает") новая ветвь в таблице до тех пор, пока она не сможет больше увеличиваться. Таким образом, если образуется ветвь с весовым коэффициентом 0,2 и во время процесса находятся две другие ветви уже с весовым коэффициентом 0,2, новая ветвь поднимается до вершины группы с весовым коэффициентом 0,2, а не просто присоединяется к ней. Процесс "всплытия" пузырьков к вершине группы дает код с уменьшенной дисперсией длины кода, в противном случае — код с такой же средней длиной, как та, которая получена посредством простого присоединения к группе. Эта сниженная дисперсия длины кода уменьшает шанс переполнения буфера.

Рис. 13.34. Дерево кодирования Хаффмана для шестизначного множества

В качестве примера этой части процесса кодирования применим процедуру Хаффмана к входному алфавиту, изображенному на рис. 13.34. Протабулированный алфавит и связанные с ним вероятности изображены на рисунке. После формирования дерева, чтобы различать две ветви, каждая вершина ветви снабжается двоичным решением "1/0". Присвоение является произвольным, но для определенности на каждой вершине будем обозначать ветвь, идущую вверх как "1", и ветвь, идущую вниз как "0". После обозначения вершин ветвей проследим траектории дерева от основания (крайнее правое положение) до каждой выходной ветви (крайнее левое положение). Траектория — это двоичная последовательность для достижения этой ветви. В следующей таблице для каждого конца ветви указана последовательность, соответствующая каждой траектории, где i = 1,..., 6.

Находим, что средняя длина кода п для этого алфавита равна 2,4 бит на знак. Это не означает, что необходимо найти способ передачи нецелого числа бит. Это означает, что для передачи 100 входных символов через канал связи в среднем должно пройти 240 бит. Для сравнения, код фиксированной длины, требуемый для охвата шестизначного входного алфавита, должен иметь длину 3 бит и энтропию входного алфавита (используем формулу (13.32)), равную 2,32 бит. Таким образом, этот код дает коэффициент сжатия 1,25 (3,0/2,4) и достигает 96,7% (2,32/2,40) возможного коэффициента сжатия. В качестве еще одного примера рассмотрим случай, для которого можно продемонстрировать использование кода расширения. Изучим трехзначный алфавит, представленный в разделе 13.6.1.

Xi

P(Xi)

a

0.73

b

0.25

c

0.02

Дерево кода Хаффмана для этого алфавита изображено на рис. 13.35, а его элементы протабулированы ниже.

Рис. 13.35. Дерево кодирования Хаффмана для трехзначного множества

Здесь i = 1, 2, 3. Средняя длина кода в приведенном примере равна 1,31 бит; она будет равна 2 бит для кода Хаффмана фиксированной длины. Коэффициент сжатия для этого кода равен 1,53. И снова, используя равенство (13.32), получим, что энтропия для алфавита равна 0,9443 бит, так что эффективность кода (0,944/1,31 = 72%) значительно меньше, чем для предыдущего примера.

Чтобы улучшить эффективность кодирования или достичь большего сжатия, следует переопределить алфавит источника. Больший алфавит источника увеличивает разнообразие, что является одним из требований при сокращении средней длины кода и увеличении числа ветвей дерева для присвоения кода переменной длины. Это делается посредством выбора знаков (по два) из алфавита источника, которые становятся новыми знаками в расширенном алфавите. Если предположить, что .символы независимы, вероятность каждого нового элемента является произведением отдельных вероятностей. Алфавит расширения имеет следующий вид.

Здесь i — 1, ..., 9, а кодовая последовательность для каждого Xi была найдена с использованием выше приведенной процедуры Хаффмана. Коэффициент сжатия для этого кода расширения равен 2,076, а эффективность кодирования — 97,7%. Коды расширения предлагают очень мощную технологию включения эффектов множеств символов, которые не являются независимыми. Например, в английском алфавите соседние буквы являются высоко коррелированными. Очень часто встречаются следующие пары букв.

th

re

in

sh

he

e_

de

ed

s_

ng

at

r_

te

es

d_

Здесь подчеркивание представляет пробел. Наиболее общими английскими наборами трех букв являются следующие.

the

and

For

ing

ion

ess

Таким образом, вместо того чтобы производить кодирование Хаффмана отдельных букв, более эффективно расширить алфавит, включив все 1-кортежи плюс распространенные 2-и 3-кортежи, а затем произвести кодирование с помощью кода расширения.









© Банк лекций Siblec.ru
Формальные, технические, естественные, общественные, гуманитарные, и другие науки.
E-mail: formyneeds@yandex.ru