2.3 Shannon/Fano-Komprimierung

Entwickelt 1960 bei Bell Labs/MIT.

Konstruiere den Code-Baum top-down:

Bilde Wurzel mit Liste aller Symbole,
            gewichtet mit Haeufigkeiten

While Blaetter-nicht-einelementig do
   Sei L die Liste eines mehrelementigen Blattes
   Bilde zwei etwa gleichgewichtige Listen L0, L1
   und haenge sie als Soehne an Liste L
      (Kanten erhalten 0/1)
end;

Zusätzlich zur codierten Nachricht muß der Baum übertragen werden.

Beispiel: Die Zeichen a, b, c, d, e sind in einem Text wie folgt verteilt:

$$\log_{2}^{}$$ Symbol Häufigkeit P(x) Informationsgehalt

a 15 0.38 1.38 20.67

b 7 0.18 2.48 17.35

c 6 0.15 2.70 16.20

d 6 0.15 2.70 16.20

e 5 0.13 2.96 14.82

39 1.00 85.25

Nach Anwendung des Algorithmus entsteht folgender Codebaum:

Die Nachrichtenlänge beträgt 89 Bit, der Informationsgehalt beträgt 85.25 Bit.