Фано кодирование. Коды шеннона - фано

Одно и тоже сообщение можно закодировать различными способами. Наиболее выгодным является такой код, при использование которого на передачу сообщений затрачивается минимальное время. Если на передачу каждого элемента символа (например, 0 или 1) тратится одно и то же время, то оптимальным будет такой код, при использование которого на передачу сообщения заданной длины будет затрачено минимальное количество элементарных символов. Коды Шеннона – Фано являются префиксными, т.е. никакое кодовое слово не является префиксом любого другого. Данное свойство позволяет однозначно декодировать любую последовательность кодовых слов

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

Чтобы составить такой код, очевидно, нужно знать частоты появления букв в русском тексте. Эти частоты приведены в таблице 1 . Буквы в таблице расположены в порядке убывания частот.

Таблица 1

Частота появления букв русского алфавита

Пользуясь таблицей, можно составить наиболее экономичный код на основе соображений, связанных с количеством информации. Очевидно, код будет самым экономичным, когда каждый элементарный символ будет передавать максимальную информацию. Рассмотрим элементарный символ (т. е. изображающий его сигнал) как физическую систему с двумя возможными состояниями: 0 и 1. Информация, которую дает этот символ, равна энтропии этой системы и максимальна в случае, когда оба состояния равновероятны; в этом случае элементарный символ передает информацию 1 (двоичная единица). Поэтому основой оптимального кодирования будет требование, чтобы элементарные символы в закодированном тексте встречались в среднем одинаково часто.

Идея кодирования состоит в том, что кодируемые символы (буквы или комбинации букв) разделяются на две приблизительно равновероятные группы: для первой группы символов на первом месте комбинации ставится 0 (первый знак двоичного числа, изображающего символ); для второй группы − 1. Далее каждая группа снова делится на две приблизительно равновероятные подгруппы; для символов первой подгруппы на втором месте ставится 0; для второй подгруппы − единица и т. д.

Продемонстрируем принцип построения кода Шеннона − Фано на примере материала русского алфавита (см. табл. 1). Отсчитаем первые шесть букв (от «−» до «т»); суммируя их вероятности (частоты), получим 0,498; на все остальные буквы от «н» до «ф» придется приблизительно такая же вероятность 0,502. Первые шесть букв (от «−» до «т») будут иметь на первом месте двоичный знак 0. Остальные буквы (от «н» до «ф») будут иметь на первом месте единицу. Далее снова разделим первую группу на две приблизительно равновероятные подгруппы: от «−» до «о» и от «е» до «т»; для всех букв первой подгруппы на втором месте поставим нуль, а второй подгруппы − единицу. Процесс будем продолжать до тех пор, пока в каждом подразделении не останется ровно одна буква, которая будет закодирована определенном двоичным числом. Механизм построения показан на таблице 2, а сам код приведен в таблице 3.

Таблица 2

Механизм построения кода Шеннона – Фано на примере русского алфавита

Таблица 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

Процесс декодирования сообщения

Итак, слово, полученное в результате декодирования принятой кодовой комбинации – «кодер».

Код Шеннона-Фано

Код строится следующим образом:

1) буквы алфавита сообщений выпи­сываются в таблицу в порядке убывания вероятностей;

2) затем они разделя­ются на две группы так, чтобы суммы вероятностей в каждой из групп бы­ли по возможности одинаковы;

3) всем буквам верхней половины в качестве первого символа приписывается 1, а всем нижним - 0;

4) каждая из получен­ных групп, в свою очередь, разбивается на две подгруппы с одинаковыми суммарными вероятностями и т. д.

Процесс повторяется до тех пор, пока в каждой подгруппе останется по одной букве.

Пример. Рассмотрим алфавит из восьми букв (табл. 12). При обычном (не учитывающем статистических характеристик) кодировании для пред­ставления каждой буквы требуется три символа.

Таблица 8.12 Таблица 13

Вычислим энтропию набора букв: Н

и среднее число символов на букву

где n() - число символов в кодовой комбинации, соответствующей букве.

Значения Н(z) и l ср не очень различаются по величине. Условие теоремы Шеннона выполнено Н(z) <= l ср

Рассмотренная методика Шеннона-Фано не всегда приводит к одно­значному построению кода. Ведь при разбиении на подгруппы можно сде­лать большей по вероятности как верхнюю, так и нижнюю подгруппу.

Множество вероятностей в предыдущей таблице можно было разбить иначе (табл. 13). При этом среднее число символов на букву оказывается равным 2,80. Таким образом, построенный код может оказаться не самым лучшим. При построении эффективных кодов с основанием s > 2 неопределенность ста­новится еще больше.

Метод Хаффмена

