Алгоритм на псевдокоде
Построение кода Фано
Обозначим
P–массив вероятностей символов алфавита
L – левая граница обрабатываемой части массива P
R– правая граница обрабатываемой части массива P
k – длина уже построенной части элементарных кодов
С – матрица элементарных кодов
Length – массив длин элементарных кодов
SL – сумма элементов первой части массива
SR – сумма элементов второй части массива.
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
4.3 Алфавитный код Гилберта – Мура
Е. Н. Гилбертом и Э. Ф. Муром был предложен метод построения алфавитного кода, для которого .
Пусть символы алфавита некоторым образом упорядочены, например, a1≤a2≤…≤an. Код называется алфавитным, если кодовые слова лексикографически упорядочены, т.е. .
Процесс построения кода происходит следующим образом.
1. Вычислим величины Qi, i=1,n:
Q1=p1/2,
Q2=p1+p2/2,
Q3=p1+p2+p3/2,
…
Qn=p1+p2+…+pn-1+pn/2.
2. Представим суммы Qi в двоичном виде.
3. В качестве кодовых слов возьмем младших бит в двоичном представлении Qi, .
Пример. Пусть дан алфавит 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. Построенный код приведен в таблице 8.
Таблица 8 Код Гилберта-Мура
ai | Pi | Qi | Li | кодовое слово |
a1 a2 a3 a4 a5 a6 | 1/23≤0.18 1/23≤0.18<1/22 1/22≤0.36<1/21 1/24≤0.07 1/24≤0.09 1/24≤0.12 | 0.09 0.27 0.54 0.755 0.835 0.94 |
Средняя длина кодового слова не превышает значения энтропии плюс 2. Действительно,
Lср=4.0.18+4.0.18+3.0.36+5.0.07+5.0.09+5.0.12=3.92<2.37+2
Дата добавления: 2019-02-07; просмотров: 283;