Кодирование. Пример 3.1.

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

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

00100010000111010101110000110

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

(a) отрезать от текущего сообщения последний левый знак, присоединить справа к рабочему кодовому слову;

(b) сопоставить рабочее кодовое слово с кодовой таблицей; если совпадения нет, перейти к (а);

(c) декодировать рабочее кодовое слово, очистить его;

(d) проверить, имеются ли еще знаки в сообщении; если «да», перейти к (а).

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

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

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

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

Данный вариант кодировки был предложен в 1948-1949 гг. независимо Р. Фано и К. Шенноном и по этой причине назван по их именам. Разглядим схему на последующем примере: пусть имеется первичный алфавит А, состоящий из 6 символов а₁ …а₆ с вероятностями возникновения в сообщении, соответственно, 0,3; 0,2; 0,2; 0,15; 0,1; 0,05. Расположим эти знаки в таблице в порядке убывания вероятностей (см. табл. 3.2). Разделим знаки на две группы таким макаром, чтоб суммы вероятностей в каждой из их могли быть примерно равными. В нашем примере в первую группу попадут a₁ и а₂ с суммой вероятностей 0,5 — им присвоим 1-ый символ кода «0». Сумма вероятностей для других 4 символов также 0,5; у их 1-ый символ кода будет «1». Продолжим деление каждой из групп на подгруппы по этой же схеме, т.е. так, чтоб суммы вероятностей на каждом шаге в примыкающих подгруппах могли быть может быть более близкими. В итоге получаем:

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

I₁^(A) = 2,390 бит. Подставляя обозначенные значения в (3.5), получаем избыточность кода Q(A,2) = 0,0249, т.е. около 2,5%. Но, данный код нельзя считать хорошим, так как вероятности возникновения 0 и 1 неодинаковы (0,35 и 0,65, соответственно). Применение изложенной схемы построения к русскому алфавиту дает избыточность кода 0,0147.

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

Метод рационального префиксного двоичного кодировки был предложен Д. Хаффманом. Построение кодов Хаффмана мы разглядим на том же примере. Сделаем новый вспомогательный алфавит A₁, объединив два знака с меньшими вероятностями (а₅ и а₆) и заменив их одним знаком (к примеру, а⁽¹⁾); возможность нового знака будет равна сумме вероятностей тех, что в него вошли, т.е. 0,15; другие знаки начального алфавита включим в новый без конфигураций; общее число символов в новеньком алфавите, разумеется, будет на 1 меньше, чем в начальном. Аналогичным образом продолжим создавать новые алфавиты, пока в последнем не остается два знака; ясно, что количество таких шагов будет равно N — 2, где N — число символов начального алфавита (в нашем случае N = 6, как следует, нужно выстроить 4 вспомогательных алфавита). В промежных алфавитах всякий раз будем переупорядочивать знаки по убыванию вероятностей. Всю функцию построения представим в виде таблицы:

Сейчас в оборотном направлении проведем функцию кодировки. Двум знакам последнего алфавита присвоим коды 0 и 1 (которому какой — роли не играет; условимся, что верхний символ будет иметь код 0, а нижний — 1). В нашем примере символ а₁⁽⁴⁾ алфавита A⁽⁴⁾, имеющий возможность 0,6, получит код 0, а a₂⁽⁴⁾ с вероятностью 0,4 — код 1. В алфавите А⁽³⁾ символ a₁⁽³⁾ получает от a₂⁽⁴⁾ его возможность 0,4 и код (1); коды символов a₂⁽³⁾ и a₃⁽³⁾, происходящие от знака a₁⁽⁴⁾ с вероятностью 0,6, будут уже двузначным: их первой цифрой станет код их «родителя» (т.е. 0), а 2-ая цифра — как договорились — у верхнего 0, у нижнего — 1; таким макаром, a₂⁽³⁾ будет иметь код 00, а a₃⁽³⁾ — код 01. Стопроцентно процедура кодировки представлена в таблице, приведенной на с.70.

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

К(А,2) = 0,3 ∙ 2 + 0,2 ∙ 2 + 0,2 ∙ 2 +0,15 ∙ 3 + 0,1 ∙ 4 + 0,05 ∙ 4 = 2,45.

Избыточность опять оказывается равной Q(A, 2) = 0,0249, но, вероятности 0 и 1 сблизились (0,47 и 0,53, соответственно). Более высочайшая эффективность кодов Хаффмана по сопоставлению с кодами Шеннона-Фано становится тривиальной, если сопоставить избыточности кодов для какого-нибудь естественного языка. Применение описанного способа для букв российского алфавита порождает коды, выставленные в табл. 3.2. (для удобства сравнения они приведены в формате табл. 3.1).

Таблица 3.2

Средняя длина кода оказывается равной К(r,2) = 4,395; избыточность кода Q(r,2) = 0,0090, т.е. не превосходит 1 %, что приметно меньше избыточности кода Шеннона-Фано (см. выше).

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

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