Построение оптимального неравномерного двоичного кода методом Шеннона-Фано

Реализуем алгоритм построения кода Шеннона-Фано по пунктам. Проиллюстрируем работу алгоритма построения кода Шеннона-Фано с помощью таблицы 2.

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

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

- первая группа – (a₁₂, a₁, a₆, a₁₀) с суммарной вероятностью

p(a₁₂)+p(a₁)+p(a₆)+ p(a₁₀)=0,15+0,14+0,12+0,12=0,53;

- вторая группа – (a₁₁, a₄, a₃, a₅, a₇, a₂, a₉, a₈) с суммарной вероятностью

p(a₁₁)+p(a₄)+p(a₃)+p(a₅)+p(a₇)+p(a₂)+p(a₉)+p(a₈)=0,111+0,09+0,08+0,07+

0,04+0,03+0,03+0,02=0,47.

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

Буква	р(аk)	Код 1		p( )	– p(ak) log p(ak)
a12	0,15			0,45	0,4105
a1	0,14			0,42	0,3971
a6	0,12			0,36	0,3671
a10	0,12			0,36	0,3671
a11	0,11			0,33	0,3503
a4	0,09			0,36	0,3127
a3	0,08			0,32	0,2915
a5	0,07			0,28	0,2686
a7	0,04			0,16	0,1858
a2	0,03			0,12	0,1518
a9	0,03			0,15	0,1518
a8	0,02			0,1	0,1129
			=3,41	H(A)=3,3670

п.3. Первым символам кодовых слов букв a₁₂, a₁, a₆, a₁₀ присваиваем символ «0», а первым символам кодовых слов букв a₁₁, a₄, a₃, a₅, a₇, a₂, a₉, a₈ присваиваем символ «1» (столбец 3, таблица 2).

п.4. Повторяется п.2 для первой группы, которая разбивается на две подгруппы: (a₁₂, a₁) и (a₆, a₇). В соответствии с п.3 вторым символам группы (a₁₂, a₁) присваивается символ «0». Вторым символам группы (a₆, a₇) присваивается символ «1».

Повторяется п.2 для группы (a₁₂, a₁), она разбивается на буквы a₁₂ и a₁.

В соответствии с п.3 третьему символу буквы a₁₂ присваивается символ «0», а третьему символу буквы a₁ - символ «1», и на этом процесс кодирования букв a₁₂ и a₁ заканчивается:

Cod a₁₂ =000,

Cod a₁ =001.

Повторяется п.2 для группы (a₆, a₇), она разбивается на буквы a₆ и a₇.

В соответствии с п.3 третьему символу буквы a₆ присваивается символ «0», а третьему символу буквы a₇ - символ «1», и на этом процесс кодирования букв a₉ и a₇ заканчивается:

Cod a₆ =010,

Cod a₇ =011.

Аналогично проводится кодирование остальных символов букв a₁₁, a₄, a₃, a₅, a₇, a₂, a₉, a₈, результаты которого представлены в столбце 3, таблица 2.

Оценим эффективность построенного кода.

Среднюю длину кодового слова вычислим по формуле (16), для чего для каждой буквы первичного алфавита воспользуемся данными из столбцов 4 и 2 таблицы 2, поместим полученные произведения в соответствующие ячейки столбца 5 и просуммируем их :

, (16)

где K – число букв первичного алфавита;

n_k – длина k-го кодового слова;

p(a_k) – вероятность появления k-го кодового слова.

=3,41.

Вычислим энтропию первичного алфавита по известной формуле (6). В столбце 6 таблицы 2 произведены соответствующие вычисления:

H(A)=3,3670 бит/символ.

Вычислим коэффициент относительной эффективности по формуле (17)

(17)

и коэффициент статистического сжатия – по формуле (18)

(18)

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