Lauflängencodierung

Eine einfache Methode der verlustfreien Komprimierung von Nutzdaten ist die Lauflängencodierung (RLE1) Run Length Encoding ):

Voraussetzung: in der zu komprimierenden Zeichenfolge gibt es Zeichen, die sich wiederholen.

Idee: man gibt die Anzahl der Wiederholungen an und dann das Zeichen, das sich wiederholt.

Ein einfaches Beispiel:

Das kann man jetzt natürlich durchaus etwas ausgefeilter umsetzen. Wir betrachten dazu ein S/W BMP Bild.

P1
20 11
00000000000000000000
00000000111000000000
00000001110000000000
00000001110000111111
11111111110001111111
11111110011111111111
11100000000000000111
00000000000000011100
00000000000011100000
00000000001110000000
00000000000000000011

Nun kann man natürlich (wie oben) schreiben: 26w3s15w3s15w3s4w14s3w15s2w14s13w3s13w3s13w3s22w2s, das sind 51 ACII-Zeichen, also 51 Byte. Die Bildinformationen umfassen 220Bit - kein wirklicher Gewinn.

Nun vereinbaren wir folgenden Code:

Wir bilden Code-Worte aus 4 Bit

Das erste Bit legt die Farbe fest (0 für weiß, 1 für schwarz)

Die folgenden 3 Bit geben an, wie oft diese Farbe wiederholt wird (000 für 1 Mal, 001 für 2 Mal, 010 für 3 Mal usw.)

Das ergibt die folgende Code Tabelle:

Code	Bedeutung
0000	1 weißes Pixel
0001	2 weißePixel
0010	3 weiße Pixel
0011	4 weiße Pixel
0100	5 weiße Pixel
0101	6 weiße Pixel
0110	7 weiße Pixel
0111	8 weiße Pixel
1000	1 schwarzes Pixel
1001	2 schwarze Pixel
1010	3 schwarze Pixel
1011	4 schwarze Pixel
1100	5 schwarze Pixel
1101	6 schwarze Pixel
1110	7 schwarze Pixel
1111	8 schwarze Pixel

(A1)

Beschreibe ein Schwarz-Weiß-Bild, das gut mit Lauflängencodierung komprimiert werden kann und eines, das schlecht mit Lauflängencodierung komprimiert werden kann.