Codierung variabler Länge

In der Codierungstheorie ist die Codierung variabler Länge ein Zeichencodierungsverfahren , bei dem Codes unterschiedlicher Länge verwendet werden, um einen Zeichensatz (ein Repertoire an Symbolen) zur Darstellung in einem Computer zu codieren . ^{[ 1 ]} Das entsprechende Konzept in der Informatik ist Bitfolge .

Codes variabler Länge ermöglichen die fehlerfreie Komprimierung und Dekomprimierung von Datenquellen und deren symbolweises Auslesen. Eine unabhängige und identisch verteilte Datenquelle lässt sich nahezu beliebig nahe an ihre Entropie komprimieren . Dies steht im Gegensatz zu Codierungsverfahren fester Länge, bei denen die Datenkomprimierung nur für große Datenblöcke möglich ist und jede Komprimierung jenseits des Logarithmus der Gesamtzahl der Möglichkeiten mit einer endlichen (wenn auch möglicherweise beliebig kleinen) Fehlerwahrscheinlichkeit einhergeht.

Aus diesen Gründen wurden sie mitunter verwendet, um englischen Text in Abenteuerspielen für frühe Mikrocomputer auf weniger Bytes zu komprimieren . Allerdings haben Festplatten , der zunehmende Arbeitsspeicher und allgemeine Komprimierungsalgorithmen solche Methoden überflüssig gemacht.

Multibyte-Kodierungen entstehen üblicherweise aus dem Bedürfnis heraus, die Anzahl der kodierbaren Zeichen zu erhöhen, ohne die Abwärtskompatibilität mit bestehenden Einschränkungen zu beeinträchtigen. Beispielsweise lassen sich mit einem Byte (8 Bit) pro Zeichen 256 mögliche Zeichen kodieren. Um mehr als 256 Zeichen zu kodieren, wäre die Verwendung von zwei oder mehr Bytes pro Kodierungseinheit naheliegend. Zwei Bytes (16 Bit) würden 65.536 mögliche Zeichen ermöglichen, eine solche Änderung würde jedoch die Kompatibilität mit bestehenden Systemen beeinträchtigen und wäre daher möglicherweise nicht realisierbar. ^{[ a ]}

Unwahrscheinlichen Quellsymbolen können längere, wahrscheinlichen Quellsymbolen hingegen kürzere Codewörter zugewiesen werden, was zu einer geringen erwarteten Codewortlänge führt. Bekannte Beispiele für Codierungsstrategien mit variabler Länge sind die Huffman-Codierung , die Lempel-Ziv-Codierung , die arithmetische Codierung und die kontextadaptive Codierung mit variabler Länge .

Ein Multibyte-Codierungssystem minimiert Störungen in bestehender Software, indem es einige Zeichen als Einzelcodes beibehält, während andere mehrere Einheiten benötigen. Dadurch entstehen drei Einheitentypen: Einzelzeichen (bestehend aus einer einzelnen Einheit), führende Zeichen (die in einer Sequenz mit mehreren Einheiten an erster Stelle stehen) und nachfolgende Zeichen (die in einer Sequenz mit mehreren Einheiten an letzter Stelle stehen). Eingabe- und Anzeigesysteme müssen diese Strukturen verarbeiten können, die meisten anderen Softwareprogramme jedoch nicht.

Die vierstellige Zeichenkette „ I♥NY “ wird beispielsweise in UTF-8 wie folgt kodiert (dargestellt als hexadezimale Bytewerte): 49 E2 99 A5 4E 59. Von den sechs Einheiten dieser Sequenz sind 49 , 4E und 59 Einzelzeichen (für I , N und Y ), E2 ist die führende Einheit und 99 und A5 sind die nachfolgenden Einheiten. Das Herzsymbol wird durch die Kombination der führenden Einheit und der beiden nachfolgenden Einheiten dargestellt.

UTF-8 unterscheidet klar zwischen einzelnen Bytes, Vorzeichen und Nachzeichen mit sich nicht überschneidenden Wertebereichen. Ältere Kodierungen hingegen verwenden oft Werte wieder, was das korrekte Parsen von Text erschwert. Dies kann zu Fehlalarmen bei der Suche führen oder dazu, dass ein beschädigtes Byte lange Sequenzen unterbricht. In gut konzipierten Kodierungen wie UTF-8 funktioniert die Suche zuverlässig, und eine Beschädigung betrifft nur das Zeichen, das die fehlerhafte Einheit enthält.

Die Erweiterung eines Codes ist die Abbildung von Quellsequenzen endlicher Länge auf Bitfolgen endlicher Länge. Dies geschieht durch die Verkettung jedes Symbols der Quellsequenz mit dem entsprechenden Codewort des ursprünglichen Codes. Mithilfe von Begriffen der formalen Sprachtheorie lautet die präzise mathematische Definition wie folgt: Seien und zwei endliche Mengen, das Quell- bzw. Zielalphabet . Ein Code ist eine totale Funktion ^{[ 2 ]} , die jedes Symbol aus auf eine Symbolfolge über abbildet . Die Erweiterung von zu einem Homomorphismus von nach , der jede Quellsymbolfolge auf natürliche Weise auf eine Zielsymbolfolge abbildet, wird als seine Erweiterung bezeichnet . ${\displaystyle S}$${\displaystyle T}$${\displaystyle C:S\to T^{*}}$${\displaystyle S}$${\displaystyle T}$${\displaystyle C}$${\displaystyle S^{*}}$${\displaystyle T^{*}}$

