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

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

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