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 also kein Wort, welches identisch mit dem Anfang eines anderen 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.
Mit Hilfe der Shannon-Fano-Kodierung oder der Huffman-Kodierung lassen sich Kodierungen konstruieren, 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 Telefonnummern eines Telefonbuchs eines Vorwahlbereichs genügen ebenfalls der Fano-Bedingung. Dies ist notwendig, weil einige Telefone sofort wählen und beim ersten „Treffer“ verbinden.
- Die deutsche Sprache hingegen genügt nicht der Fano-Bedingung, weil z. B. „bei“ ein Wort der deutschen Sprache ist und zugleich Präfix von „beide“ ist.
- Der Morsecode erfüllt die Fano-Bedingung, wenn die längere Pause zwischen zwei Zeichen als drittes Symbol der Sprache betrachtet wird. Eine Folge der beiden Symbole kurzes Signal und langes Signal würde die Fano-Bedingung nicht erfüllen.
Formale Definition
Sei eine Sprache und das leere Wort. erfüllt die Fanobedingung, ist also präfixfrei genau dann, wenn ein Gefüge von zwei Wörtern der Sprache nur dann ein Wort sein kann, wenn einer der Bestandteile das leere Wort ist:
Automat
Ein deterministischer Kellerautomat, der mit leerem Keller akzeptiert, erfüllt genau die Fano-Bedingung.
Literatur
- Rainer Malaka, Andreas Butz, Heinrich Hußmann: Medieninformatik: Eine Einführung. Pearson Studium, München 2009, ISBN 978-3-8273-7353-3, S. 74–77.