Übungsaufgaben

Lauflängencodierung

Aufgabe 1: Binärbild decodieren

Sie erhalten eine Binärdatei, die ein Schwarz-Weiß-Bild der Größe 8 × 8 Pixel in bitweise lauflängencodierter Form enthält. Nachdem Sie die Binärdaten in Dezimalzahlen übersetzt haben, erhalten Sie die folgende Zahlenfolge:

2, 4, 4, 1, 2, 1, 2, 15, 0, 2, 6, 4, 2, 15, 0, 4

Sie wissen, dass die lauflängencodierten Bilddaten mit “weiß” beginnen.

• Skizzieren Sie das resultierende Bild.
• Das Bild wurde mit 4 Bit pro Lauflänge codiert. Wie groß ist die komprimierte Datei in Bit?
• Welchen Kompressionsfaktor hat die Lauflängencodierung hier im Vergleich zu einer unkomprimierten Bilddarstellung mit 8 ⋅ 8 = 64 Bit?

Wenn die Lauflänge mit 3 Bit statt 4 Bit codiert wird, lassen sich nur die Lauflängenwerte 0–7 direkt darstellen, statt wie oben 0–15.

• Geben Sie die Zahlenfolge (als Dezimalzahlen) an, die Sie erhalten, wenn das Bild mit 3 Bit pro Lauflänge lauflängencodiert wird. Lesen Sie dazu die Werte am decodierten Bild ab oder überlegen Sie, welche Werte sich im Vergleich zur oben dargestellten Zahlenfolge ändern.
• Wie groß ist die komprimierte Datei nun in Bit?
• Welchen Kompressionsfaktor erreicht die Lauflängencodierung nun?

Aufgabe 2: DNS-Sequenz komprimieren

In der Aufgabe DNS-Sequenzen zur Einführung in die Codierung wurden DNS-Sequenzen betrachtet, die aus den Buchstaben A, C, G und T bestehen.

Da diese Sequenzen aus nur 4 verschiedenen Buchstaben bestehen, sind Zeichenwiederholungen nicht unwahrscheinlich. In dieser Aufgabe sollen DNS-Sequenzen daher mittels Lauflängencodierung komprimiert werden.

• Geben Sie die folgende DNS-Sequenz in lauflängencodierter Form an (Leerzeichen dienen hier nur zur besseren Lesbarkeit). Verwenden Sie dazu die einfache Form der Lauflängencodierung ohne Markierungszeichen, in der auch einzelne Zeichen im Format Zeichen Lauflänge dargestellt werden:
  AAA CCT TTT AAA AGG

  • Wie viele Bit werden hier für die komprimierten Daten benötigt, wenn jeder Buchstabe und jede Lauflänge mit jeweils 2 Bit dargestellt werden?
  • Wie viele Bit wären für eine unkomprimierte Darstellung mit 2 Bit pro Zeichen nötig?
  • Welchen Kompressionsfaktor liefert die Lauflängencodierung hier?

• Die Sequenz wird nun um 12 einzelne Zeichen am Ende erweitert:
  AAA CCT TTT AAA AGG ACT ACT ACT ACT

  • Wie viele Bit sind nun jeweils für die komprimierten und unkomprimierten Daten nötig? Was stellen Sie hier fest?

• Verwenden Sie nun die Lauflängencodierung mit Markierungszeichen und komprimieren Sie dabei Zeichenwiederholungen erst ab einer Lauflänge von 3 im Format Markierungszeichen Zeichen Lauflänge. Als Markierungszeichen wird hier der Buchstabe G festgelegt.

  • Welche Ausgabe liefert die Lauflängencodierung nun?
  • Wie viele Bit sind nun für die komprimierten Daten nötig?

Huffman-Codierung

Aufgabe 3: Textdaten codieren

Codieren Sie die folgende Textnachricht mit der Huffman-Codierung:

ONINOOONOKIMONO

Skizzieren Sie den resultierenden Huffman-Baum und ermitteln Sie die Binärcodes für jedes einzelne Zeichen.

Beantworten Sie anschließend die folgenden Fragen zur Kompressionsstärke des Huffman-Codes:

• Wie viele Bit werden insgesamt zur Codierung der Nachricht mit Ihrem Huffman-Baum benötigt?
• Wie viele Bit werden zur Codierung der Nachricht benötigt, wenn die Nachricht im ASCII-Format mit 1 Byte pro Zeichen gespeichert wird?
• Welche Kompressionsfaktor erhalten Sie hier im Vergleich zur ASCII-Codierung?
• Wie viele Bit wären zur Codierung der Nachricht nötig, wenn Sie jeden Buchstaben, der vorkommt, durch einen Binärcode mit der gleichen Länge darstellen würden?

Aufgabe 4: Textdaten decodieren

Decodieren Sie den folgenden binären Huffman-Code und ermitteln Sie die codierte Textnachricht:

001010110110000011101011

Zur Decodierung ist der folgende Huffman-Baum gegeben:

LZW-Codierung

Aufgabe 5: Textdaten codieren

Codieren Sie die folgende Textnachricht mit dem LZW-Algorithmus und geben Sie die codierte Nachricht an (es reicht dabei, die Nummern in der Ausgabe als Dezimalzahlen anzugeben):

TINTININTINTENTINT

Vervollständigen Sie dazu das Wörterbuch, das während der Codierung entsteht. Das Wörterbuch enthält initial die folgenden Einträge:

Für Fortgeschrittene: Geben Sie die Ausgabe des LZW-Algorithmus im Binärformat an. Beachten Sie dabei, dass die Anzahl an Bitstellen, mit denen die Codewörter jeweils ausgegeben werden, im Laufe der Codierung ansteigt.

Aufgabe 6: Textdaten decodieren

Sie erhalten eine Textdatei, die mit dem LZW-Algorithmus komprimiert wurde. Nachdem Sie die Binärdaten in Dezimalzahlen übersetzt haben, erhalten Sie die folgende Zahlenfolge:

0, 0, 2, 3, 1, 4, 9, 8, 2, 6, 10

Decodieren Sie die Zahlenfolge in die ursprüngliche Textnachricht und rekonstruieren Sie dabei das Wörterbuch. Sie wissen dabei, dass das Wörterbuch initial die folgenden Einträge enthält: