Рівномірне алфавітне двійкове кодування
Пример 1.
Неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с началом (префиксом*) какого-либо иного более длинного кода.
* В языковедении термин «префикс» означает «приставка».
Например, если имеется код , то уже не могут использоваться коды и пр. Если условие Фано выполняется, то при прочтении (расшифровке) закодированного сообщения путем сопоставления с таблицей кодов всегда можно точно указать, где заканчивается один код и начинается другой.
Пусть имеется следующая таблица префиксных кодов:
Требуется декодировать сообщение:
Декодирование производится циклическим повторением следующих действий:
(a) отрезать от текущего сообщения крайний левый символ, присоединить справа к рабочему кодовому слову;
(b) сравнить рабочее кодовое слово с кодовой таблицей; если совпадения нет, перейти к (а);
(c) декодировать рабочее кодовое слово, очистить его;
(d) проверить, имеются ли еще знаки в сообщении; если «да», перейти к (а).
Применение данного алгоритма дает:
Доведя процедуру до конца, получим сообщение: «мам********».
Таким образом, использование префиксного кодирования позволяет делать сообщение более коротким, поскольку нет необходимости передавать разделители знаков. Однако условие Фано не устанавливает способа формирования префиксного кода и, в частности, наилучшего из возможных. Мы рассмотрим две схемы построения префиксных кодов.
Префиксный код Шеннона-Фано
Данный вариант кодирования был предложен в 1948-1949 гг. независимо Р. Фано и К. Шенноном и по этой причине назван по их именам. Рассмотрим схему на следующем примере: пусть имеется первичный алфавит , состоящий из шести знаков с вероятностями появления в сообщении, соответственно, .
Расположим эти знаки в таблице в порядке убывания вероятностей (см. табл. 2). Разделим знаки на две группы таким образом, чтобы суммы вероятностей в каждой из них были бы приблизительно равными.
В нашем примере в первую группу попадут и с суммой вероятностей - им присвоим первый знак кода . Сумма вероятностей для остальных четырех знаков также 0,5; у них первый знак кода будет "1".
Продолжим деление каждой из групп на подгруппы по этой же схеме, т.е. так, чтобы суммы вероятностей на каждом шаге в соседних подгруппах были бы возможно более близкими. В результате получаем:
Из процедуры построения кодов легко видеть, что они удовлетворяют условию Фано и, следовательно, код является префиксным. Средняя длина кода равна:
. Подставляя указанные значения в (5), получаем избыточность кода , т.е. около 2,5%. Однако, данный код нельзя считать оптимальным, поскольку вероятности появления неодинаковы (0,35 и 0,65, соответственно). Применение изложенной схемы построения к русскому алфавиту дает избыточность кода .
Префиксный код Хаффмана[1] (David Albert Huffman)
Способ оптимального префиксного двоичного кодирования был предложен Д. Хаффманом. Построение кодов Хаффмана мы рассмотрим на том же примере.
1. создадим новый вспомогательный алфавит , объединив два знака с наименьшими вероятностями ( ) и заменив их одним знаком (например, );
2. вероятность нового знака будет равна сумме вероятностей тех, что в него вошли, т.е. ;
3. остальные знаки исходного алфавита включим в новый без изменений;
4. общее число знаков в новом алфавите, очевидно, будет на меньше, чем в исходном;
5. аналогичным образом продолжим создавать новые алфавиты, пока в последнем не останется два знака.
Количество таких шагов будет равно , где - число знаков исходного алфавита (в нашем случае , следовательно, необходимо построить вспомогательных алфавита). В промежуточных алфавитах каждый раз будем переупорядочивать знаки по убыванию вероятностей. Всю процедуру построения представим в виде таблицы:
Теперь в обратном направлении проведем процедуру кодирования.
Двум знакам последнего алфавита присвоим коды (которому какой - роли не играет; условимся, что верхний знак будет иметь код 0, а нижний - 1).
В нашем примере знак а1(4)алфавита A(4), имеющий вероятность 0,6, получит код 0, а a2(4)с вероятностью 0,4 - код 1.
В алфавите А(3)знак a1(3) получает от a2(4) его вероятность 0,4 и код (1);
коды знаков a2(3) и a3(3), происходящие от знака a1(4) с вероятностью 0,6, будут уже двузначным: их первой цифрой станет код их «родителя» (т.е. 0), а вторая цифра - как условились - у верхнего 0, у нижнего - 1; таким образом, a2(3)будет иметь код 00, а a3(3) - код 01. Полностью процедура кодирования представлена в таблице:
Из процедуры построения кодов вновь видно, что они удовлетворяют условию Фано и, следовательно, не требуют разделителя. Средняя длина кода, как и в предыдущем примере оказывается:
Избыточность снова оказывается равной , однако, вероятности сблизились ( , соответственно). Более высокая эффективность кодов Хаффмана по сравнению с кодами Шеннона-Фано становится очевидной, если сравнить избыточности кодов для какого-либо естественного языка. Применение описанного метода для букв русского алфавита порождает коды, представленные в табл. 2. (для удобства сопоставления они приведены в формате табл. 1).
Таблица 2
Средняя длина кода оказывается равной ; избыточность кода , т.е. не превышает 1%, что заметно меньше избыточности кода Шеннона-Фано (см. выше).
Код Хаффмана важен в теоретическом отношении, поскольку можно доказать, что он является самым экономичным из всех возможных, т.е. ни для какого метода алфавитного кодирования длина кода не может оказаться меньше, чем код Хаффмана (см.[3, с.209-211]).
Таким образом, можно заключить, что существует способ построения оптимального неравномерного алфавитного кода. Не следует думать, что он представляет чисто теоретический интерес. Метод Хаффмана и его модификация - метод адаптивного кодирования (динамическое кодирование Хаффмана) - нашли широчайшее применение в программах-архиваторах, программах резервного копирования файлов и дисков, в системах сжатия информации в модемах.
В этом случае двоичный код первичного алфавита строится цепочками равной длины, т.е. со всеми знаками связано одинаковое количество информации равное . Формировать признак конца знака не требуется, поэтому для определения длины кода можно воспользоваться формулой . Приемное устройство просто отсчитывает оговоренное заранее количество элементарных сигналов и интерпретирует цепочку (устанавливает, какому знаку она соответствует), соотнося ее с таблицей кодов. Правда, при этом недопустимы сбои, например, пропуск (непрочтение) одного элементарного сигнала приведет к сдвигу всей кодовой последовательности и неправильной ее интерпретации; решается проблема путем синхронизации передачи или иными способами. С другой стороны, применение равномерного кода оказывается одним из средств контроля правильности передачи, поскольку факт поступления лишнего элементарного сигнала или, наоборот, поступление неполного кода сразу интерпретируется как ошибка.