Построение оптимального кода Хаффмана (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

 

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

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

Код Шеннона

Код Шеннона позволяет построить почти оптимальный код с длинами кодовых слов Li < - log pi +1. Тогда Lcp <H(p1, …,pn)+1. Код Шеннона строится следующим образом.

1. Упорядочим символы исходного алфавита А={a1,a2,…,an} по убыванию их вероятностей: p1≥p2≥p3≥…≥pn.

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

3. Q0=0, Q1=p1, Q2=p1+p2, Q3=p1+p2+p3, …, Qn=1.

4. Представим Qi в двоичной системе счисления и возьмем в качестве кодового слова первые знаков после запятой.

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

, .

Пример. Пусть дан алфавит A={a1, a2, a3, a4, a5, a6} с вероятностями p1=0.36, p2=0.18, p3=0.18, p4=0.12, p5=0.09, p6=0.07. Построенный код приведен в таблице.

 

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

 

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

Lср= 0.36.2+(0.18+0.18).3+(0.12+0.09+0.07).4=2.92< 2.37+1

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

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

p0:=0, Q0:=0

DO (i=1,…,n)

Qi:= Qi-1+pi \

Li:= - [log2pi]

OD

DO (i=1,…,n)

DO (j=1,…,Li)

Qi-1:=Qi-1 *2

C[i,j]:= Qi-1

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

OD

OD

Код Фано

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

Пример. Пусть дан алфавит A={a1, a2, a3, a4, a5, a6} с вероятностями p1=0.36, p2=0.18, p3=0.18, p4=0.12, p5=0.09, p6=0.07. Построенный код приведен в таблице и на рисунке.

 

Таблица 7. Код Фано

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

 

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

Lср=0.36.2+0.18.2+0.18.2+0.12.3+0.09.4+0.07.4=2.44

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

Алгоритм Фано

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

L - левая граница обрабатываемой части массива P

R- правая граница обрабатываемой части массива P

k - длина уже построенной части элементарных кодов

С - массив элементарных кодов

Length - массив длин элементарных кодов.

Fano(L,R,k)
IF (L<R)

k:=k+1

m:=Med(L,R)

DO (i=L,…,R)

IF (i≤m) C[i,k]:=0, Length[i]:= Length[i]+1

ELSE C[i,k]:=1, Length[i]:= Length[i]+1

FI

OD

Fano (L,m,k)

Fano (m+1,R,k)

FI

 

Функция Med находит медиану массива P, т.е. такой индекс L≤m≤R, что

величина минимальна.

 

Med (L,R)

SL:=0

DO (i=L,…,R-1)

SL:=SL+p[i] <сумма элементов первой части>

OD

SR:=p[R] <сумма элементов второй части>

m:=R

DO (SL ≥ SR)

m:=m-1

SL:=SL-p[m]

SR:=SR+p[m]

OD

Med:=m