ЛАБОРАТОРНАЯ РАБОТА 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 |
Следовательно, некоторая избыточность в последовательностях символов осталась. Из теоремы Шеннона следует, что эту избыточность также можно устранить, если перейти к кодированию достаточно большими блоками.
Оптимальное кодирование
Теорема кодирования Шеннона. Методы побуквенного оптимального кодирования. Критерии оптимальности кода. Блочное кодирование. Единая система кодирования текстовой информации.
Кодирование , минимизирующее избыточность кода , называется оптимальным .
Вопрос существования таких кодов составляет суть одной из основных теорем теории информации – теоремы кодирования, доказанной К. Шенноном. Приведем одну из эквивалентных формулировок данной теоремы.
Теорема кодирования
. Сообщения произвольного источника информации 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.
Очевидно, что процесс построения кода в общем случае содержит неоднозначность, так как мы не всегда можем поделить последовательность на два равновероятных подмножества. Либо слева, либо справа сумма вероятностей будет больше. Критерием лучшего варианта является меньшая избыточность кода. Заметим также, что правильное считывание кода – от корня дерева к символу – обеспечит его префиксность.
Одно и тоже сообщение можно закодировать различными способами. Наиболее выгодным является такой код, при использование которого на передачу сообщений затрачивается минимальное время. Если на передачу каждого элемента символа (например, 0 или 1) тратится одно и то же время, то оптимальным будет такой код, при использование которого на передачу сообщения заданной длины будет затрачено минимальное количество элементарных символов. Коды Шеннона – Фано являются префиксными, т.е. никакое кодовое слово не является префиксом любого другого. Данное свойство позволяет однозначно декодировать любую последовательность кодовых слов
Рассмотрим принцип построения одного из первых алгоритмов сжатия, который сформулировали американские ученые Шеннон и Фано на примере букв русского алфавита. Алгоритм использует коды переменной длины, т.е. часто встречающийся символ кодируется кодом меньшей длины, редко встречающийся – кодом большей длины .
Чтобы составить такой код, очевидно, нужно знать частоты появления букв в русском тексте. Эти частоты приведены в таблице 1 . Буквы в таблице расположены в порядке убывания частот.
Таблица 1
Частота появления букв русского алфавита
Пользуясь таблицей, можно составить наиболее экономичный код на основе соображений, связанных с количеством информации. Очевидно, код будет самым экономичным, когда каждый элементарный символ будет передавать максимальную информацию. Рассмотрим элементарный символ (т. е. изображающий его сигнал) как физическую систему с двумя возможными состояниями: 0 и 1. Информация, которую дает этот символ, равна энтропии этой системы и максимальна в случае, когда оба состояния равновероятны; в этом случае элементарный символ передает информацию 1 (двоичная единица). Поэтому основой оптимального кодирования будет требование, чтобы элементарные символы в закодированном тексте встречались в среднем одинаково часто.
Идея кодирования состоит в том, что кодируемые символы (буквы или комбинации букв) разделяются на две приблизительно равновероятные группы: для первой группы символов на первом месте комбинации ставится 0 (первый знак двоичного числа, изображающего символ); для второй группы − 1. Далее каждая группа снова делится на две приблизительно равновероятные подгруппы; для символов первой подгруппы на втором месте ставится 0; для второй подгруппы − единица и т. д.
Продемонстрируем принцип построения кода Шеннона − Фано на примере материала русского алфавита (см. табл. 1). Отсчитаем первые шесть букв (от «−» до «т»); суммируя их вероятности (частоты), получим 0,498; на все остальные буквы от «н» до «ф» придется приблизительно такая же вероятность 0,502. Первые шесть букв (от «−» до «т») будут иметь на первом месте двоичный знак 0. Остальные буквы (от «н» до «ф») будут иметь на первом месте единицу. Далее снова разделим первую группу на две приблизительно равновероятные подгруппы: от «−» до «о» и от «е» до «т»; для всех букв первой подгруппы на втором месте поставим нуль, а второй подгруппы − единицу. Процесс будем продолжать до тех пор, пока в каждом подразделении не останется ровно одна буква, которая будет закодирована определенном двоичным числом. Механизм построения показан на таблице 2, а сам код приведен в таблице 3.
Таблица 2
Механизм построения кода Шеннона – Фано на примере русского алфавита
| Двоичные знаки | |||||||||
| Буквы | 1 й | 2 й | 3 й | 4 й | 5 й | 6 й | 7 й | 8 й | 9 й |
| - | |||||||||
| о | |||||||||
| е | |||||||||
| а | |||||||||
| и | |||||||||
| т | |||||||||
| н | |||||||||
| с | |||||||||
| р | |||||||||
| в | |||||||||
| л | |||||||||
| к | |||||||||
| м | |||||||||
| д | |||||||||
| п | |||||||||
| у | |||||||||
| я | |||||||||
| ы | |||||||||
| з | |||||||||
| ъ, ь | |||||||||
| б | |||||||||
| г | |||||||||
| ч | |||||||||
| й | |||||||||
| х | |||||||||
| ж | |||||||||
| ю | |||||||||
| ш | |||||||||
| ц | |||||||||
| щ | |||||||||
| э | |||||||||
| ф |
Таблица 3
Результат кодирования букв русского алфавита кодом Шеннона - Фано
Пример 4. Запишем фразу «способ кодирования», используя код Шеннона - Фано.
Решение: Воспользуемся таблицей 3 и получим следующий результат:
(1001)с (110011)п (001)о (1001)с (001)о (111010)б (000)пробел
(10111)к (001)о (110010)д (0110)и (10100)р (001)о (10101)в
(0101)а (1000)н (0110)и (110110)я
Заметим, что здесь нет необходимости отделять друг от друга буквы специальным знаком, так как и без этого декодирование выполняется однозначно благодаря свойству префиксности: ни одна более короткая кодовая комбинация не является началом более длинной кодовой комбинации. Действительно, из таблицы 3 видно, что самыми короткими являются коды для символов «пробел» и «о». При этом не один другой более длинный код не имеет в начале последовательности 000 («пробел») и 001 («о»). То же самое можно наблюдать и для всех других двоичных последовательностей кода Шеннона – Фано, которые приведены в таблице 3.
Необходимо отметить, что любая ошибка при кодирование (случайное перепутывание знаков 0 или 1) при таком коде губительна, так как декодирование всего следующего за ошибкой текста становится невозможным.
Пример 5. Определим, является ли рассмотренный нами код оптимальным при отсутствие ошибок?
Решение: Найдем среднюю информацию, приходящуюся на один элементарный символ (0 или 1), и сравним ее с максимально возможной информацией, которая равна единице. Для этого найдем сначала среднюю информацию, содержащуюся в одной букве передаваемого текста, т. е. энтропию на одну букву (см. формулу 8):
По таблице 1 определяем среднее число элементарных символов на букву:
Таким образом, информация на один символ весьма близка к своему верхнему пределу единице, а данный код весьма близок к оптимальному.
В случае использования пятиразрядного двоичного кода информация на один символ:
Пример 6. Пусть по каналу связи получено сообщение (слово на русском языке) закодированное кодом Шеннона – Фано: 10111001110010010010100.
Необходимо декодировать данную последовательность.
Решение: Процесс декодирования основывается на свойстве префиксности кода и выполняется слева на право. Из таблицы 3 видно, что минимальная длина кода составляет три бита. Отсчитает три бита от начала принятой кодовой комбинации, получим – 101. В таблице такой код отсутствует, поэтому добавляем еще один бит, получим – 1011. Данного кода также нет в таблице, следовательно, необходимо добавить еще один бит, получим комбинацию – 10111, которой соответствует буква «к». Кодовая комбинация 10111 исключается из принятой кодовой комбинации и заменяется исходным символом (буква «к»). Процесс декодирования остальных букв принятого сообщения выполняется аналогично.
Полный процесс декодирования приведен в таблице 4. Знак «-» в таблице означает, что в таблице 3 отсутствует выбранный код.
Таблица 4
Процесс декодирования сообщения
| Принятая кодовая последовательность | ||||||||||||||||||||||
| - | ||||||||||||||||||||||
| - | ||||||||||||||||||||||
| к | ||||||||||||||||||||||
| к | о | |||||||||||||||||||||
| к | о | - | ||||||||||||||||||||
| к | о | - | ||||||||||||||||||||
| к | о | - | ||||||||||||||||||||
| к | о | д | ||||||||||||||||||||
| к | о | д | - | |||||||||||||||||||
| к | о | д | е | |||||||||||||||||||
| к | о | д | е | - | ||||||||||||||||||
| к | о | д | е | - | ||||||||||||||||||
| к | о | д | е | р |
Итак, слово, полученное в результате декодирования принятой кодовой комбинации – «кодер».
Алгоритм метода Шеннона-Фано - один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано, и он имеет большое сходство с алгоритмом Хаффмана. Алгоритм основан на частоте повторения. Так, часто встречающийся символ кодируется кодом меньшей длины, а редко встречающийся - кодом большей длины.
В свою очередь, коды, полученные при кодировании, префиксные. Это и позволяет однозначно декодировать любую последовательность кодовых слов. Но все это вступление.
Для работы оба алгоритма должны иметь таблицу частот элементов алфавита.
Итак, алгоритм Хаффмана работает следующим образом:
Алгоритм Шеннона-Фано работает следующим образом:
Ну вот, быстро осмыслив информацию, можно написать код алгоритма Шеннона-Фано на паскале. Попросили именно на нем написать. Поэтому приведу листинг вместе с комментариями.
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]
Ну вот собственно и все, о чем я хотел рассказать. Всю информацию можно взять из википедии. На рисунках приведены частоты сверху.
Спасибо за внимание!
| c(i) | p(c(i)) |
| d | 5 / 17 |
| c | 4 / 17 |
| space | 3 / 17 |
| b | 3 / 17 |
| a | 2 / 17 |
Длина кода s(i) в полученной таблице равна int(-lg p(c(i))) , если сиволы удалость разделить на группы с одинаковой частотой, в противном случае, длина кода равна int(-lg p(c(i))) + 1 .
длиной в 39 бит. Учитывая, что оргинал имел длину равную 136 бит, получаем коэффициент сжатия ~28% - не так уж и плохо.
Глядя на полученную последовательность, возникает вопрос: "А как же теперь это расжать?". Мы не можем, как в случае кодирования, заменять каждые 8 бит входного потока, кодом переменной длины. При расжатии нам необходимо всё сделать наоборот - заменить код переменной длины символом длиной 8 бит. В данном случае, лучше всего будет использовать бинарное дерево, листьями которого будут являтся символы (аналог дерева Хаффмана).
Кодирование Шеннона-Фано является достаточно старым методом сжатия, и на сегодняшний день оно не представляет особого практического интереса (разве что как упражнение по курсу структур данных). В большинстве случаев, длина сжатой последовательности, по данному методу, равна длине сжатой последовательности с использованием кодирования Хаффмана. Но на некоторых последовательностях всё же формируются не оптимальные коды Шеннона-Фано, поэтому сжатие методом Хаффмана принято считать более эффективным. Для примера, рассмотрим последовательность с таким содержанием символов: "a" - 14, "b" - 7, "c" - 5, "d" - 5, "e" - 4. Метод Хаффмана сжимает её до 77 бит, а вот Шеннона-Фано до 79 бит.
|
Из-за такой неопределённости у некоторых людей возникают даже такие мысли: "... программа иногда назначает некоторым символам..." и так далее - рассуждения о длине кодов. Если вы не пишете AI, то такое понятие, как "программа иногда" что-то делает, звучит смешно. Правильно реализованный алгоритм - работает строго опеределённо.
