Кодирование шеннона фано пример. Коды шеннона - фано

Для определенности будем рассматривать кодирование в двоичном алфавите (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% больше энтропии.

Оптимальное кодирование

Теорема кодирования Шеннона. Методы побуквенного оптимального кодирования. Критерии оптимальности кода. Блочное кодирование. Единая система кодирования текстовой информации.

Кодирование , минимизирующее избыточность кода , называется оптимальным .

Вопрос существования таких кодов составляет суть одной из основных теорем теории информации – теоремы кодирования, доказанной К. Шенноном. Приведем одну из эквивалентных формулировок данной теоремы.

Теорема кодирования . Сообщения произвольного источника информации 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.

Очевидно, что процесс построения кода в общем случае содержит неоднозначность, так как мы не всегда можем поделить последовательность на два равновероятных подмножества. Либо слева, либо справа сумма вероятностей будет больше. Критерием лучшего варианта является меньшая избыточность кода. Заметим также, что правильное считывание кода – от корня дерева к символу – обеспечит его префиксность.

Кодирование Шеннона-Фано является одним из самых первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон (Shannon) и Фано (Fano). Данный метод сжатия имеет большое сходство с кодированием Хаффмана , которое появилось на несколько лет позже. Главная идея этого метода - заменить часто встречающиеся символы более короткими кодами, а редко встречающиеся последовательности более длинными кодами. Таким образом, алгоритм основывается на кодах переменной длины. Для того, чобы декомпрессор впоследствии смог раскодировать сжатую последовательность, коды Шеннона-Фано должны обладать уникальностью, то есть, не смотря на их переменную длину, каждый код уникально определяет один закодированый символ и не является префиксом любого другого кода.
Рассмотрим алгоритм вычисления кодов Шеннона-Фано (для наглядности возьмём в качестве примера последовательность "aa bbb cccc ddddd"). Для вычисления кодов, необходимо создать таблицу уникальных символов сообщения c(i) и их вероятностей p(c(i)) , и отсортировать её в порядке невозрастания вероятности символов.

c(i)	p(c(i))
d	5 / 17
c	4 / 17
space	3 / 17
b	3 / 17
a	2 / 17

Далее, таблица символов делится на две группы таким образом, чтобы каждая из групп имела приблизительно одинаковую частоту по сумме символов. Первой группе устанавливается начало кода в "0", второй в "1". Для вычисления следующих бит кодов символов, данная процедура повторяется рекурсивно для каждой группы, в которой больше одного символа. Таким образом для нашего случая получаем следующие коды символов:

Длина кода 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 бит.

символ код Хаффмана код Шеннона-Фано a 0 00 b 111 01 c 101 10 d 110 110 e 100 111

Кстати, в одном источнике (не буду указывать каком), эту последовательность сжали методом Шеннона-Фано до 84 бит, а методом Хаффмана до тех же 77. Такие отличаи в степени сжатия возникают из-за нестрогого определения способа деления символов на группы.
Как же мы делили на группы? Достаточно просто:

Из-за такой неопределённости у некоторых людей возникают даже такие мысли: "... программа иногда назначает некоторым символам..." и так далее - рассуждения о длине кодов. Если вы не пишете AI, то такое понятие, как "программа иногда" что-то делает, звучит смешно. Правильно реализованный алгоритм - работает строго опеределённо.

Алгоритм метода Шеннона-Фано - один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано, и он имеет большое сходство с алгоритмом Хаффмана. Алгоритм основан на частоте повторения. Так, часто встречающийся символ кодируется кодом меньшей длины, а редко встречающийся - кодом большей длины.
В свою очередь, коды, полученные при кодировании, префиксные. Это и позволяет однозначно декодировать любую последовательность кодовых слов. Но все это вступление.

Для работы оба алгоритма должны иметь таблицу частот элементов алфавита.

Итак, алгоритм Хаффмана работает следующим образом:

1. На вход приходят упорядоченные по невозрастанию частот данные .
2. Выбираются две наименьших по частоте буквы алфавита, и создается родитель (сумма двух частот этих «листков»).
3. Потомки удаляются и вместо них записывается родитель, «ветви» родителя нумеруются: левой ветви ставится в соответствие «1», правой «0».
4. Шаг два повторяется до тех пор, пока не будет найден главный родитель - «корень».

Алгоритм Шеннона-Фано работает следующим образом:

1. На вход приходят упорядоченные по невозрастанию частот данные.
2. Находится середина, которая делит алфавит примерно на две части. Эти части (суммы частот алфавита) примерно равны. Для левой части присваивается «1», для правой «0», таким образом мы получим листья дерева
3. Шаг 2 повторяется до тех пор, пока мы не получим единственный элемент последовательности, т.е. листок

Таким образом, видно, что алгоритм Хаффмана как бы движется от листьев к корню, а алгоритм Шеннона-Фано, используя деление, движется от корня к листям.

Ну вот, быстро осмыслив информацию, можно написать код алгоритма Шеннона-Фано на паскале. Попросили именно на нем написать. Поэтому приведу листинг вместе с комментариями.

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] to show"); ReadLn; ClrScr; { Поиск кода Фано, входные параметры начало и конец последовательности } SearchTree(" "," ", 1, 6); ReadLn; end;

Ну вот собственно и все, о чем я хотел рассказать. Всю информацию можно взять из википедии. На рисунках приведены частоты сверху.

Спасибо за внимание!

Алгоритм построения сжимающего кода Шеннона – Фано заключается в следующем.

1. Все символов дискретного источника располагаются в порядке убывания вероятностей их появления (табл. 4.2).

Таблица 4.2. Построение кода Шеннона-Фано

2. Образованный столбец символов делится на две группы таким образом, чтобы суммарные вероятности каждой группы мало отличались друг от друга.

3. Верхняя группа кодируется символом «1», а нижняя – «0».

4. Каждая группа делится на две подгруппы с близкими суммарными вероятностями; верхняя подгруппа кодируется символом «1», а нижняя – «0».

5. Процесс деления и кодирования продолжается до тех пор, пока в каждой подгруппе не окажется по одному символу сообщения источника.

6. Записывается код для каждого символа источника; считывание кода осуществляется слева направо.

При использовании простейшего равномерного кода для кодирования шести элементов алфавита источника потребуется по три двоичных символа на каждую букву сообщения. Если же используется код Шеннона – Фано, то среднее число символов на одну букву