Методические указания к заданию 3.2

Задачу экономного кодирования сообщений источника, имеющего отличное от равномерного распределение вероятностей появления символов его алфавита, позволяют решить неравномерные префиксные коды.

Рассмотрим принцип построения таких кодов методами Шеннона-Фано и Хаффмана [2, 3]. Оба этих кода основываются на статистических свойствах источника сообщений и ставят в соответствие часто встречающимся символам алфавита короткие кодовые комбинации. Из-за того, что разным символам алфавита соответствуют кодовые комбинации разной длины, такие коды называют неравномерными.

В качестве примера возьмем сообщение: «ИНН 631300151031». Данный текст содержит избыточность, устранить которую с помощью метода RLE невозможно. Избыточность можно определить по формуле:

,

где - энтропия сообщения;

- длина кодовой комбинации при равномерном кодировании.

Энтропия сообщения вычисляется по формуле:

,

где - объем алфавита источника;

- относительная частота или вероятность появления символа в сообщении.

Относительная частота (вероятность) встречаемости символа определяется как отношение абсолютной частоты появления символа в сообщении к общей длине сообщения:

,

где - абсолютная частота (частотность) встречаемости i-ого символа алфавита источника; - объем алфавита источника.

В данном случае энтропия сообщения равна:

бит/символ,

где - относительная частота появления символа «1»;

- относительная частота появления символов «0» и «3»;

- относительная частота появления символа «Н»;

- относительная частота появления символов «5», «6», «И», « ».

При использовании равномерного кода длина кодовой комбинации определяется так:

,

где - объем алфавита источника;

- функция округления аргумента до ближайшего целого значения, большего, чем .

В данном примере бит/символ.

Избыточность сообщения при кодировании равномерным кодом равна:

.

На первом этапе построения кода Шеннона-Фано формируется модель сообщения – таблица абсолютных частот встречаемости символов.

Символ	Частота встречаемости	Символ	Частота встречаемости
		И
Н		Пробел

Для получения кодовых комбинаций строится кодовое дерево. При построении кода Шеннона-Фано дерево строится от корня к листьям. В качестве корня используется множество всех символов алфавита сообщения (рис. 1), упорядоченное по частоте встречаемости символов. Число сверху равно суммарной частоте встречаемости символов множества в исходном сообщении.

Рис. 1. Корень кодового дерева Шеннона-Фано

Затем множество символов делится на два подмножества так, чтобы новые множества имели равные, насколько это возможно, суммарные частоты встречаемости входящих в них символов. Эти подмножества соединяются с корнем дерева ветвями, становясь потомками. Левой ветви дерева присваивается бит 1, а правой ветви – 0 (рис. 2).

Рис. 2. Деление на подмножества

Полученные подмножества также рекурсивно делятся, пока не будут сформированы листья дерева – отдельные символы сообщения (рис. 3).

Кодовые комбинации (на рис. 3 они указаны в кавычках под соответствующими листьями) получаются при движении от корня дерева к кодируемому символу-листу путем сбора бит, присвоенных пройденным ветвям дерева. Запись кодовой комбинации ведут в направлении от старших бит к младшим. Например, при кодировании символа «3» сначала следует пройти по правой ветви к множеству {3, Н, 5, 6, И, Пробел } (к кодовой комбинации добавляется бит 0). Затем нужно пройти по левой ветви к множеству {3, Н} (к кодовой комбинации добавляется бит 1). Наконец, нужно пройти по левой ветви, чтобы достичь листа «3». Таким образом, получена кодовая комбинация «011».

Рис. 3. Дерево кода Шеннона-Фано

При декодировании биты считываются из входного потока и используются, как указатели направления движения по кодовому дереву от корня к искомому листу. При достижении листа найденный символ записывается в выходной поток, а движение по кодовому дереву снова начинают от корня. Например, декодирование комбинации «010» происходит следующим образом. Из потока считывается бит 0, следовательно, нужно пройти по правой ветви от корня дерева к узлу {3, Н, 5, 6, И, }. Следующий бит единичный, что требует пройти по левой ветви к множеству {3, Н}. Наконец, следующий бит 0 приводит декодер по правой ветви к листу «Н».

В следующей таблице приведены все разрешенные комбинации полученного кода Шеннона-Фано.

Закодированное сообщение будет иметь вид: «000101001000000010011110111010110011111001111». Общая длина закодированного сообщения составляет 45 бит.

Средняя длина кодовой комбинации равна:

бит/символ.

Избыточность сообщения после применения кода Шеннона-Фано снизилась до значения:

.

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