Präfixcodes

Präfixcodes sind Zeichencodes über einem Alphabet, bei dem kein Codewort das Präfix eines anderen Codeworts bildet. Dadurch ist der Code sofort dekodierbar: Beim Lesen des Codes lässt sich unmittelbar erkennen, wie lange jedes Symbol ist, ohne auf weitere Symbole schauen zu müssen.

Formale Eigenschaften: Für einen D-ären Alphabet gilt die Kraftbedingung Sum_i D^{-l_i} ≤ 1, wobei l_i die Längen der Codewörter sind. Ist diese Bedingung erfüllt, existiert ein Präfixcode mit diesen Längen; sie liefert auch eine notwendige Bedingung für die Machbarkeit eines Codes. Jedes Präfixcode ist eindeutig dekodierbar (instantan), doch nicht jedes eindeutig dekodierbare Code-System ist ein Präfixcode. Präfixcodes schließen also eine stärkere Eigenschaft ein, die direkte Dekodierbarkeit garantiert.

Beispiele: Ein binäres Präfixcode-Beispiel ist C = {0, 10, 11}. Keine Codefolge ist das Präfix einer anderen. Ein fehlerhaftes Beispiel ist C = {0, 01}, denn das Codewort 0 ist ein Präfix von 01. Solche Codes verweigern die Präfixfreiheit und liefern keine sofortige Dekodierbarkeit.

Zusammenhang und Anwendungen: Präfixcodes spielen eine zentrale Rolle in der Datenkompression und Kodierungstheorie. Sie bilden die theoretische Grundlage für effiziente Codierungsmethoden wie die Huffman-Kodierung, die für gegebene Symbolwahrscheinlichkeiten eine minimale durchschnittliche Codewortlänge liefert. In der Praxis werden oft binäre oder mehrstellige Präfixcodes verwendet, gelegentlich auch kanonische Huffman-Codes zur Implementierung von Code-Tabellen.