- Fano-Bedingung
-
Die Fano-Bedingung (nach Robert Fano) bezeichnet in der Kodierungstheorie der Informatik die Eigenschaft einer Sprache, präfix-frei zu sein. In einer Sprache, die der Fano-Bedingung genügt, gibt es kein Wort, das Präfix eines anderen Wortes ist. Informell ausgedrückt: In der Sprache existiert kein Wort welches identisch mit dem Anfang eines weiteren Wortes ist. Präfix-freie Sprachen vereinfachen die Worterkennung, da nach jedem erkannten Wort sofort zum nächsten übergegangen werden kann. Eine weitere Vorausschau ist aufgrund der Präfixfreiheit nicht nötig. Die Anwendung der Shannon-Fano-Kodierung bzw. des Huffman-Codes führen zu Kodierungen, die die Fano-Bedingung erfüllen. Ein Code, der die Fano-Bedingung erfüllt, wird Präfixcode genannt.
Beispiele
- Die Sprache L = {0, 10, 110, 1110, 11110} (z.B. als Kodierung der Werte 0,1,2,3,4) ist präfixfrei und genügt damit der Fano-Bedingung.
- Die deutsche Sprache hingegen genügt nicht der Fano-Bedingung, weil "bei" ein Wort der deutschen Sprache ist und zugleich Präfix von "Beispiel".
- Auch der Morsecode erfüllt die Fano-Bedingung nicht, deshalb benötigt man zum Dekodieren ein weiteres "Zeichen", die Pause zwischen zwei Codewörtern (Morsezeichen).
Formale Definition
Sei
eine Sprache und
das leere Wort.
Automat
Ein deterministischer Kellerautomat, der mit leerem Keller akzeptiert, erfüllt genau die Fano-Bedingung.
Wikimedia Foundation.