Vissza
Labor 7, haladóknak
Huffman kód
Tetszőleges szövegállomány tartalmát
tömörítsük, Huffman kódot használva.
Példa:
Ha egy
szövegállomány karakter előfordulási
statisztikája a következő:
a
|
b
|
c
|
d
|
e
|
f
|
45
|
13
|
12
|
16
|
9
|
5
|
akkor a karaktereknek megfelelő kódok a következőek
lesznek:
a
|
b
|
c
|
d
|
e
|
f
|
0
|
101
|
100
|
111
|
1101
|
1100
|
Az
elof,
az
apa
és
fiu
tömbök lépésenkénti
előállítása a következő:
0 1
2 3 4 5
elof
[45 13 12 16 9
5]
5 + 9 = 14
45 13 12 16 9 5
apa
[_ _ _ _ 6
6]
fiu
[_ _ _ _ 1
0]
0 1
2 3 4
5 6
elof
[45 13 12
16 9 5 14]
12 + 13 = 25
45 13 12
16 9 5
14
apa
[_ 7 7 _ 6
6 _]
fiu
[_
1 0 _ 1 0
_]
0 1
2 3 4
5 6 7
elof[45
13 12 16
9 5 14
25]
16 + 14 = 30
45 13 12
16 9
5
14 25
apa [_
7 7 8 6 6
8 _]
fiu [_
1 0 1 1 0
0 _]
0 1
2 3 4
5 6 7 8
elof[45
13 12 16 9 5
14 25 30]
25 + 30 = 55
45 13 12
16 9
5 14 25 30
apa [_
7 7 8 6 6
8 9 9]
fiu [_
1 0 1 1 0
0 0 1]
0 1
2 3 4
5 6 7
8 9
elof[45 13 12
16 9 5 14 25 30 55] 45 + 55 = 100
45 13 12 16 9 5 14
25 30 55
apa
[10 7 7 8 6
6 8 9 9 10]
fiu [
0 1 0 1 1
0 0 0 1 1]
0 1
2 3 4
5 6 7
8 9 10
elof[45
13 12 16 9 5
14 25 30 55 100]
apa
[10 7 7 8
6 6 8 9 9
10 11]
fiu
[0 1 0 1
1 0 0 0 1
1 vege]
A
felépített tömbök alajpján a
kódok meghatározása a következő lesz:
pl. a c-nek
megfelelő kód: 100
0 1
2 3 4
5 6 7
8 9 10
elof[45
13 12
16 9 5
14 25 30 55 100]
apa
[10 7 7
8
6 6 8 9 9
10 11]
fiu
[0 1 0 1
1 0 0 0 1
1 vege]
0 1
2 3 4
5 6 7
8 9 10
elof[45
13 12
16 9 5
14 25 30 55 100]
apa
[10 7 7
8
6 6 8 9 9
10 11]
fiu
[0 1 0 1
1 0 0 0 1
1 vege]
0 1
2 3 4
5 6 7
8 9
10
elof[45
13 12
16 9 5
14 25 30 55 100]
apa
[10 7 7
8
6 6 8 9 9
10 11]
fiu
[0 1 0 1
1 0 0 0 1
1 vege]
pl. az e-nek
megfelelő kód: 1101
0 1
2 3 4
5 6 7
8 9 10
elof[45
13 12 16 9 5
14 25 30 55 100]
apa
[10 7 7 8
6 6
8 9 9
10 11]
fiu [0 1 0
1
1
0 0 0 1
1 vege]
0 1
2 3 4
5 6
7 8 9 10
elof[45
13 12
16 9 5
14 25 30 55 100]
apa
[10 7 7
8
6 6 8
9 9
10 11]
fiu [0 1
0 1
1 0 0
0 1
1 vege]
0 1
2 3 4
5 6 7 8
9 10
elof[45
13 12
16 9 5
14 25 30 55 100]
apa
[10 7 7
8
6 6 8 9 9
10 11]
fiu [0 1
0 1
1 0 0 0 1
1 vege]
0 1
2 3 4
5 6 7 8 9 10
elof[45 13 12 16 9 5
14 25 30 55 100]
apa [10 7 7 8
6 6 8 9 9
10
11]
fiu [0 1 0 1
1 0 0 0 1
1 vege]
A megfelelő bináris fa szemléletes
felépítése, pedig a következő
lesz (lásd Cormen, Leiserson and Rivest: Algoritmusok)::
