LU04b - Komprimierung

Einleitung

In diesem Kapitel konzentrieren wir uns auf verlustfreie Verfahren zur Komprimierung von Daten. Bei diesen Verfahren können die ursprünglichen Daten wiederhergestellt werden. Zum Beispiel:

Verlustbehaftete Verfahren für Bilddateien finden Sie im Kapitel LU03d - Bildformate.

Run length encoding (RLE)

Bei diesen Verfahren werden identische Zeichen oder Zeichenketten, die mehrmals hintereinander stehen, nur einmal abgespeichert. Je nach Art der Daten kann dieses Kompressionsverfahren massive Einsparungen bringen.

Beispiel: Brief

Ein Brief besteht zu einem grossen Teil aus Leerzeichen (hier als _ dargestellt).

Text

Herr___________________________________________________________________________
Hans_Muster____________________________________________________________________
Wegweg_0_______________________________________________________________________
_______________________________________________________________________________
0000_Hier______________________________________________________________________
_______________________________________________________________________________
Sehr_geehrter_Herr_Muster______________________________________________________

Codierung

Um Speicherplatz zu sparen, wird nicht jedes Leerzeichen einzeln gespeichert. Stattdessen wird angegeben, wie oft sich ein Zeichen wiederholt.

Herr\76_\
Hans_Muster\69_\
Wegweg_0\72_\
\80_\
0000_Hier\71_\
\80_\
Sehr_geehrter_Herr_Muster\65_\

Diese Codierung kann auf alle Zeichen angewandt werden, die mehrfach hintereinander folgen.

Beispiel: Grafik

Eine Grafik besteht zum grössten Teil aus Pixeln mit der Hintergrundfarbe. Zum Beispiel hat diese Wiki-Seite, die Sie im Moment betrachten, wohl 80-90% weisse Pixel. Es wäre nun sehr ineffizient, jeden weissen Pixel einzeln zu übermitteln. Stattdessen wird einfach angegeben, wieviele weisse Pixel hintereinander folgen.

Wörterbuch für Texte

Bei diesen Verfahren wird ein Wörterbuch mit allen im Text vorkommenden Wörtern erstellt. Im eigentlichen Text wird anstelle der Wörter nur noch die Position im Wörterbuch angegeben.

Zum Entpacken der Datei, muss das Wörterbuch in der komprimierten Daten mitgegeben werden.

Beispiel

Wenn Fliegen hinter Fliegen fliegen, fliegen Fliegen Fliegen hinterher.
Wörterbuch
Index Wort
0 Wenn
1 Fliegen
2 fliegen
3 hinterher
4 hinter
Codierung
0 1 4 1 2 2 1 1 3

Je länger der Text ist, desto häufiger kommen die gleichen Wörter vor. Somit wird das Verfahren umso besser, je länger der Text ist.

Verfahren

Entropiecodierung

Bei diesen Verfahren wird jedes Zeichen durch einen unterschiedlich langen Code ersetzt. Dabei wird den häufigsten Zeichen ein kurzer, den seltenen Zeichen ein längerer Code zugeordnet. Im Gegensatz zur ASCII-Codierung haben die Zeichencodes eine variable Länge. Dadurch können häufige Zeichen mit 2 oder 3 Bits codiert werden, was eine markante Einsparung bedeutet.

Morse-Alphabet

Der im 19. Jahrhundert entwickelte Morsecode setzt eine Form der Entropiekodierung ein. Jedem Zeichen wird ein Code aus Punkten (kurzes Signal) und Strichen (langes Signal) zugeordnet. Dabei wird den häufigsten Buchstaben ein Code aus wenigen Signalen zugeordnet. Die selten genutzten Zeichen haben einen längeren Code.

Um die einzelnen Zeichen zu erkennen, wird nach jedem Zeichen eine längere Pause eingelegt. Beim Morsen mit einer Lichtquelle (z.B. Taschenlampe) gilt:

Huffman

Viele aktuelle Kompressionsverfahren nutzen (nebst anderen Verfahren) die Entropiecodierung. Die Grundlagen dazu finden Sie im Kapitel Huffman.


Marcel Suter