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

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

В 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	0,3
B	0,2
E	0,2
A	0,15
C	0,1
F	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} во второй. Далее по имеющемуся алгоритму распределим нули и единицы в соответствующие знаки кода каждой подгруппы.

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

Первичный алфавит	Вероятности появления	Знаки кода символа	Код символа	Длина кода
I	II	III	IV
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

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

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 символа.

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

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

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

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}. Расположим эти символы в таблице в порядке убывания их вероятностей.

Первичный алфавит	D	B	E	A	C	F
Вероятности появления символов	0,3	0,2	0,2	0,15	0,1	0,05

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

A⁰	Код А⁰	A¹	Код А¹	А²	Код А²	А³	Код А³	А⁴	Код А⁴
a⁰₁=D _{P = 0,3}		a¹₁ _{P = 0,3}		a²₁ _{P = 0,3}		a³₁ _{P = 0,4}		a⁴₁ _{P = 0,6}
a⁰₂=B _{P = 0,2}		a¹₂ _{P = 0,2}		a²₂ _{P = 0,3}		a³₂ _{P = 0,3}		a⁴₂ _{P = 0,4}
a⁰₃=E _{P = 0,2}		a¹₃ _{P = 0,2}		a²₃ _{P = 0,2}		a³₃ _{P = 0,3}
a⁰₄=A _{P = 0,15}		a¹₄ _{P = 0,15}		a²₄ _{P = 0,2}
a⁰₅=C _{P = 0,1}		a¹₅ _{P = 0,15}
a⁰₆=F _{P = 0,05}

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

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

A⁰	Код А⁰	A¹	Код А¹	А²	Код А²	А³	Код А³	А⁴	Код А⁴
a⁰₁=D _{P = 0,3}		a¹₁ _{P = 0,3}		a²₁ _{P = 0,3}		a³₁ _{P = 0,4}		a⁴₁ _{P = 0,6}
a⁰₂=B _{P = 0,2}		a¹₂ _{P = 0,2}		a²₂ _{P = 0,3}	01	a³₂ _{P = 0,3}		a⁴₂ _{P = 0,4}
a⁰₃=E _{P = 0,2}		a¹₃ _{P = 0,2}		a²₃ _{P = 0,2}		a³₃ _{P = 0,3}
a⁰₄=A _{P = 0,15}		a¹₄ _{P = 0,15}		a²₄ _{P = 0,2}
a⁰₅=C _{P = 0,1}		a¹₅ _{P = 0,15}
a⁰₆=F _{P = 0,05}

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

D _0,3

B _0,2

E _0,2

A _0,15

C _0,1

F _0,05

Теперь соединим два крайних правых символа (C и F), имеющих наименьшую вероятность появления, дугами, исходящими из одного и того же узла уровня N-1 (в основании узла указана суммарная вероятность использования получившегося символа нового промежуточного алфавита):

D _0,3

B _0,2

E _0,2

A _0,15

C _0,1

F _0,05

0,15

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

D _0,3

B _0,2

E _0,2

A _0,15

C _0,1

F _0,05

0,15

0,3

Продолжая описанный алгоритм построения, получим следующее дерево:

B _0,2	E _0,2	A _0,15	C _0,1	F _0,05

		D _0,3

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

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

К(Хаффман, А, 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₂0,3 + 0,2* log₂0,2 + 0,2* log₂0,2 + 0,15* log₂0,15 + + 0,1* log₂0,1 + 0,05* log₂0,05) = 2,41 бит.

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

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

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

12 3 4

Не нашли, что искали? Воспользуйтесь поиском по сайту: