1
Lauflänge und Kompression
- Lauflänge:Folgen gleicher Werte werden als Anzahl-Wert notiert: aus
rrrssssgrrwird3r4s1g2r. - Grenze:bei vielen Einzelzeichen wird die Folge länger:
abcwird zu1a1b1c. - Protokoll:Vereinbarung über Format, Reihenfolge und Fehlerfälle — Sender und Empfänger müssen es gleich umsetzen.
Herleitung:
rrrssssgrr \(\rightarrow\) 3r4s1g2r| codieren
Jede Folge gleicher Zeichen wird durch Anzahl und Wert ersetzt.
\(10\) Zeichen \(\rightarrow\) \(8\) Zeichen
| zählen
Original und komprimierte Folge gleich behandeln: je Zeichen gleich viele Bits.
\(\dfrac{8}{10}=0{,}8\)
| teilen
Komprimierte Größe durch Originalgröße.
\((1-0{,}8)\cdot 100\,\% = 20\,\%\)
Ergebnis
Die Kompression spart 20 % Speicherplatz.
Merke
Kompressionsverhältnis: Größe der komprimierten Daten : Größe der Originaldaten
2
Der Huffman-Baum
- Häufigkeiten:zuerst zählen, wie oft jedes Zeichen vorkommt.
- Zusammenfassen:immer die zwei Knoten mit den kleinsten Häufigkeiten zu einem neuen Knoten mit der Summe verbinden.
- Code ablesen:von der Wurzel zum Blatt: links 0, rechts 1.
- Präfixfrei:kein Code ist Anfang eines anderen — deshalb braucht man keine Trennzeichen.
- Bits gesamt:Summe aus Häufigkeit × Codelänge über alle Zeichen.
Baue den Huffman-Baum: Wähle nacheinander zwei Knoten aus (Klick oder Tab + Enter) — sie werden zu einem neuen Knoten verbunden. Am Ende stehen die Codes und die Bitzahl im Readout.
Halte fest: Häufige Zeichen landen nah an der Wurzel und bekommen kurze Codes, seltene Zeichen lange.
3
Allgemeine Hinweise
Reihenfolge Anzahl-Wert
In den Prüfungsaufgaben steht erst die Anzahl, dann der Wert: 4s, nicht s4.
Gleiche Häufigkeiten
Bei Gleichstand ist die Wahl frei — verschiedene Bäume sind möglich, die Gesamtbitzahl bleibt aber gleich.
Vergleichsgröße nennen
Beim Kompressionsverhältnis angeben, womit verglichen wird: 8 Bit je Zeichen oder die kleinste feste Codelänge.