Fano-Bedingung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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. 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[Bearbeiten]

  • 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 „beispielsweise“ 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[Bearbeiten]

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[Bearbeiten]

Ein deterministischer Kellerautomat, der mit leerem Keller akzeptiert, erfüllt genau die Fano-Bedingung.