Datenkompression: Verlustfreie Verfahren: Statistische Verfahren: Präfix Codes

zurück

5 Verlustfreie Verfahren

5.1 Statistische Verfahren

5.1.1 Der Morse Code

5.1.2 Shannon-Fano Codierung

5.1.3 Huffman Codierung

5.1.4 Präfixfreie Codes

5.1.5 MNP - MicroCom Network Protokoll

5.1.6 Arithmetische Codierung

5.1.7 Adaptive Arithmetische Codierung

5.1.8 Quasiarithmetische Codierung

5.1.9 CABAC

5.1.10 Dynamische Markov Codierung

5.1.11 PPM

5.1.12 BWT - Burrows-Wheeler-Transformation

5.1.13 BWCA - Burrows-Wheeler Kompressions Algorithmus

Präfix Codes

Präfix-Codes werden auch als präfixfreie Codes bezeichnet. Zwei Beispiele für präfixfreie Codes haben Sie schon kennengelernt. Das Erste war der Shannon-Fano-Code und der zweite war der Huffman-Code. Daneben gibt es eine Reihe weiterer Codes, mit denen auch unendlich große Alphabete codiert werden können.

Ein präfixfreier Code wird genau dann als präfixfrei bezeichnet, wenn ein beliebiges gültiges Codewort nicht der Beginn eines anderen gültigen Codewortes ist. Ein nicht präfixfreier Code ist darauf angewiesen, dass man die codierten Textsymbole mit Hilfe von Trennzeichen markiert. Dieses Trennsymbol dient als Zusatzsymbol, durch dass dieser Code quasi präfixfrei wird. Die eindeutige Decodierbarkeit eines Codes ist ein sicheres Indiz für die Präfixfreiheit eines Codes.

Angenommen Sie lesen das Wort 'Urinstinkt' so kann hier der Effekt des Trennsymbols bestens erläutert werden, mit einem Trennsymbol erhielten Sie beispielsweise 'Urin stinkt'. Wie man hier schön sehen kann, ist das Wort 'Urin' der Beginn eines anderen Wortes in diesem Fall 'Urinstinkt'. Wenn man das Trennzeichen vergisst und man sagen möchte dass 'Urin stinkt' bekommt der Satz einen völlig anderen Sinn. Im Falle von Codes kann eine fehlerhafte Decodierung dazu führen, dass alle weiteren Folgesymbole einen völlig anderen Text/Sinn ergeben. Die Präfixfreiheit ließe sich am besten dadurch erklären, dass es vielleicht das Wort 'Urinstikt' geben darf, jedoch nicht eines der Worte 'U', 'Ur', 'Uri', 'Urin', 'Urins', 'Urinst', 'Urinsti', 'Urinstin' und 'Urinstink'. Das Trennsymbol sorgt für die einwandfreie Decodierierbarkeit (Lesbarkeit) des Textes. Das Trennsymbol löst das Problem der Nichteindeutigkeit bei der Decodierung.

Bei der Datenkompression ist ein solches Extrasymbol als Trennzeichen zwischen zwei Symbolen (Codeworte) nicht sehr effizient. Statt dessen verändert man den Code und damit dessen Eigenschaft so, dass man zwei beliebige Codeworte auch ohne Trennsymbole hintereinander schreiben kann, ohne die eindeutige Decodierbarkeit zu gefährden. Der Schlüssel für die eindeutige Decodierbarkeit liegt darin, dass jedes gültige Codewort nicht der Beginn eines jeden anderen Codewortes ist.

Codierung

Decodierung

schnelle Alternativen

Tabellengestützte Decodierverfahren

Golomb-Codes

Solomon Wolf Golomb stellte in einer Arbeit im Jahr 1966 [1] in der Zeitschrift IEEE Transactions on Information Theory IT-12(3):399–401 einen Code vor, der sich genau dann optimal verhält, wenn positive Zahlen codiert werden müssen, die die eine besondere geometrische Verteilung haben.

Wenn, die Wahrscheinlichkeit eines Ereignisses $\mathbf {p}$ sehr viel größer ist als seine Gegenwahrscheinlichkeit $\mathbf {q} =(1-\mathbf {p} )$ ist($\mathbf {p} >>(1-\mathbf {p} )$), so ist die naheliegende Repräsentationen in Form einer Lauflängencodierung nicht sehr effizient.

$P(n)=p\cdot (1-p)^{n+1}$

Der Golombcode ist optimal, wenn $(1-p)^{b}+(1-p)^{b+1}\leq 1<(1-p)^{b-1}+(1-p)^{b}$

Es ist nicht nötig für diese Verteilung den Huffmanalgorithmus zu bemühen. der Code kann einfacher konstruiert werden.

$q=\left\lfloor {\frac {\left(x-1\right)}{b}}\right\rfloor$

q ist das Ergebnis der Ganzzahldivision durch b

r ist der Rest der Ganzzahldivision

$r=x-qb-1$

b = Bernoulli ...

Golombcode m = 1

n	G(n)	Codewort	n	G(n)	Codewort
0	${\frac {1}{2}}$	0	6	${\frac {1}{128}}$	1111110
1	${\frac {1}{4}}$	10	7	${\frac {1}{256}}$	11111110
2	${\frac {1}{8}}$	110	8	${\frac {1}{512}}$	111111110
3	${\frac {1}{16}}$	1110	9	${\frac {1}{1024}}$	1111111110
4	${\frac {1}{32}}$	11110	10	${\frac {1}{2048}}$	11111111110
5	${\frac {1}{64}}$	111110	11	${\frac {1}{4096}}$	111111111110
$\dots$	$\dots$	$\dots$	$\dots$	$\dots$	$\dots$

Dieser Code hat die Eigenschaft eine bestimmte Verteilung nachzubilden. Wenn man ein Alphabet codieren muss welches diese Verteilung aufweist, so ist dieser Code sehr geeignet. Dieses Ergebnis ist ähnlich einem einem entarteten Huffmanbaum, bis auf das letzte Element. Dieser Code ist ein sogenannter Kommacode, das Komma wird durch die Zahl 0 repräsentiert.

$\sum _{n=0}^{\infty }G(n)=1$

Rice-Codes

Robert Rice - spezialfall des Golombcodes, bei denen modulo einer Zahl $2^{k}$ gearbeitet wird. Dann benutzt man einfache Bitmaskierungen, um den Code zu konstruieren.

Elias-Codes

Die Elias-Codes wurden in der folgenden Arbeit vorgestellt: Elias, P. Universal Codeword Sets and Representations of the Integers - IEEE Transactions on Information Theory 21, 2 (März 1975), 194-203.

Elias-Codes können ohne Modifikation nur positive Werte größer als 0 darstellen. Alles in allem lassen sich mit diesen Codes Zahlen universell darstellen, bspw. solche die sehr groß sein können, ohne dass man ein extra Alphabet erzeugen muss. Das ist beispielsweise notwendig, wenn vor dem Beginn der Codierung nicht klar ist, welche Zahlenwerte codiert werden müssen. Kurzum, wenn der zu erwartende Wertebereich nicht bekannt ist.

Die Codes sind nicht besonders effizient, dafür aber universell und werden vergleichsweise selten eingesetzt.

Fibonacci-Codes

0	1	2	3	4	5	6	7	8	9	10	11	12	13
1	1	2	3	5	8	13	21	34	55	89	144	233	377