Codes variabler Länge lassen sich in absteigender Reihenfolge ihrer Allgemeinheit streng verschachteln: nicht-singuläre Codes, eindeutig dekodierbare Codes und Präfixcodes. Präfixcodes sind stets eindeutig dekodierbar und diese wiederum stets nicht-singulär.

Ein Code ist nicht singulär, wenn jedes Quellsymbol auf eine andere nichtleere Bitfolge abgebildet wird; das heißt, die Abbildung von Quellsymbolen auf Bitfolgen ist injektiv .

Die Abbildung ist beispielsweise nicht nicht-singulär, da sowohl a als auch b auf dieselbe Bitfolge 0 abgebildet werden; jede Erweiterung dieser Abbildung führt zu einer verlustbehafteten (nicht verlustfreien) Codierung. Eine solche singuläre Codierung kann dennoch nützlich sein, wenn ein gewisser Informationsverlust akzeptabel ist (beispielsweise bei der Audio- oder Videokomprimierung, wo eine verlustbehaftete Codierung der Quellquantisierung entspricht ). ${\displaystyle M_{1}=\{\,{\texttt {a}}\mapsto {\texttt {0}},{\texttt {b}}\mapsto {\texttt {0}},{\texttt {c}}\mapsto {\texttt {1}}\,\}}$

Die Abbildung ist jedoch nicht singulär; ihre Erweiterung erzeugt eine verlustfreie Codierung, die für die allgemeine Datenübertragung nützlich ist (diese Eigenschaft ist aber nicht immer erforderlich). Der nicht singuläre Code muss nicht kompakter als der Quellcode sein (und in vielen Anwendungen ist ein größerer Code sogar nützlich, beispielsweise um Codierungs- oder Übertragungsfehler zu erkennen oder zu beheben oder in Sicherheitsanwendungen, um den Quellcode vor unbemerkten Manipulationen zu schützen). ${\displaystyle M_{2}=\{\,{\texttt {a}}\mapsto {\texttt {1}},{\texttt {b}}\mapsto {\texttt {011}},{\texttt {c}}\mapsto {\texttt {01110}},{\texttt {d}}\mapsto {\texttt {1110}},{\texttt {e}}\mapsto {\texttt {10011}},{\texttt {f}}\mapsto {\texttt {0}}\}}$

Ein Code ist eindeutig dekodierbar, wenn seine Erweiterung nicht singulär ist . Ob ein gegebener Code eindeutig dekodierbar ist, kann mit dem Sardinas-Patterson-Algorithmus entschieden werden .

The mapping ${\displaystyle M_{3}=\{\,{\texttt {a}}\mapsto {\texttt {0}},{\texttt {b}}\mapsto {\texttt {01}},{\texttt {c}}\mapsto {\texttt {011}}\,\}}$ is uniquely decodable (this can be demonstrated by looking at the follow-set after each target bit string in the map, because each bitstring is terminated as soon as we see a ${\displaystyle {\texttt {0}}}$ bit which cannot follow any existing code to create a longer valid code in the map, but unambiguously starts a new code).

Consider again the code ${\displaystyle M_{2}}$ from the previous section.^[2] This code is not uniquely decodable, since the string 011101110011 can be interpreted as the sequence of codewords 01110 – 1110 – 011, but also as the sequence of codewords 011 – 1 – 011 – 10011. Two possible decodings of this encoded string are thus given by cdb and babe. However, such a code is useful when the set of all possible source symbols is completely known and finite, or when there are restrictions (such as a formal syntax) that determine if source elements of this extension are acceptable. Such restrictions permit the decoding of the original message by checking which of the possible source symbols mapped to the same symbol are valid under those restrictions.

A code is a prefix code if no target bit string in the mapping is a prefix of the target bit string of a different source symbol in the same mapping. This means that symbols can be decoded instantaneously after their entire codeword is received. Other commonly used names for this concept are prefix-free code, instantaneous code, or context-free code. A special case of prefix codes are block codes, LEB128, and variable-length quantity (VLQ) codes.

For example, the mapping ${\displaystyle M_{3}}$ above is not a prefix code because we do not know after reading the bit string 0 whether it encodes an a source symbol, or if it is the prefix of the encodings of the b or c symbols. An example of a prefix code is shown below.

Example of encoding and decoding:

aabacdab → 00100110111010 → |0|0|10|0|110|111|0|10| → aabacdab

For this example, if the probabilities of ${\displaystyle ({\texttt {a}},{\texttt {b}},{\texttt {c}},{\texttt {d}})}$ were ${\displaystyle \textstyle \left({\frac {1}{2}},{\frac {1}{4}},{\frac {1}{8}},{\frac {1}{8}}\right)}$, the expected number of bits used to represent a source symbol using the code above would be:

${\displaystyle 1\times {\frac {1}{2}}+2\times {\frac {1}{4}}+3\times {\frac {1}{8}}+3\times {\frac {1}{8}}={\frac {7}{4}}}$.

As the entropy of this source is 1.75 bits per symbol, this code compresses the source as much as possible so that the source can be recovered with zero error.

• Golomb code
• Kruskal count
• Instruction set architecture § Instruction length in computing
• wchar_t wide characters
• Lotus Multi-Byte Character Set (LMBCS)
• Triple-Byte Character Set (TBCS)
• Double-Byte Character Set (DBCS)
• Single-Byte Character Set (SBCS)

• Salomon, David (September 2007). Variable-Length Codes for Data Compression (1 ed.). Springer Verlag. ISBN 978-1-84628-958-3. (xii+191 pages) Errata 1Errata 2
• Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Codes and automata. Encyclopedia of Mathematics and its Applications. Vol. 129. Cambridge, UK: Cambridge University Press. ISBN 978-0-521-88831-8. Zbl 1187.94001.Draft available online