Wikipedia · einfach zusammengefasst · Stand
Fano-Bedingung
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- …
Inhalt3 Abschnitte
Bedeutung und Nutzen
Die Fano-Bedingung bezeichnet in der Kodierungstheorie der Informatik die Eigenschaft einer Sprache, präfix-frei zu sein. Sie ist nach Robert Fano benannt. Präfix-frei bedeutet: Kein Wort der Sprache ist zugleich identisch mit dem Anfang (Präfix) eines anderen Wortes derselben Sprache.
Dadurch wird die Worterkennung einfacher: Sobald ein Wort erkannt ist, kann sofort das nächste beginnen. Es ist keine weitere Vorausschau nötig, um zu entscheiden, ob das erkannte Zeichen- oder Wortstück bereits vollständig ist. Ein Code mit dieser Eigenschaft heißt Präfixcode.
Kodierungen, welche die Fano-Bedingung erfüllen, lassen sich mit der Shannon-Fano-Kodierung oder der Huffman-Kodierung konstruieren.
Beispiele für präfixfreie und nicht präfixfreie Sprachen
Die Sprache L = {0, 10, 110, 1110, 11110}, etwa als Kodierung der Werte 0, 1, 2, 3, 4, ist präfixfrei und erfüllt daher die Fano-Bedingung.
Auch die Telefonnummern eines Telefonbuchs innerhalb eines Vorwahlbereichs erfüllen die Bedingung. Das ist technisch notwendig, weil Telefonvermittlungsstellen, zumindest im Festnetz, eine Nummer Ziffer für Ziffer betrachten und die Verbindung sofort herstellen, sobald eine vollständige Nummer gewählt wurde.
Die deutsche Sprache erfüllt die Fano-Bedingung nicht: „bei“ ist ein deutsches Wort und zugleich Präfix von „beide“.
Morsecode erfüllt die Bedingung, wenn die längere Pause zwischen zwei Zeichen als drittes Symbol der Sprache gilt. Nur mit den beiden Symbolen kurzes Signal und langes Signal wäre die Fano-Bedingung nicht erfüllt.
Formale Bedingung und Automat
Sei L eine Sprache und ε das leere Wort. L erfüllt die Fano-Bedingung, also ist präfixfrei, genau dann, wenn ein Gefüge uv von zwei Wörtern der Sprache nur dann selbst ein Wort sein kann, wenn einer der beiden Bestandteile das leere Wort ist:
∀ u,v,w ∈ L : (w = uv ⇒ u = ε ∨ v = ε)
Dabei steht uv für die Zusammensetzung der Wörter u und v. Zusätzlich gilt: Ein deterministischer Kellerautomat, der mit leerem Keller akzeptiert, akzeptiert genau die Sprachen, die die Fano-Bedingung erfüllen.