4.2.2 Префиксное неравномерное кодирование

Возможно ли такое кодирование, которое не использует разделители? Существует ли оптимальный способ неравномерного двоичного кодирования?

Суть первого вопроса состоит в нахождении такого варианта кодирования, при котором последующее выделение из него каждого отдельного знака оказывается однозначным без специальных указателей разделения знаков.

Наиболее простыми и употребимыми кодами такого типа являются так называемые префиксные коды, которые удовлетворяют следующему условию Фано.

Неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с началом (префиксом) какого-либо иного более длинного кода.

Например, если имеется код 110, то уже не могут использоваться коды 11, 1, 1101, 11001, и т.п.

Если условие Фано выполняется, то при прочтении (расшифровке) закодированного сообщения путем сопоставления с таблицей кодов всегда можно точно указать, где заканчивается один код и начинается другой.

Наиболее известны 2 схемы построения префиксных кодов.

Префиксный код Шеннона – Фано

Данный вариант кодирования был предложен в 1948 – 49 гг. независимо Р. Фано и К. Шенноном. Рассмотрим его на примере.

Пусть имеется первичный алфавит А, состоящий из 6 знаков (а1, … а6) с вероятностями появления (0.30, 0.20, 0.20, 0.15, 0.10, 0.05) соответственно. Расположим эти знаки в таблице в порядке уменьшения вероятностей. Разделим на 2 группы таким образом, чтобы суммы вероятностей в каждой из них были примерно равными (таблица 4.2), шаг 1.

Таблица 4.2 Код Шеннона-Фано

Знак	Вер-сть	1 шаг	2 шаг	3 шаг	4 шаг	Код
а1	0.30	0	0			00
а2	0.20	0	1			01
а3	0.20	1	0			10
а4	0.15	1	1	0		110
а5	0.10	1	1	1	0	1110
а6	0.05	1	1	1	1	1111

В нашем примере в первую группу попадут а1, а2 (сумма вероятностей 0.5), во вторую – все остальные символы. Первый знак кода для 1-ой группы будет «0», для второй – «1».

Продолжим деление каждой из групп на подгруппы по этой же схеме (т.е., чтобы суммы вероятностей на каждом шаге в соседних подгруппах были бы возможно более близкими). Окончательные коды приведены в таблице 3.1 в последнем столбце.

Из процедуры построения кодов легко видеть, что они удовлетворяют условию Фано, и код является префиксным.

Средняя длина кода равна:

2*(0.30+0.20+0.20)+3*0.15+4*(0.10+0.05)=2.45 .

Среднее количество информации на знак

I =  =2.390.

Избыточность данного кода:

= =0.0249 (всего 2.5%!).

Применительно к русскому языку такой код дает избыточность 0.0147%!

Однако данный код не является оптимальным, так как вероятности знаков (0 и 1) не одинаковы  и соответственно.

Префиксный код Хаффмана

Способ оптимального префиксного двоичного кодирования был предложен Д. Хаффманом.

Рассмотрим построение кода Х на вышеприведенном примере.

Дан первичный алфавит из 6 символов А=(а1, а2, а3, а4, а5, а6) с вероятностями (0.30, 0.20, 0.20, 0.15, 0.10, 0.05) соответственно.

Создадим новый алфавит А1, объединив 2 знака с наименьшими вероятностями (а5, а6), и заменив их новым знаком а(1). Вероятность нового знака равна сумме вероятностей тех знаков, что в него вошли, то есть 0.15. остальные знаки алфавита включим в новый без изменений. Общее число знаков будет на 1 меньше, чем в исходном.

Аналогичным образом продолжим создавать новые алфавиты, пока в последнем на останется 2 знака. Очевидно, что количество шагов будет равно (N-2), где N – число знаков исходного алфавита.

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

Всю процедуру построения представим в виде таблицы 4.3.

Таблица 4.3. Промежуточные алфавиты

№ знака	Исх. алф-т А	А(1)	А(2)	А(3)	А(4)
1	0 .3	0 .3	0 .3	0 .4	0.6
2	0 .2	0 .2	0 .3	0 .3	0.4
3	0 .2	0 .2	0 .2	0.3
4	0.15	0 .15	0.2
5	0 .10	0.15
6	0.05

Теперь в обратном направлении (против стрелок) проведем процедуру кодирования. Двум знакам последнего алфавита присвоим коды 0 и 1 (которому какой – роли не играет; например, условимся, что верхнему – 0, а нижнему –1). Процесс кодирования представлен в таблице 4.4.

Таблица 4.4 Построение кода Хаффмана

№ знака	Исх. алф-т А		А(1)		А(2)		А(3)		А(4)
	вер-сть	коды	вер-сть	коды	вер-сть	коды	вер-сть	коды	вер-сть	коды
1	0.30	0 0	0 .3	0 0	0.3	0 0	0.4	1	0.6	0
2	0.20	1 0	0 .2	1 0	0 .3	0 1	0.3	0 0	0.4	1
3	0.20	1 1	0 .2	1 1	0 .2	10	0.3	01
4	0.15	0 10	0 .15	010	0 .2	11
5	0.10	0 110	0 .15	011
6	0.05	0111

Средняя длина кода, как и в предыдущем примере, равна:

2*(0.30+0.20+0.20)+3*0.15+4*(0.10+0.05)=2.45.

Избыточность также равна 0.0249. Однако вероятности 0 и 1 сблизились (0.47 и 0.53 соответственно).

Более высокая эффективность кодов Хаффмана по сравнению с кодами Шеннона-Фано становится очевидной, если сравнить избыточность кодов для естественного языка. Так, для русского языка средняя длина кода К(ru, 2)=4.395, избыточность кода Q(ru,2)=0.0090, т.е. не превышает 1%, что заметно меньше избыточности кода Шеннона-Фано.

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

Метод Хаффмана и его модификация – метод адаптивного кодирования (динамическое кодирование Хаффмана) – нашли широкое применение в программах-архиваторах, программах резервного копирования файлов и дисков, в системах сжатия информации в модемах и факсах.