Алгоритм на псевдокоде

Построение оптимального кода Хаффмена (n,P)

Обозначим

n – количество символов исходного алфавита

P – массив вероятностей, упорядоченных по убыванию

C – матрица элементарных кодов

L – массив длин кодовых слов

Huffman(n,P)

IF (n=2) C[1,1]:=0, L[1]:=1

C[2,1]:=1, L[2]:=1

ELSE q:=P[n-1]+P[n]

j:=Up(n,q) <поиск и вставка суммы>

Huffman(n-1,P)

Down(n,j) <достраивание кодов>

FI

Функция Up (n,q) находит в массиве P место, куда вставить число q и вставляет его, сдвигая вниз остальные элементы.

DO (i=n-1, n-2,…,2)

IF (P[i-1]≤q) P[i]:=P[i-1]

ELSE j:=I

OD

FI

OD

P[j]:=q

Процедура Down (n,j) формирует кодовые слова.

S:=C[j,*] <запоминание j-той строки матрицы элементарных кодов в массив S>

L:=L[j]

DO (i=j,…,n-2)

C[i,*]:=C[i+1,*] <сдвиг вверх строк матрицы С>

L[i]:=L[i+1]

OD

C[n-1,*]:= S, C[n,*]:= S <восстановление префикса кодовых слов из массива S >

C[n-1,L+1]:=0, C[n,L+1]:=1

L[n-1]:=L+1, L[n]:=L+1

5. Почти оптимальное алфавитное кодирование

Рассмотрим несколько классических побуквенных кодов, у которых средняя длина кодового слова близка к оптимальной. Пусть имеется дискретный вероятностный источник, порождающий символы алфавита А={a₁,…,a_n} с вероятностями p_i = p(a_i), .

Код Шеннона

Код Шеннона позволяет построить почти оптимальный код с длинами кодовых слов L_i < - log p_i +1. Тогда L_cp <H(p₁, …,p_n)+1. Код Шеннона строится следующим образом.

1. Упорядочим символы исходного алфавита А={a₁,a₂,…,a_n} по убыванию их вероятностей: p₁≥p₂≥p₃≥…≥p_n.

2. Составим нарастающие суммы вероятностей Q_i:

Q₀=0, Q₁=p₁, Q₂=p₁+p₂, Q₃=p₁+p₂+p₃, … , Q_n=1.

3. Представим Q_i в двоичной системе счисления и возьмем в качестве кодового слова первые - log₂p_i знаков после запятой .

Для вероятностей, представленных в виде десятичных дробей, удобно определить длину кодового слова L_i из соотношения

, .

Пример. Пусть дан алфавит A={a₁, a₂, a₃, a₄, a₅, a₆} с вероятностями p₁=0.36, p₂=0.18, p₃=0.18, p₄=0.12, p₅=0.09, p₆=0.07. Построенный код приведен в таблице.

Таблица 11 Код Шеннона

ai	Pi	Qi	Li	кодовое слово
a1 a2 a3 a4 a5 a6	1/22≤0.36<1/2 1/23≤0.18<1/22 1/23≤0.18<1/22 1/24≤0.12<1/23 1/24≤0.09<1/23 1/24≤0.07<1/23	0 0.36 0.54 0.72 0.84 0.93	2 3 3 4 4 4	00 010 100 1011 1101 1110

Построенный код является префиксным. Вычислим среднюю длину кодового слова и сравним ее с энтропией. Значение энтропии вычислено при построении кода Хаффмена (H = 2.37).

L_ср= 0.36^.2+(0.18+0.18)^.3+(0.12+0.09+0.07)^.4=2.92< 2.37+1

Алгоритм на псевдокоде

Алгоритм построения кода Шеннона

p₀:=0, Q₀:=0

DO (i=1,…,n)

Q_i := Q_i-1+p_i

L_i:= -log₂p_i 

OD

DO (i=1,…,n)

DO (j=1,…,L_i)

Q_i-1:=Q_{i-1 *}2

C[i,j]:= Q_i-1

IF (Q_i-1>1) Q_i-1:=Q_i-1-1 FI

OD

OD

Код Фано

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

Пример. Пусть дан алфавит A={a₁, a₂, a₃, a₄, a₅, a₆} с вероятностями p₁=0.36, p₂=0.18, p₃=0.18, p₄=0.12, p₅=0.09, p₆=0.07. Построенный код приведен в таблице и на рисунке.

Таблица 12 Код Фано

ai	Pi	кодовое слово				Li
a1	0.36	0	0			2
a2	0.18	0	1			2
a3	0.18	1	0			2
a4	0.12	1	1	0		3
a5	0.09	1	1	1	0	3
a6	0.07	1	1	1	1	4

Рисунок 68 Кодовое дерево для кода Фано

Полученный код является префиксным и почти оптимальным со средней длиной кодового слова

L_ср=0.36^.2+0.18^.2+0.18^.2+0.12^.3+0.09^.4+0.07^.4=2.44