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

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

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

Рис. 4.2.1. Абсолютные частоты появления букв в книге [1]

Из-за того, что разным символам алфавита соответствуют кодовые комби-нации разной длины, такие коды называют неравномерными.

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

L 1 ^H 100% ,n

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

n - длина кодовой комбинации при равномерном кодировании. Энтропия сообщения вычисляется по формуле:

где N - объем алфавита источника (для русского алфавита N =33);

p_i-относительная частота(вероятность)появления символа в сообщении.Относительная частота встречаемости символа определяется как отноше-

ние абсолютной частоты появления символа в сообщении к общей длине сооб-щения (числу символов в сообщении):

p_{i m}ⁱ,

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

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

11

_______________________________________________________________________________

Пробел.

При необходимости расчета логарифма по основанию два через логарифм по основанию десять можно воспользоваться соотношением:

При использовании равномерного кода (например, СР-1251) длина кодо-вой комбинации определяется так:

n log₂N,

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

меньшего, чем x .

В данном примере n log ₂ 8 3бита.

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

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

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

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

Затем множество символов делят на два подмножества так, чтобы новые множества имели равные, насколько это возможно, суммарные частоты встре-

12

_______________________________________________________________________________

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

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

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

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

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

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

13

_______________________________________________________________________________

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

Закодированное сообщение будет иметь вид:

000101001000000010011110111010110011111001111

Общая длина закодированного сообщения составляет 45 бит.

Средняя длина кодовой комбинации равна (напомним, что число символов в сообщении – 16):

n ⁴⁵ 2,813 бит/символ.

16

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

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