Оптимальное кодирование
Теорема кодирования Шеннона. Методы побуквенного оптимального кодирования. Критерии оптимальности кода. Блочное кодирование. Единая система кодирования текстовой информации.
Кодирование , минимизирующее избыточность кода , называется оптимальным .
Вопрос существования таких кодов составляет суть одной из основных теорем теории информации – теоремы кодирования, доказанной К. Шенноном. Приведем одну из эквивалентных формулировок данной теоремы.
Теорема кодирования
. Сообщения произвольного источника информации Z с энтропией H
(Z
) всегда можно закодировать последовательностями в алфавите B
, состоящем из M символов
, так
, что средняя длина кодового слова будет сколь угодно близка к величине
, но не меньше нее.
Доказательство этой теоремы в силу его сложности не рассматривается.
Теорема утверждает, что разность можно сделать как угодно малой. В этом и заключается задача методов оптимального кодирования.
Вернемся к рассмотрению алфавитного источника информации, генерирующего сообщения в символах алфавита А . Поскольку избыточность кода задается формулой
очевидно, что чем меньше , тем оптимальнее код. Для уменьшения следует кодировать часто встречающиеся символы более короткими словами и наоборот. На соблюдении этого требования основаны все методы оптимального кодирования. Кроме того, для обеспечения декодирования неравномерного кода важно соблюдать принцип префиксности : никакое кодовое слово не должно являться началом другого кодового слова.
Приведем два наиболее известных метода оптимального побуквенного кодирования. Для простоты изложения возьмем двоичный алфавит в качестве кодового.
Шаг 1. Упорядочиваем символы исходного алфавита в порядке невозрастания их вероятностей. (Записываем их в строку.)
Шаг 2. Не меняя порядка символов, делим их на две группы так, чтобы суммарные вероятности символов в группах были по возможности равны.
Шаг 3. Приписываем группе слева "0", а группе справа "1" в качестве элементов их кодов.
Шаг 4. Просматриваем группы. Если число элементов в группе более одного, идем на Шаг 2. Если в группе один элемент, построение кода для него завершено.
Рис. 4.1. Двоичное дерево, соответствующее кодированию по методу Шеннона – Фано
Рассмотрим работу описанного алгоритма на примере кодирования алфавита 
, символы которого встречаются с вероятностями (0,25; 0,05; 0,25; 0,1; 0,25; 0,1) соответственно. Результат кодирования изображен на рис. 4.1.
Очевидно, что процесс построения кода в общем случае содержит неоднозначность, так как мы не всегда можем поделить последовательность на два равновероятных подмножества. Либо слева, либо справа сумма вероятностей будет больше. Критерием лучшего варианта является меньшая избыточность кода. Заметим также, что правильное считывание кода – от корня дерева к символу – обеспечит его префиксность.
Алгоритм метода Шеннона-Фано - один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано, и он имеет большое сходство с алгоритмом Хаффмана. Алгоритм основан на частоте повторения. Так, часто встречающийся символ кодируется кодом меньшей длины, а редко встречающийся - кодом большей длины.
В свою очередь, коды, полученные при кодировании, префиксные. Это и позволяет однозначно декодировать любую последовательность кодовых слов. Но все это вступление.
Для работы оба алгоритма должны иметь таблицу частот элементов алфавита.
Итак, алгоритм Хаффмана работает следующим образом:
Алгоритм Шеннона-Фано работает следующим образом:
Ну вот, быстро осмыслив информацию, можно написать код алгоритма Шеннона-Фано на паскале. Попросили именно на нем написать. Поэтому приведу листинг вместе с комментариями.
Program ShennonFano;
uses crt;
const
a:array of char = ("a","b","c","d","e","f"); { символы }
af:array of integer = (10, 8, 6, 5, 4, 3); { частота символов }
{ Процедура для поиска кода каждой буквы }
procedure SearchTree(branch:char; full_branch:string; start_pos:integer; end_pos:integer);
var
dS:real; { Среднее значение массива }
i, m, S:integer; { m - номер средней буквы в последовательности, S - сумма чисел, левой ветки }
c_branch:string; { текущая история поворотов по веткам }
begin
{ проверка если это вход нулевой то очистить историю }
if (a<>" ") then c_branch:= full_branch + branch
else c_branch:= "";
{ Критерий выхода: если позиции символов совпали, то это конец }
if (start_pos = end_pos) then
begin
WriteLn(a, " = ", c_branch);
exit;
end;
{ Подсчет среднего значения частоты в последовательности }
dS:= 0;
for i:=start_pos to end_pos do dS:= dS + af[i];
dS:= dS/2;
{ Тут какой угодно можно цикл for, while, repeat поиск середины }
S:= 0;
i:= start_pos;
m:= i;
while ((S+af[i]
Ну вот собственно и все, о чем я хотел рассказать. Всю информацию можно взять из википедии. На рисунках приведены частоты сверху.
Спасибо за внимание!
ЛАБОРАТОРНАЯ РАБОТА 9
Эффективное кодирование
Цель: Изучение методик эффективного кодирования.
1. Построить код Шеннона-Фано по выбранным вариантам и результаты свести в таблицы.
2. Построить код Хаффмана по выбранным вариантам и результаты свести в таблицы. Для каждого построенного кода построить кодовое дерево.
Отчет по лабораторной работе должен содержать:
– краткие теоретические сведения о коде Шеннона-Фано и коде Хаффмана;
– построить коды Шеннона-Фано и Хаффмана при различных вариантах входных данных (для каждого кода выбрать произвольно три группы по 12 символов в каждой, присвоить каждому символу вероятность (сумма равна единице) и построить указанные коды).
– выводы.
Основные понятия и определения
Код Шеннона-Фано
Код строят следующим образом: знаки алфавита сообщений вписываются в таблицу в порядке убывания вероятностей. Затем их разделяют на две группы так, чтобы суммы вероятностей в каждой из групп были по возможности одинаковы. Всем знакам верхней половины в качестве первого символа приписывают «0», а всем нижним – «1». Каждую из полученных групп, в свою очередь разбивают на две подгруппы с одинаковыми суммарными вероятностями и т. д. Процесс повторяется до тех пор, пока в каждой подгруппе останется по одному знаку.
Пример 1. Проведем эффективное кодирование ансамбля из восьми знаков, характеристики которого представлены в табл. 3.1.
Таблица 3.1
| Знаки | Вероятность | Кодовые комбинации | Ступень разбиения |
| Z 1 | 0.22 | ||
| Z 2 | 0.2 | ||
| Z 3 | 0.16 | ||
| Z 4 | 0.16 | ||
| Z 5 | 0.1 | ||
| Z 6 | 0.1 | ||
| Z 7 | 0.04 | ||
| Z 8 | 0.02 |
Рис. 3.1. Дерево группового разделения вероятностей Шеннона-Фано
Ясно, что при обычном (не учитывающем статистических характеристик) кодировании для представления каждого знака требуется три двоичных символа. Используя методику Шеннона-Фано, получаем совокупность кодовых комбинаций, приведенных в табл. 3.1.
Так как вероятности знаков представляют собой целочисленные отрицательные степени двойки, то избыточность при кодировании устраняется полностью. Среднее число символов на знак в этом случае точно равно энтропии. Убедимся в этом, вычислив энтропию
,
и среднее число символов на знак
,
где – число символов в кодовой комбинации, соответствующей знаку .
В общем случае для алфавита из восьми знаков среднее число символов на знак будет меньше трех, но больше энтропии алфавита .
Пример 2. Определим среднюю длину кодовой комбинации при эффективном кодировании знаков ансамбля. Приведенного в табл. 3.2.
Энтропия ансамбля равна 2,76. В результате сопоставления отдельным знакам ансамбля кодовых комбинаций по методике Шеннона-Фано (табл. 3.2) получаем среднее число символов на знак, равное 2,84.
Таблица 3.2
Характеристики ансамбля из восьми знаков
| Знаки | Вероятность | Кодовые комбинации | Ступень разбиения |
| Z 1 | 0,22 | ||
| Z 2 | 0,20 | ||
| Z 3 | 0,16 | ||
| Z 4 | 0,16 | ||
| Z 5 | 0,10 | ||
| Z 6 | 0,10 | ||
| Z 7 | 0,04 | ||
| Z 8 | 0,02 |
Следовательно, некоторая избыточность в последовательностях символов осталась. Из теоремы Шеннона следует, что эту избыточность также можно устранить, если перейти к кодированию достаточно большими блоками.
Для определенности будем рассматривать кодирование в двоичном алфавите (m = 2). Буквы (или любые сообщения, подлежащие кодированию) исходного алфавита записывают в порядке убывающей вероятности. Упорядоченное таким образом множество букв разбивают на две части так, чтобы суммарные вероятности этих подмножеств были примерно равны. Всем знакам (буквам) верхней половины в качестве первого символа присваивают кодовый элемент 1, а всем нижним - 0. Затем каждое подмножество снова разбивается на два подмножества с соблюдением того же условия равенства вероятностей и с тем же условием присваивания кодовых элементов в качестве второго символа. Такое разбиение продолжается до тех пор, пока в подмножестве не окажется только по одной букве кодируемого алфавита. При каждом разбиении буквам верхнего подмножества присваивается кодовый элемент 1, а буквам нижнего подмножества - 0.
Пример. Провести эффективное кодирование ансамбля из восьми знаков:
|
(знак) x i |
Вероят-ность p i |
Кодовые последовательности |
Длина l i |
р i l i |
-р i log р i |
|||
|
Номер разбиения |
||||||||
2,7 и 
.
Как видно, l ср = H , следовательно, полученный код является оптимальным.
Заметим, что при равномерном (не учитывающем статистических характеристик) кодировании с использованием m =2 знаков количество элементов в кодовой последовательности будет l log m n = log 2 8 = 3, т.е. для представления каждого знака использованного алфавита потребуется три двоичных символа.
При кодировании по методике Шеннона - Фано некоторая избыточность в последовательностях символов, как правило, остается (l ср > H ).
Эту избыточность можно устранить, если перейти к кодированию достаточно большими блоками .
Пример. Рассмотрим процедуру эффективного кодирования сообщений, образованных с помощью алфавита, состоящего всего из двух знаков x 1 и x 2 с вероятностями появления соответственно
p (х 1) = 0,9; p (x 2) = 0,1.
Так
как вероятности не равны, то
последовательность из таких букв будет
обладать избыточностью. Однако, при
побуквенном кодировании мы никакого
эффекта не получим. Действительно, на
передачу каждой буквы требуется символ
либо 1, либо 0, в то время как энтропия
равна 
,
т.е. оказывается 
.
При кодировании блоков, содержащих по две буквы, получим коды:
|
Вероятности |
комбинации |
|||
|
номер разбиения |
||||
Так
как знаки статистически не связаны,
вероятности блоков определяют как
произведение вероятностей составляющих
знаков. Среднее число символов на блок
а на букву
1,29/2 = 0,645, т.е. приблизилось к Н
= 0,47, и таким образом удалось повысить
эффективность кодирования.
Кодирование блоков, содержащих по три знака, дает еще больший эффект:
|
Вероятность |
кодовые комбинации |
|||||
|
номер разбиения |
||||||
Среднее число символов на блок равно 1,59, а на знак - 0,53, что всего на 12% больше энтропии.
Алгоритм метода Шеннона-Фано - один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано, и он имеет большое сходство с алгоритмом Хаффмана. Алгоритм основан на частоте повторения. Так, часто встречающийся символ кодируется кодом меньшей длины, а редко встречающийся - кодом большей длины.
В свою очередь, коды, полученные при кодировании, префиксные. Это и позволяет однозначно декодировать любую последовательность кодовых слов. Но все это вступление.
Для работы оба алгоритма должны иметь таблицу частот элементов алфавита.
Итак, алгоритм Хаффмана работает следующим образом:
Алгоритм Шеннона-Фано работает следующим образом:
Ну вот, быстро осмыслив информацию, можно написать код алгоритма Шеннона-Фано на паскале. Попросили именно на нем написать. Поэтому приведу листинг вместе с комментариями.
Program ShennonFano;
uses crt;
const
a:array of char = ("a","b","c","d","e","f"); { символы }
af:array of integer = (10, 8, 6, 5, 4, 3); { частота символов }
{ Процедура для поиска кода каждой буквы }
procedure SearchTree(branch:char; full_branch:string; start_pos:integer; end_pos:integer);
var
dS:real; { Среднее значение массива }
i, m, S:integer; { m - номер средней буквы в последовательности, S - сумма чисел, левой ветки }
c_branch:string; { текущая история поворотов по веткам }
begin
{ проверка если это вход нулевой то очистить историю }
if (a<>" ") then c_branch:= full_branch + branch
else c_branch:= "";
{ Критерий выхода: если позиции символов совпали, то это конец }
if (start_pos = end_pos) then
begin
WriteLn(a, " = ", c_branch);
exit;
end;
{ Подсчет среднего значения частоты в последовательности }
dS:= 0;
for i:=start_pos to end_pos do dS:= dS + af[i];
dS:= dS/2;
{ Тут какой угодно можно цикл for, while, repeat поиск середины }
S:= 0;
i:= start_pos;
m:= i;
while ((S+af[i]
Ну вот собственно и все, о чем я хотел рассказать. Всю информацию можно взять из википедии. На рисунках приведены частоты сверху.
Спасибо за внимание!
