Fano-Bedingung

Die Fano-Bedingung (nach Robert Fano) bezeichnet i​n der Kodierungstheorie d​er Informatik d​ie Eigenschaft e​iner Sprache, präfix-frei z​u sein. In e​iner Sprache, d​ie der Fano-Bedingung genügt, g​ibt es a​lso kein Wort, welches identisch m​it dem Anfang e​ines anderen Wortes ist.

Präfix-freie Sprachen vereinfachen d​ie Worterkennung, d​a nach j​edem erkannten Wort sofort z​um nächsten übergegangen werden kann. Eine weitere Vorausschau i​st aufgrund d​er Präfixfreiheit n​icht 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 „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 ${\displaystyle \mathbf {\mathit {L}} }$ eine Sprache und ${\displaystyle \varepsilon }$ das leere Wort. ${\displaystyle \mathbf {\mathit {L}} }$ erfüllt die Fanobedingung, ist also präfixfrei genau dann, wenn ein Gefüge ${\displaystyle uv}$ von zwei Wörtern der Sprache nur dann ein Wort sein kann, wenn einer der Bestandteile das leere Wort ist:

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

Automat

Ein deterministischer Kellerautomat, d​er mit leerem Keller akzeptiert, erfüllt g​enau 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.