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 $\mathbf {\mathit {L}}$ eine Sprache und $\varepsilon$ das leere Wort. $\mathbf {\mathit {L}}$ erfüllt die Fanobedingung, ist also präfixfrei genau dann, wenn ein Gefüge $uv$ von zwei Wörtern der Sprache nur dann ein Wort sein kann, wenn einer der Bestandteile das leere Wort ist:

$\forall u,v,w\in \mathbf {\mathit {L}} :(w=uv\implies u=\varepsilon \lor v=\varepsilon )$

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.