Шаг 10.
Теоретическая информатика. Кодирование информации в теории Шеннона.
Алфавитное неравномерное двоичное кодирование. Код Хаффмана

    На этом шаге мы рассмотрим алфавитное неравномерное двоичное кодирование; префиксный код; код Хаффмана.

    Данный случай относится к варианту (2). При этом как следует из названия, символы некоторого первичного алфавита (например, русского) кодируются комбинациями символов двоичного алфавита (т.е. 0 и 1), причем, длина кодов и, соответственно, длительность передачи отдельного кода, могут различаться. Длительности элементарных сигналов при этом одинаковы (0 = 1 = ). За счет чего можно оптимизировать кодирование в этом случае? Очевидно, суммарная длительность сообщения будет меньше, если применить следующий подход: тем буквам первичного алфавита, которые встречаются чаще, присвоить более короткие по длительности коды, а тем, относительная частота которых меньше – коды более длинные. Но длительность кода – величина дискретная, она кратна длительности сигнала передающего один символ двоичного алфавита. Следовательно, коды букв, вероятность появления которых в сообщении выше, следует строить из возможно меньшего числа элементарных сигналов. Построим кодовую таблицу для букв русского алфавита, основываясь на приведенных ранее вероятностях появления отдельных букв.

    Очевидно, возможны различные варианты двоичного кодирования, однако, не все они будут пригодны для практического использования – важно, чтобы закодированное сообщение могло быть однозначно декодировано, т.е. чтобы в последовательности 0 и 1, которая представляет собой многобуквенное кодированное сообщение, всегда можно было бы различить обозначения отдельных букв. Проще всего этого достичь, если коды будут разграничены разделителем – некоторой постоянной комбинацией двоичных знаков. Условимся, что разделителем отдельных кодов букв будет последовательность 00 (признак конца знака), а разделителем слов – 000 (признак конца слова – пробел). Довольно очевидными оказываются следующие правила построения кодов:

    Длительность передачи каждого отдельного кода ti, очевидно, может быть найдена следующим образом: ti = ki , где ki – количество элементарных сигналов (бит) в коде символа i. В соответствии с приведенными выше правилами получаем следующую таблицу кодов:

Таблица 1. Таблица кодов
Буква Код pi·103 ki Буква Код pi·103 ki
пробел 000 174 3 я 1011000 18 7
о 100 90 3 ы 1011100 16 7
е 1000 72 4 з 1101000 16 7
а 1100 62 4 ь,ъ 1101100 14 7
и 10000 62 5 б 1110000 14 7
т 10100 53 5 г 1110100 13 7
н 11000 53 5 ч 1111000 12 7
с 11100 45 5 й 1111100 10 7
р 101000 40 6 х 10101000 9 8
в 101100 38 6 ж 10101100 7 8
л 110000 35 6 ю 10110000 6 8
к 110100 28 6 ш 10110100 6 8
м 111000 26 6 ц 10111000 4 8
д 111100 25 6 щ 10111100 3 8
п 1010000 23 7 э 11010000 3 8
у 1010100 21 7 ф 11010100 2 8

    Теперь по формуле можно найти среднюю длину кода K(2) для данного способа кодирования:

    Поскольку для русского языка, I1(r)=4,356 бит, избыточность данного кода, согласно (2), составляет:

Q(r) = 1 - 4,356/4,964 0,122;

это означает, что при данном способе кодирования будет передаваться приблизительно на 12% больше информации, чем содержит исходное сообщение. Аналогичные вычисления для английского языка дают значение K(2) = 4,716, что при I1(e) = 4,036 бит приводят к избыточности кода Q(e) = 0,144.

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

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

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

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


    Пример 1. Пусть имеется следующая таблица префиксных кодов:

