2.6. Метод Хаффмана.

Метод полягає в побудові кодового дерева Хаффмана, положення символа на якому визначається частотою (ймовірністю) його появи. Реалізація методу здійснюється по таких кроках:

1. Всім символам ставиться у відповідність одна з вершин дерева.

2. Об’єднуємо дві вершини з мінімальними частотами (вершина з більшою частотою зліва, а з меншою – справа) і для нової вершини вказуємо сумарну частоту.

3. Переходимо на пункт 2, доки не об’єднаємо всі вершини.

4. Обходимо дерево зверху і визначаємо розряди коду по такому правилу: перехід вліво – розряд =1, перехід вправо – розряд = 0 (рис.3).

Для реалізації методу можна використати таку таблицю

c 22 22 22 26 32 42 58 100 01

e 20 20 20 22 26 32 42 00

h 16 16 16 20 22 26 111

l 16 16 16 16 20 110

a 10 10 16 16 100

k 10 10 10 1011

m 4 6 10101

b 2 10110

В цій таблиці сумуванням двох останніх елементів стовпця визначається новий елемент, який вставляється у відповідне місце нового стовпця. Сумування продовжується доки не будуть просумовані всі елементи. Отриманий результуючий елемент відповідає кореневій вершині дерева.

Рис. 3.

Нижче приведений можливий варіант програми і результати її роботи

implicit integer*2(j),character*1(z)

dimension zmn(8),jmn(50),jm1(50),jm2(50),jml(50),zmk(50,10)

data zmn/'c','e','h','l','a','k','m','b'/

jn=8

jmn(1)=22

jmn(2)=20

jmn(3)=16

jmn(4)=16

jmn(5)=10

jmn(6)=10

jmn(7)=4

jmn(8)=2

do 1 j=1,jn

jm1(j)=j

jm2(j)=0

1 jml(j)=0

jp=1

jk=jn

jj=jk

4 if(jp.eq.jk) go to 5

jc=jk-2

jx=jmn(jk-1)+jmn(jk)

2 jj=jj+1

jmn(jj)=jx

jm1(jj)=jk-1

jm2(jj)=jk

jml(jj)=0

if(jp.gt.jc) go to 8

if(jmn(jp).lt.jx) go to 33

jmn(jj)=jmn(jp)

jm1(jj)=jm1(jp)

jm2(jj)=jm2(jp)

jp=jp+1

go to 2

3 if(jp.gt.jc) go to 8

jj=jj+1

jmn(jj)=jmn(jp)

jm1(jj)=jm1(jp)

jm2(jj)=jm2(jp)

jml(jj)=0

jp=jp+1

go to 3

8 jp=jk+1

jk=jj

go to 4

9 format(' ',i4,3x,a1,4i4,1x,10a1)

5 jjj=jj

17 j1=jm1(jj)

j2=jm2(jj)

jl=jml(jj)

if(jml(j1).ne.0) go to 12

if(jl.eq.0) go to 14

do 11 j=1,jl

11 zmk(j1,j)=zmk(jj,j)

jml(j1)=jl

14 if(j2.eq.0) go to 22

zmk(j1,jl+1)='1'

jml(j1)=jml(j1)+1

12 if(j2.eq.0) go to 22

if(jml(j2).ne.0) go to 22

if(jl.eq.0) go to 24

do 21 j=1,jl

21 zmk(j2,j)=zmk(jj,j)

24 zmk(j2,jl+1)='0'

jml(j2)=jl+1

22 jj=jj-1

if(jj.gt.jn) go to 17

do 27 j=1,jjj

z=' '

if(j.le.8) z=zmn(j)

37 write(6,9) j,z,jmn(j),jm1(j),jm2(j),jml(j),(zmk(j,jk),jk=1,jml(j))

27 continue

stop

end

1 c 22 1 0 2 01

2 e 20 2 0 2 00

3 h 16 3 0 3 111

4 l 16 4 0 3 110

5 a 10 5 0 3 100

6 k 10 6 0 4 1011

7 m 4 7 0 5 10101

8 b 2 8 0 5 10100

9 22 1 0 0

10 20 2 0 0

11 16 3 0 0

12 16 4 0 0

13 10 5 0 0

14 10 6 0 4 1011

15 6 7 8 4 1010

16 22 1 0 0

17 20 2 0 0

18 16 3 0 0

19 16 4 0 0

20 16 14 15 3 101

21 10 5 0 3 100

22 26 20 21 0

23 22 1 0 0

24 20 2 0 0

25 16 3 0 3 111

26 16 4 0 3 110

27 32 25 26 0

28 26 20 21 0

29 22 1 0 2 01

30 20 2 0 2 00

31 42 29 30 0

32 32 25 26 2 11

33 26 20 21 2 10

34 58 32 33 1 1

35 42 29 30 1 0

36 100 34 35 0

3. КОНТРОЛЬНІ ЗАПИТАННЯ

1. Що таке оптимальне (ефективне) кодування?

2. На чому базуються методи ефективного кодування?

3. Вкажiть основнi етапи побудови оптимального коду методом Шеннона-Фано.

4. Вкажiть основнi етапи побудови оптимального коду методом Хаффмана.

5. Порiвняйте методи побудови оптимальних кодiв та вкажiть їх особливостi.

4. ЛАБОРАТОРНЕ ЗАВДАННЯ

1. Ознайомтесь з методами побудови оптимальних кодiв.

2. Для заданого варіанту вручну побудуйте коди методом Шеннона-Фано і методом Хаффмана.

3. Розробiть алгоритм та реалiзуйте програму побудови оптимальних кодiв методом Шеннона-Фано та Хаффмана.

4. Перевiрте роботоздатнiсть програм на тестових прикладах.

5. ОФОРМЛЕННЯ ЗВІТУ

1. Короткий опис методу та алгоритму побудови оптимального коду.

2. Тексти програм.

3. Результати тестування програм.

6. ЛІТЕРАТУРА

1. Цымбал В.П. Теория информации и кодирование.: - К.: Вища школа, 1992.

2. Лагутин О.И. Модемы. Справочник пользователя –СПб.:”Лань”,1997.