WikiDer > Präfixcodierung

EIN Präfix-Codierung oder präfixfreie Kodierung ist ein Codierung wobei jedes Quellelement (Datenelement aus der Quelle) als a . kodiert ist Tupel (endliche Reihe) von Codeelementen (Datenelementen des resultierenden Codes), so dass der Code eines Datenelements aus der Quelle niemals der erste Teil des Codes eines anderen Symbols ist. Dadurch ist es möglich, eine Reihe von Symbolen durch Verkettung der Codes der einzelnen Symbole, d.h. durch Aneinanderreihen der Codeelemente ohne Separator. Beim Decodieren von Anfang an wird zunächst festgestellt, ob das erste Codeelement ein Code ist. Falls nicht, wird bestimmt, ob die ersten 2 Elemente zusammen einen Code bilden, und so weiter, bis festgestellt wird, dass ein erster Teil des gesamten Codes der Code eines Buchstabens ist. Das gleiche geschieht dann ab dem nächsten Codeelement usw. Dadurch wird die Dekodierung relativ einfach, im Gegensatz zu Kodierungen, bei denen die Dekodierung zwar eindeutig, aber ein "Rätsel" ist.

Beispiele sind Codierung mit fester Länge, Huffman-Codierung und Fibonacci-Kodierung.

Nehmen wir zum Beispiel den Fall, dass es sich um eine Buchstabenfolge aus den Buchstaben A, B und C handelt und dass die Codeelemente the Bits sein.

Bei einer Codierung mit fester Länge beispielsweise sind die Codes von A, B und C 00, 01 bzw. 10. CABA wird dann als 10000100 codiert. Die Entschlüsselung ist einfach, da der Code des Ganzen sehr einfach in Codes einzelner Buchstaben aufgeteilt werden kann: 10 00 01 00.

Die Huffman-Codierung auf der Grundlage der Häufigkeiten, in denen die Buchstaben in dieser einen Quelle vorkommen, macht den Code für A kürzer. Die Codes von A, B und C sind beispielsweise 0, 10 bzw. 11. CABA wird dann als 110100 codiert. Die Decodierung von Anfang an ist wie folgt: 1 ist kein gültiger Code, 11 ist es. 0 ist ein gültiger Code. 1 ist kein gültiger Code, 10 schon. 0 ist ein gültiger Code. Aufgeteilt haben wir also 11 0 10 0, was CABA ergibt. Es dauert 6 Bits anstelle von 8, spart 1/4 Teil. Im schlimmsten Fall, wo die Buchstaben A, B und C gleich häufig in der Quelle vorkommen, beträgt die Einsparung immer 1/6.

Da die Codes von A, B und C von der Quelle abhängen, müssen auch die notwendigen Bits gezählt werden. Unter dem Strich gibt es sicherlich eine Einsparung, wenn die Anzahl der Buchstaben in der Quelle mehr als das 3-fache dieser Anzahl beträgt.

Huffman-Codierung basierend auf festen Frequenzen, mit beispielsweise fester Codierung von A, B und C wie oben, ergibt manchmal einen Code von 2 Bits pro Buchstabe (nämlich wenn das A in der Quelle nicht existiert), aber im Durchschnitt weniger, und dort werden keine zusätzlichen Bits gleichzeitig benötigt, um die Verschlüsselung zu passieren.

Fibonacci-Kodierung basierend auf der Darstellung von A, B und C durch bzw. 1, 2 und 3 mit den Codes 11, 011 und 0011, CABA codiert als 00111101111. Bei der Dekodierung in Folge markiert die erste Folge 11 immer das Ende des Buchstabencodes. Der Code des Ganzen lässt sich daher leicht in Codes einzelner Buchstaben aufteilen: 0011 11 011 11.

Synchronisation

Präfix-Codierung mit z. B. den Codes 01 und 1010 für resp. A und B erleichtern die Dekodierung von 010101010101 und 101010101010 (bzw. AAAAAA und BBB). Der Versuch, von einem anderen Punkt als dem Anfang zu decodieren, würde jedoch abhängig vom genauen Startpunkt zu sehr unterschiedlichen Ergebnissen führen.

Bei der Fibonacci-Codierung ist jedoch aus einer 0 die nächste Sequenz 11 das Ende des Quellelementcodes, was eine Möglichkeit zur Synchronisation bietet (Bestimmen, wo ein Code beginnt, ohne die Codes von Anfang an zu betrachten). Die 11 Funktionen als Separator, wobei die mittlere 11 in ..011110.. nicht mit diesem Zeichen verwechselt werden sollte. Die Anzahl der Einsen in einer Reihe (wenn diese Zahl nicht 1 ist) ist jedoch immer gerade, sodass sie leicht in Paare aufgeteilt werden können. In Bezug auf den Code ohne Trennzeichen sind diejenigen aus der Codierung von 1 also die leere Zeichenfolge 0, 00, 10.000, 100, 010, 0000, 1000, 0100, 0010, 1010, 00000, 10000, .. (alle Codes, die endet nicht mit 1, wenn es also nicht die leere Zeichenfolge ist, endet sie mit 0 und ohne die Sequenz 11). Ab der Codierung von 2 kann die Notation noch kompakter sein, indem die letzte 0 weggelassen wird: die leere Zeichenfolge 0, 1, 00, 10, 01.000, 100, 010, 001, 101, 0000, 1000, .. (alle Codes ohne die Folge 11; die Reihenfolge ist nach Länge, dann nach Zahlenwert als umgekehrte Binärzahlen). So gesehen kann 011 als Trennzeichen betrachtet werden, vorausgesetzt, der Code für 1 einschließlich des dahinter liegenden Trennzeichens ist nur 11.