Таблица 2. Таблица кодов
а л м р у ы
10 010 00 11 0110 0111

    Требуется декодировать сообщение: 00100010000111010101110000110.

    Декодирование производится циклическим повторением следующих действий.

  1. Отрезать от текущего сообщения крайний левый символ, присоединить к рабочему кодовому слову.
  2. Сравнить рабочее кодовое слово с кодовой таблицей; если совпадения нет, перейти к (1).
  3. Декодировать рабочее кодовое слово, очистить его.
  4. Проверить, имеются ли еще знаки в сообщении; если "да", перейти к (1).

    Применение данного алгоритма дает:

    Доведя процедуру до конца, получим сообщение: "мама мыла раму".

    Таким образом, использование префиксного кодирования позволяет делать сообщение более коротким, поскольку нет необходимости передавать разделители знаков. Однако условие Фано не устанавливает способа формирования префиксного кода и, в частности, наилучшего из возможных.

    Способ оптимального префиксного двоичного кодирования был предложен Д.Хаффманом. Построение кодов Хаффмана мы рассмотрим на следующем примере: пусть имеется первичный алфавит A, состоящий из шести знаков a1, ..., a6 с вероятностями появления в сообщении, соответственно, 0,3; 0,2; 0,2; 0,15; 0,1; 0,05. Создадим новый вспомогательный алфавит A1, объединив два знака с наименьшими вероятностями (a5 и a6) и заменив их одним знаком (например, a(1)); вероятность нового знака будет равна сумме вероятностей тех, что в него вошли, т.е. 0,15; остальные знаки исходного алфавита включим в новый без изменений; общее число знаков в новом алфавите, очевидно, будет на 1 меньше, чем в исходном. Аналогичным образом продолжим создавать новые алфавиты, пока в последнем не останется два знака; ясно, что число таких шагов будет равно N – 2, где N – число знаков исходного алфавита (в нашем случае N = 6, следовательно, необходимо построить 4 вспомогательных алфавита). В промежуточных алфавитах каждый раз будем переупорядочивать знаки по убыванию вероятностей. Всю процедуру построения представим в виде таблицы:

    Теперь в обратном направлении поведем процедуру кодирования. Двум знакам последнего алфавита присвоим коды 0 и 1 (которому какой – роли не играет; условимся, что верхний знак будет иметь код 0, а нижний – 1). В нашем примере знак a1(4) алфавита A(4), имеющий вероятность 0,6 , получит код 0, а a2(4) с вероятностью 0,4 – код 1. В алфавите A(3) знак a1(3) с вероятностью 0,4 сохранит свой код (1); коды знаков a2(3) и a3(3), объединенных знаком a1(4) с вероятностью 0,6 , будут уже двузначным: их первой цифрой станет код связанного с ними знака (т.е. 0), а вторая цифра – как условились – у верхнего 0, у нижнего – 1; таким образом, a2(3) будет иметь код 00, а a3(3) – код 01. Полностью процедура кодирования представлена в следующей таблице:

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

    K(2) = 0,3·2+0,2·2+0,2·2+0,15·3+0,1·4+0,05·4 = 2,45.

    Для сравнения можно найти I1(A)  – она оказывается равной 2,409, что соответствует избыточности кода Q = 0,0169, т.е. менее 2%.

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

    Применение описанного метода для букв русского алфавита дает следующие коды:

Таблица 3. Таблица кодов русских букв
Буква Код pi·103 ki Буква Код pi·103 ki
пробел 000 174 3 я 0011001 18 6
о 111 90 3 ы 0101100 16 6
е 0100 72 4 з 010111 16 6
а 0110 62 4 ь,ъ 100001 14 6
и 0111 62 4 б 101100 14 6
т 1001 53 4 г 101101 13 6
н 1010 53 5 ч 110011 12 6
с 1101 45 4 й 0011001 10 7
р 00101 40 5 х 1000000 9 7
в 00111 38 5 ж 1000001 7 7
л 01010 35 5 ю 1100101 6 7
к 10001 28 5 ш 00110000 6 8
м 10111 26 5 ц 11001000 4 8
д 11000 25 5 щ 11001001 3 8
п 001000 23 6 э 001100010 3 9
у 001001 21 6 ф 001100011 2 9

    Средняя длина кода оказывается равной K(2) = 4,395; избыточность кода Q(r) = 0,00887, т.е. менее 1%.

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

    На следующем шаге мы рассмотрим равномерное алфавитное двоичное кодирование; байтовый код.




Предыдущий шаг Содержание Следующий шаг