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

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

 

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

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

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

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

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

4. Проверить выполнение неравенства Крафта-МакМиллана для полученного кода

5. Вычислить энтропию исходного файла и сравнить со средней длиной кодового слова.

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

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

2. В чем заключается теорема Крафта? Теорема МакМиллана?

3. Что такое энтропия дискретного вероятностного источника?

4. Какова основная характеристика неравномерного кода?

5. Что такое избыточность кода?

6. Почему код Хаффмана называется оптимальным?