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

Построение кода Фано

Обозначим

P–массив вероятностей символов алфавита

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

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

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

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

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

S_L  – сумма элементов первой части массива

S_R – сумма элементов второй части массива.

 

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)

S_L:= 0

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

    S_L:=S_L+ P [i]    

OD

S_R:=P [R]                

m:= R

DO (S_L ≥ S_R)

    m:=m-1

    S_L:=S_L - P [m]

    S_R:=S_R+ P [m]

OD

Med:= m

 

Порядок выполнения работы

1. Изучить теоретический материал.

2. Реализовать процедуру построения кода Фано.

3. Построить код Фано для текста на английском языке (использовать файл не менее 1 Кб). Распечатать полученную кодовую таблицу в виде:

Символ	Вероятность	Кодовое слово	Длина кодового слова

 

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

Таблица 1

 

Энтропия исходного текста	Средняя длина кодового слова

Контрольные вопросы

1. Почему код Фано считается почти оптимальным?

2. Насколько средняя длина кодового слова превосходит энтропию источника для кода Фано?

3. Какой код называется алфавитным?

4. Является ли алфавитным код Фано?

 

 

Лабораторная работа № 5

Тема: Алфавитный код Гилберта-Мура.