Datenkompression und Dateiformate

Die Fano-Bedingung

Was ist das?

Die Fano-Bedingung geht auf den Italiener Robert Fano zurück und lautet wissenschaftlich exakt formuliert: Kein Kodewort darf als Präfix eines anderen Kodewortes auftreten.
Was bedeutet das aber?
Das erklärt man am Besten an einem Beispiel: das wohl berühmteste Beispiel ist der Morse-Code. Denn wenn man einen Text in Morsecode übersetzt muss nach jedem Zeichen ein Trennzeichen erfolgen. Beispiel mit | als Trennzeichen:
INFORMATIK MACHT SPASS
. . | _ . | . . _ . | _ _ _ | . _ . | _ _ | . _ | _ | . . | _ . _ | _ _ | . _ | _ . _ . | . . . . | _ | . . . | . _ _ . | . _ | . . . | . . .
Diesen Text könnte man nun mittels Morsecodetabelle (wenn man diese nicht schon im Kopf hat) wieder zurückübersetzen. Was passiert aber nun wenn man die Pausen weglässt? Schauen wir es uns an:
. . _ . . . _ . _ _ _ . _ . _ _ . _ _ . . _ . _ _ _ . _ _ . _ . . . . . _ . . . . _ _ . . _ . . . . . .
Das Ergebnis sieht erstmal nicht unbedingt schlechter aus, aber was passiert wenn man den Text zurückübersetzen möchte? Probieren wir es aus. Das erste Zeichen: . - könnte ein E sein oder . . könnte ein I sein oder . . _ könnte ein U sein oder . . _ . könnte ein F sein, was ist nun aber richtig? Diese Frage lässt sich nicht beantworten, außer man kennt den Originaltext, wovon wir jetzt aber nicht ausgehen wollen, da dies in der Praxis nicht der Fall sein wird.
 
Zusammenfassend lässt sich also sagen, dass ein Code für ein Zeichen nicht der Anfang eines Codes für ein anderes Zeichen sein darf. Die Fano-Bedingung ist der zweite wichtige Grundsatz der Huffman-Kodierung.

Beispiele:

nicht gegen die Fano-Bedingung verstoßen:

gegen die Fano-Bedingung verstoßen:

Wie kann man aber mit 2 Zuständen Dinge komprimieren?

Als 2 Zustände wähle ich die binären Zustände 0 und 1. Man kann z.B. definieren, dass ein Code immer auf 0 enden muss. So ist klar, wann der nächste Buchstabe beginnt. Muss man nur wenige verschiedene Zeichenketten codieren, bietet sich ein Baum an, bei dem man definiert: 0 ist eine Verzweigung nach links und eine 1 ist eine Verzweigung nach rechts. Für die Buchstaben A bis E ergibt das:

Zeichenbaum für die Zeichen A bis E

Wie man sicherlich schon erkennen kann ist dieses Verfahren bei weitem nicht optimal, so ergeben sich bereits bei 10 verschiedenen Zeichen unnötig lange Codes.

Mit dem Thema der optimalen Bäume beschäftigte sich lange Jahre David Huffman und hat ihn gefunden.

Über diese Ausarbeitung | Begriffe © Johannes Uhlig, diese Seite darf im Rahmen der Weiterbildung der eigenen Person verwendet werden. © | nach oben