Метод Хаффмена свободен от недостатка связанного с неоднозначностью построения кода. Данная методика также использует статистические свойства источника сообщений. Метод гарантирует однозначное построение кода с наименьшим для данного распределения вероятностей средним числом символов на букву.

В таблице 14 показаны основные шаги построения кода.

Таблица 14

Для двоичного кода методика сводится к следующему:

1) Буквы алфавита сообщений выписываются в основной столбец в порядке убывания вероят­ностей;

2) две последние буквы объединяются в одну вспомогательную бук­ву, которой приписывается суммарная вероятность;

3) вероятности букв, не участвовавших в объединении, и полу­ченная суммарная вероятность снова располагаются в порядке убывания ве­роятностей в дополнительном столбце, а две последние буквы снова объединяются.

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

Для составления кодовой комбина­ции, соответствующей данному сообще­нию, необходимо проследить путь пере­хода сообщений по строкам и столбцам таблицы. Для наглядности строится кодо­вое дерево(рис.1).

Рис.1 Кодовое дерево

Из точки, соответствующей вероятности 1, направляются две ветви, причем ветви с большей вероятностью присваивается символ 1, а с меньшей - 0. Такое последовательное ветвление продолжается до тех пор, пока не дойдем до каждой буквы (рис. 1).

Теперь, двигаясь по кодовому дереву сверху вниз, можно записать для каждой буквы соответствующую ей кодовую комбинацию;

01 00 111 110 100 1011 10101 10100

Длина кода 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, то такое понятие, как "программа иногда" что-то делает, звучит смешно. Правильно реализованный алгоритм - работает строго опеределённо.

При ответе на данный вопрос необходимо привести пример построения префиксного кода Шеннона-Фано для заданного начального алфавита и известных частот использования символов этого алфавита с помощью таблицы и графа.

В 1948-1949 гг. Клод Шеннон (Claude Elwood Shannon ) и Роберт Фано (Robert Mario Fano ) независимо друг от друга предложили префиксный код, названный в последствие в их честь. Алгоритм Шеннона - Фано использует избыточность сообщения, заключённую в неоднородном распределении частот символов его первичного алфавита, то есть заменяет коды более частых символов короткими двоичными последовательностями, а коды более редких символов - более длинными двоичными последовательностями.

Рассмотрим этот префиксный код на примере. Пусть имеется первичный алфавит, состоящий из шести символов: {A; B; C; D; E; F}, также известны вероятности появления этих символов в сообщении соответственно {0,15; 0,2; 0,1; 0,3; 0,2; 0,05}. Расположим эти символы в таблице в порядке убывания их вероятностей.

Кодирование осуществляется следующим образом. Все знаки делятся на две группы с сохранением порядка следования (по убыванию вероятностей появления), так чтобы суммы вероятностей в каждой группе были приблизительно равны. В нашем примере в первую группу попадают символы D и B, все остальные буквы попадают во вторую группу. Поставим ноль в первый знак кодов для всех символов из первой группы, а первый знак кодов символов второй группы установим равным единице.

Продолжим деление каждой группы. В первой группе два элемента, и деление на подгруппы здесь однозначно: в первой подгруппе будет символ D, а во второй - символ B. Во второй группе теоретически возможны три способа деления на подгруппы: {E} и {A, C, F}, {E, A} и {C, F}, {E, A, C} и {F}. Но в первом случае абсолютная разность суммарных вероятностей будет |0,2 - (0,15 + 0,1 + 0,05)| = 0,1. Во втором и третьем варианте деления аналогичные величины будут 0,2 и 0,4 соответственно. Согласно алгоритму необходимо выбрать тот способ деления, при котором суммы вероятностей в каждой подгруппе были примерно одинаковыми, а, следовательно, вычисленная разность минимальна. Соответственно наилучшим способом деления будет следующий вариант: {E} в первой подгруппе и {A, C, F} во второй. Далее по имеющемуся алгоритму распределим нули и единицы в соответствующие знаки кода каждой подгруппы.

Осуществляем деление на подгруппы по той же схеме до тех пор, пока не получим группы, состоящие из одного элемента. Процедура деления изображена в таблице (символ Х означает, что данный знак кода отсутствует):

Данный код может быть построен и с помощью графа. Распределим символы алфавита в порядке убывания вероятностей - это будут концевые вершины (листья) будущего двоичного дерева (нижние индексы соответствуют вероятностям появления символов):

Согласно алгоритму построения кода Шеннона-Фано разобьем эти символы на две группы с приблизительно равными суммарными вероятностями появления и соединим первые символы каждой группы с корнем дерева:

Продолжаем построение графа по приведенному алгоритму, соединяя первые символы получающихся подгрупп с узлами ветвления более высоких уровней. Таким образом, на следующих этапах построения получим:

D 0,3	B 0,2	E 0,2	A 0,15	C 0,1	F 0,05

