MINT lernen

Textaufgaben: Datenkompression

Eine Faxzeile mit Lauflängen codieren und prüfen, wann sich ein Huffman-Code für die Schulwetterstation lohnt.

Dein Fortschritt:
0 / 0 Aufgaben
1

Die Zeile im Faxgerät

AFB I–II

Das Sekretariat faxt ein Formular an eine Behörde. Das Faxgerät tastet das Blatt Zeile für Zeile ab; jedes Pixel ist entweder weiß (W) oder schwarz (S) und belegt roh 1 Bit. Bevor es sendet, fasst das Gerät jede Zeile mit der Lauflängencodierung zusammen. Jeder Lauf wird dabei mit 6 Bit für die Anzahl und 1 Bit für die Farbe gespeichert.

Eine Zeile des Formulars
Abgetastete Zeile (40 Pixel) Pixel 1Pixel 40
Vereinfachte Darstellung einer Zeile mit zwei schwarzen Strichen.
  1. Erstellen Sie die Lauflängencodierung der Zeile in der Schreibweise Anzahl-Zeichen.
  2. Bestimmen Sie die Größe der codierten Zeile in Bit und die Kompressionsrate.
  3. Untersuchen Sie, ab wie vielen Läufen pro Zeile die Lauflängencodierung bei dieser Zeilenlänge keinen Gewinn mehr bringt.

Hinweise

Hinweis zu Aufgabe a)
Zähle, wie viele gleichfarbige Pixel jeweils direkt nebeneinander liegen.
Hinweis zu Aufgabe b)
Wie viele Läufe hat die Zeile, und wie viel Bit kostet jeder? Rate = Originalgröße : komprimierte Größe.
Hinweis zu Aufgabe c)
Die rohe Zeile kostet immer 40 Bit. Ab welcher Anzahl von Läufen kostet die codierte Fassung genauso viel oder mehr?

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

12W3S20W5S

Erwartungshorizont zu Aufgabe b)

4 Läufe · (6 + 1) Bit = 28 Bit; roh: 40 · 1 Bit = 40 Bit.

Kompressionsrate: 40 : 28 ≈ 1,43 : 1.

Erwartungshorizont zu Aufgabe c)

Codierte Größe: n Läufe · 7 Bit. Gewinn nur, solange 7n < 40, also n ≤ 5 (35 Bit).

Ab 6 Läufen (42 Bit) ist die codierte Zeile größer als das Original; im Extremfall abwechselnd schwarz-weiß (40 Läufe) wären es 280 Bit. Lauflängencodierung lohnt sich also nur bei langen gleichfarbigen Abschnitten.

2

Die Schulwetterstation

AFB II–III

Die Wetterstation auf dem Schuldach funkt jeden Tag ein einziges Wettersymbol an den Schulserver: S (Sonne), W (Wolken), R (Regen) oder G (Gewitter). Bisher verwendet sie einen festen Code mit 2 Bit pro Symbol (S = 00, W = 01, R = 10, G = 11). In den letzten 100 Tagen kamen die Symbole unterschiedlich oft vor (Abbildung).

Die Informatik-AG will auf einen Huffman-Code umstellen. Ein Mitglied behauptet: „Ein Huffman-Code ist immer kürzer als ein fester Code mit gleich vielen Bit pro Symbol.“

Häufigkeit der Symbole an 100 Tagen
S · Sonne50W · Wolken30R · Regen15G · Gewitter5 Anzahl der Tage mit diesem Symbol
Sonnige Tage überwiegen deutlich.
  1. Zeichnen Sie den Huffman-Codebaum für diese Häufigkeiten und geben Sie den Code jedes Symbols an.
  2. Weisen Sie nach, dass der Huffman-Code für die 100 Meldungen 15 % weniger Bit braucht als der feste 2-Bit-Code.
  3. Widerlegen Sie die Behauptung des AG-Mitglieds.

Hinweise

Hinweis zu Aufgabe a)
Verschmelze immer die beiden seltensten Knoten. Links = 0, rechts = 1.
Hinweis zu Aufgabe b)
Multipliziere jede Häufigkeit mit der Codelänge und addiere. Vergleiche mit 100 · 2 Bit.
Hinweis zu Aufgabe c)
Ein einziges Gegenbeispiel genügt. Was passiert, wenn alle vier Symbole gleich oft vorkommen?

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

Schritt 1: G (5) + R (15) → Knoten 20. Schritt 2: 20 + W (30) → Knoten 50. Schritt 3: 50 + S (50) → Wurzel 100.

Mögliche Codes: S = 0, W = 10, R = 110, G = 111. Andere Zuordnungen von 0 und 1 sind richtig, wenn die Codelängen 1, 2, 3, 3 stimmen und der Code präfixfrei ist.

Erwartungshorizont zu Aufgabe b)

Huffman: 50 · 1 + 30 · 2 + 15 · 3 + 5 · 3 = 50 + 60 + 45 + 15 = 170 Bit.

Fester Code: 100 · 2 = 200 Bit. Ersparnis 30 Bit, 30 : 200 = 15 %.

Erwartungshorizont zu Aufgabe c)

Gegenbeispiel: Kommen alle vier Symbole je 25-mal vor, verschmelzen zuerst zwei Paare zu je 50 und dann beide zur Wurzel. Jedes Symbol erhält einen 2-Bit-Code – der Huffman-Code braucht genauso viele Bit (200) wie der feste Code, er ist also nicht kürzer.

Zusätzlich muss der Empfänger den Codebaum kennen; wird er mitgesendet, ist das Ergebnis sogar länger. Huffman spart nur bei ungleich verteilten Häufigkeiten. Vollständig ist die Antwort mit konkretem Gegenbeispiel und Rechnung.