2.4 Huffman-Komprimierung (1952)

Konstruiere den Code-Baum bottom-up.

Bilde Wald mit Blaettern mit Symbolen, gewichtet mit Haeufigkeiten
While noch_kein_Baum
   Seien L0, L1 die beiden Wurzeln mit kleinstem Gewicht
   Bilde Vater L mit Soehnen L0, L1
      (Kanten erhalten 0/1, Vater erhaelt Summe der Sohngewichte)
end;

Nachrichtenlänge beträgt 87 Bit.

Satz: Huffman nie länger als Shannon-Fano !
$\cong$ Unix-utility pack, komprimiert auf 60 % bei Textfiles.

Verteilung der ASCII-Zeichen im Spiegelartikel Multimedia

$$\hookleftarrow \bigsqcup$$ 1 ! 56 `` 1 '

9 ( 9 ) 163 , 71 - 135 .

4 / 42 0 16 1 13 2 11 3

11 4 13 5 6 6 5 7 6 8

11 9 20 : 1 ; 2 ? 60 A

57 B 24 C 87 D 40 E 52 F

40 G 31 H 23 I 16 J 58 K

20 L 86 M 31 N 10 O 49 P

1 Q 21 R 80 S 51 T 19 U

31 V 35 W 1 Y 27 Z 2 [

2 ] 679 a 189 b 357 c 571 d

2198 e 175 f 309 g 519 h 1099 i

14 j 209 k 557 l 346 m 1392 n

407 o 127 p 9 q 969 r 636 s

819 t 482 u 94 v 154 w 18 x

17 y 139 z 1 Ä 1 Ü 31 ß

68 ä 35 ö 67 ü

Häufigkeit einiger Buchstaben im Spiegelartikel Multimedia

$$\log_{2}^{}$$ Symbol Anzahl P(x) Informationsgehalt

a 679 0.14 2.88 1955.23

b 189 0.04 4.72 892.95

c 357 0.07 3.80 1359.12

d 571 0.11 3.13 1786.94

e 2198 0.44 1.18 2604.35

f 175 0.04 4.83 846.24

g 309 0.06 4.02 1240.75

h 519 0.10 3.27 1695.70

4997 12381.28 = 82 % von 14991 (bei 3 Bit pro Zeichen)

Huffman-Code-Baum für einige Buchstaben im Spiegelartikel Multimedia

Symbol Anzahl Code Codelänge

a 679 110 2037

b 189 11101 945

c 357 1011 1428

d 571 100 1713

e 2198 0 2198

f 175 11100 875

g 309 1010 1236

h 519 1111 2076

12508 = 83 % von 14991