D 0,3	B 0,2	E 0,2	A 0,15	C 0,1	F 0,05

Окончательно имеем следующий граф:

D 0,3	B 0,2	E 0,2	A 0,15	C 0,1	F 0,05

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

D 0,3	B 0,2	E 0,2	A 0,15	C 0,1	F 0,05

Для получения кода символа достаточно пройти по дугам полученного дерева от корня к соответствующей вершине и записать номера дуг, по которым осуществляется движение. Например, для символа A, двигаясь от корня дерева, проходим дуги с номерами 1, 1 и 0, следовательно код символа A - 110. Аналогично могут быть получены коды других символов.

Полученный код удовлетворяет условию Фано, следовательно он является префиксным. Средняя длина этого кода равна (см. формулу на стр.13):

К(Шеннона-Фано, А, Binary) = 0,3*2+0,2*2+0.2*2+0,15*3 +0,1*4+0.05*4 = 2,45 символа.

Теперь по известной нам формуле найдем избыточность кода Шеннона –Фано:

Q(Шеннона-Фано, A, Binary) = 2,45/2,41 – 1 = 0,01659751.

То есть избыточность кода Шеннона-Фано для нашего шестибуквенного алфавита составляет всего около 1,7 %. Для русского алфавита этот избыточность кодирования кодом Шеннона-Фано составила бы примерно 1,47%.

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

При ответе на данный вопрос необходимо привести пример построения префиксного кода Хаффмана для заданного начального алфавита и известных частот использования символов этого алфавита с помощью таблицы и графа.

В 1952 году Давид Хаффман показал, что предложенный им метод кодирования является оптимальным префиксным кодом для дискретных источников без памяти (у такого источника все сообщения независимы).

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

Рассмотрим алгоритм построения кода Хаффмана на примере. Пусть имеется первичный алфавит, состоящий из шести символов: {A; B; C; D; E; F}, также известны вероятности появления этих символов в сообщении соответственно {0,15; 0,2; 0,1; 0,3; 0,2; 0,05}. Расположим эти символы в таблице в порядке убывания их вероятностей.

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

Теперь начинается второй этап алгоритма кодирования по Хаффману. Для формирования кода мы нумеруем символы всех промежуточных алфавитов, начиная с последнего. В нашем примере – с А 4 .

В А 4 всего два символа. Они получают соответственно номера 0 и 1. В алфавите А 3 уже три символа. Причем, один из символов алфавита А 4 , назовем этот символ «предок», был получен объединением двух символов алфавита А 3 , назовем первый из этих символов «дочкой», а второй «сыном». Коды этих двух символов формируются следующим образом. К номеру «предка» приписываются справа 0, чтобы получить номер «дочки», и 1 – чтобы получить номер «сына». Следующая итерация алгоритма по той же схеме формирует коды символов алфавита А 2 . В нем два первых символа будут иметь те же коды, что были у них в А 1 , а два последних символа изменят свой код, удлинив его на 1 символ («0» и «1» соответственно). Процесс останавливается при достижении первичного алфавита A 0 – коды для знаков первичного алфавита получены.

Данный алгоритм построения можно осуществить и с помощью графа. Расположим символы первичного алфавита в порядке убывания вероятностей их появления. Эти символы будут листьями будущего кодового дерева. Будем считать, что уровень этих концевых узлов равен N.

В получившемся промежуточном алфавите вновь выбираем два символа с наименьшей частотой использования. Это символ А с вероятностью 0,15 и новый символ, получившийся в результате объединения символов C и F на предыдущем этапе и имеющий ту же вероятность использования. Соединяем эти символы дугами, исходящими из одного узла N-2 уровня:

Посчитаем среднюю длину кодового слова для кода Хаффмана и нашего первичного алфавита А.

К(Хаффман, А, Binary) = = 0,3*2 + 0,2*2 + 0.2*2 + 0,15*3 + 0,1*4 + 0.05*4 = 2,45 символа

Среднее количество информации на один символ первичного алфавита равно:

I A = - (0,3* log 2 0,3 + 0,2* log 2 0,2 + 0,2* log 2 0,2 + 0,15* log 2 0,15 + + 0,1* log 2 0,1 + 0,05* log 2 0,05) = 2,41 бит.

Относительная избыточность кода Хаффмана в нашем случае:

Q(Хаффмана, A, Binary) = 2,45/2,41 – 1 = 0,01659751.

Таким образом, для нашего примера код Шеннона-Фано и код Хаффмана обладают одинаковой избыточностью. Однако, в тех случаях когда вероятности символов первичного алфавита сильно разнятся, ситуация меняется. Код Хаффмана обладает существенно меньшей избыточностью. Например, для русского языка избыточность кодирования кодом Хаффмана оказывается равной примерно 0,0090.

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

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

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

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

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

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

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

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

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