Begleitmaterial zum Unterricht M114 «Verluslose Kompression»

Die verlustlose Kompression von Daten

Grundsätzlich wird bei der Datenkompression versucht, redundante Informationen zu entfernen. Dazu werden die Daten in eine Darstellung überführt, mit der sich Informationen in kürzerer Form darstellen lassen. Diesen Vorgang übernimmt ein Kodierer und man bezeichnet den Vorgang als Kompression oder Komprimierung. Die Umkehrung bezeichnet man als Dekompression oder Dekomprimierung. Man spricht von verlustfreier Kompression, wenn aus den komprimierten Daten wieder alle Originaldaten gewonnen werden können. Das ist beispielsweise bei der Kompression ausführbarer Programmdateien notwendig. Bei der verlustbehafteten Kompression können die Originaldaten aus den komprimierten Daten meist nicht mehr exakt zurückgewonnen werden, das heisst, ein Teil der Information geht verloren. Solche Verfahren werden häufig zur Bild- oder Videokompression und Audiodatenkompression eingesetzt.

Einstieg: Ein verlustloses Komprimierungsverfahren aus dem 18. Jahrhundert

Der Morsecode ein historisches Verfahren (1838, Samuel Morse und Alfred Lewis Vail) zur verlustlos komprimierten Übermittlung (akustisch, elektrisch oder optisch) von Buchstaben, Zahlen und weiteren Zeichen in Seefunk und Telegrafie.

Die Codes haben unterschiedliche Codelängen. Häufig verwendete Zeichen erhalten einen kurzen Code, seltene einen langen. Ein Beispiel zu Morsecodes: Welche Botschaft beinhaltet die folgende Morsecodesequenz Morsecodebeispiel.mp3? Die Grenzen dieses Codes soll nun das folgende Beispiel aufzeigen. Was kann diese Codesequenz alles bedeuten:
« • • – • • • • – »?

  • « • • | – • • | • | • – » = IDEA
  • « • • – | • • • | • – » = USA
  • « • • – | • • • • | – » = UHT (Abbk. Ultra-High Temperatur)
  • « • • – • | • • • – » = FV (Abbk. Fussballverein)

Also keinesfalls eindeutig! Der Nachteil beim Morsecode liegt darin, dass es ohne spezielles Trennzeichen (Delimiter) oft Missverständnisse geben kann, wo das Zeichen beginnt und wo es endet. Dieses Problem besteht z.B. bei der Huffman-Kodierung nicht, weil hier die Eigenschaft erfüllt sein muss, dass kein Codewort der Beginn eines anderen Codewortes sein darf. Die Huffman-Codierung werden wir in einem späteren Abschnitt behandeln.

1.0 Studium der verlustlosen Komprimierungsverfahren

Erarbeiten sie die Theorie zu folgenden Themen:

  • Huffman
  • RLC
  • BWT
  • LZW

und erstellen sie eine Zusammenfassung in der Grössenordnung von 1..2 Seiten. Etwa so, wie wenn sie einen Spickzettel für eine Prüfung zusammenstellen würden. Sie finden z.B. auf dieser Webseite entsprechende Fachbeiträge.

1.1 Übung zu Huffman-Kodierung

Erstellen sie den Huffman-Code für die Textzeile: «GREIFENSEE SCHIFFFAHRT». Beachten sie, dass das Leerzeichen zwischen Greifensee und Schifffahrt auch ein zu codierendes Zeichen ist. Vergleichen sie die Codeeffizient gegenüber der ASCII-Codierung.

1.2 Übung zu RLC

Erstellen sie den RL-Code für das folgende Bitmap. Vergleichen sie den Speicherbedarf des Bitmap's mit und ohne RLC. Bei welchen Bildern ist RLE besonders effizient, wo eher nicht?

1.3 Übung zu BWT

  • Erstellen sie die BWT-Transformation für das Wort «ANANAS» und überprüfen sie mit der rücktransformation ihr Resultat.
  • Sie erhalten den Code «IICRTGH6» in der Burrows-Wheeler-Transformation. Was verbirgt sich dahinter?

1.4 Übung zu LZW

  • Erstellen sie die LZW-Codierung für das Wort «ANANAS» und überprüfen sie mit der Dekodierung ihr Resultat.
  • Sie erhalten den LZW-Code «ERDBE<256>KL<260>». Was verbirgt sich dahinter?

Lösung zu 1.1 Huffman-Kodierung

Erstellen sie den Huffman-Code für die Textzeile: «GREIFENSEE SCHIFFFAHRT». Beachten sie, dass das Leerzeichen zwischen Greifensee und Schifffahrt auch ein zu codierendes Zeichen ist. Vergleichen sie die Codeeffizient gegenüber der ASCII-Codierung.

Lösung zu 1.2 RLC

Erstellen sie den RL-Code für das folgende Bitmap. Vergleichen sie den Speicherbedarf des Bitmap's mit und ohne RLC. Bei welchen Bildern ist RLE besonders effizient, wo eher nicht? =
Ohne RLC: 11111111111'00'111111'00'1111'000000'11'000000'1111'00'111111'00'11111111111 = 64 Bit
Beginnend bei Rot wechseln sich die beiden Farben ständig ab:

RLC Dezimal: 11 / 2 / 6 / 2 / 4 / 6 / 2 / 6 / 4 / 2 / 6 / 2 / 11
4 Bit ergeben die Anzahl nacheinander angeordneten Pixel's

RLC Binär: 1011'0010'0110'0010'0100'0110'0010'0110'0100'0010'0110'0010'1011 = 52 Bit

Lösung zu 1.3 BWT

  • Erstellen sie die BWT-Transformation für das Wort «ANANAS» und überprüfen sie mit der rücktransformation ihr Resultat. = SNNAAA1
  • Sie erhalten den Code «IICRTGH6» in der Burrows-Wheeler-Transformation. Was verbirgt sich dahinter? = RICHTIG

Lösung zu 1.4 LZW

  • Erstellen sie die LZW-Codierung für das Wort «ANANAS» und überprüfen sie mit der Dekodierung ihr Resultat. = AN«256»AS
  • Sie erhalten den LZW-Code «ERDBE<256>KL<260>». Was verbirgt sich dahinter? = ERDBEERKLEE