Mit Google fortfahren
Datenkompression: RLE, Huffman und LZW erklärt
Datenkompression stellt digitale Daten mit weniger Bits dar. Verlustfreie Verfahren stellen das Original exakt wieder her; verlustbehaftete Verfahren entfernen dauerhaft Informationen und tauschen dadurch Qualität gegen eine kleinere Datenmenge.
Auf dieser Seite untersuchst du Datenmuster und entscheidest, wann Lauflängencodierung, Huffman-Codierung oder LZW sinnvoll ist.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Warum lassen sich Daten verkleinern?
Viele Dateien enthalten Redundanz: Zeichen, Pixel oder längere Folgen wiederholen sich oder treten mit sehr unterschiedlichen Häufigkeiten auf. Ein Kompressionsverfahren beschreibt solche Regelmäßigkeiten kürzer.
Bei AAAAAABBBCCCCDDDD kann beispielsweise eine Anzahl zusammen mit dem zugehörigen Zeichen gespeichert werden:
6A3B4C4D
Der Decoder liest 6A als sechs aufeinanderfolgende A. Die Bedeutung der Daten bleibt erhalten, obwohl die Darstellung kürzer ist.
Codec
Ein Codec besteht aus einem Kompressor und einem Dekompressor. Der Kompressor erzeugt aus den Ausgangsdaten eine codierte Darstellung. Der Dekompressor rekonstruiert daraus die Daten.
Nicht jede Eingabe besitzt nutzbare Regelmäßigkeiten. Außerdem benötigen Dateiformate oft Zusatzinformationen, etwa Zähler, Wörterbücher oder Codebäume.
Verlustfrei oder verlustbehaftet?
Verlustfreie Kompression
Nach dem Dekomprimieren stimmen alle Daten exakt mit dem Original überein. Das ist für Texte, Programme und andere Daten nötig, bei denen bereits ein verändertes Bit wichtig sein kann.
RLE, Huffman und LZW arbeiten verlustfrei. Auch ZIP und PNG verwenden verlustfreie Verfahren.
Verlustbehaftete Kompression
Bei der Kompression werden Informationen dauerhaft entfernt. Die rekonstruierte Datei ähnelt dem Original, ist aber nicht damit identisch.
JPEG für Fotos sowie viele Audio- und Videoformate nutzen verlustbehaftete Verfahren. Sie können weniger auffällige Bild- oder Toninformationen schwächer darstellen oder entfernen. Eine stärkere Reduktion kann jedoch sichtbare oder hörbare Qualitätsverluste verursachen.
Die passende Art hängt vom Zweck ab:
| Situation | Sinnvolle Art | Begründung |
|---|---|---|
| Programmdatei | verlustfrei | Jeder Bestandteil muss exakt erhalten bleiben. |
| Textdokument | verlustfrei | Veränderte Zeichen verändern den Inhalt. |
| Foto für eine Webseite | oft verlustbehaftet | Eine geringe Abweichung kann zugunsten einer kleineren Datei akzeptabel sein. |
| medizinisches oder dauerhaft zu bewahrendes Original | verlustfrei | Ein Informationsverlust kann problematisch sein. |
Verlustfrei beschreibt die exakte Rekonstruktion, nicht eine besonders starke Verkleinerung. Verlustbehaftet bedeutet, dass entfernte Informationen nicht zurückgewonnen werden können.
RLE fasst gleiche Zeichen zusammen
Die Lauflängencodierung, kurz RLE, ersetzt einen Lauf gleicher Elemente durch seine Länge und das Element.
Ein einfacher Ablauf lautet:
- Beginne beim ersten Element.
- Zähle, wie oft es ohne Unterbrechung vorkommt.
- Gib Anzahl und Element aus.
- Fahre beim nächsten anderen Element fort.
Für HAAAALLOOO!!!! entstehen die Läufe H, AAAA, LL, OOO und !!!!.
Mit der vereinbarten Schreibweise „Anzahl vor Zeichen“ lautet das Ergebnis:
1H4A2L3O4!
Zum Decodieren wird jedes Zeichen so oft wiederholt, wie die vorangestellte Zahl angibt. Dadurch entsteht wieder exakt HAAAALLOOO!!!!.
RLE eignet sich für lange, zusammenhängende Wiederholungen, beispielsweise in einfachen Bildern mit großen gleichfarbigen Flächen. Bei häufig wechselnden Daten kann die Darstellung länger werden:
ABCD wird mit derselben Schreibweise zu 1A1B1C1D.
Das Beispiel verwendet einstellige Lauflängen. Ein echtes Dateiformat muss zusätzlich eindeutig festlegen, wie Zahlen und Zeichen gespeichert und voneinander getrennt werden. Erst mit einer solchen Festlegung lässt sich die Bitersparnis exakt bestimmen.
Huffman gibt häufigen Symbolen kurze Codes
Die Huffman-Codierung nutzt unterschiedliche Symbolhäufigkeiten. Häufige Symbole erhalten meist kurze, seltene Symbole längere Bitfolgen.
Damit aneinandergereihte Codewörter eindeutig decodierbar sind, verwendet Huffman einen Präfixcode.
Präfixcode
Bei einem Präfixcode ist kein vollständiges Codewort der Anfang eines anderen Codeworts. Deshalb erkennt der Decoder das Ende jedes Codeworts ohne zusätzliches Trennzeichen.
Ein Huffman-Baum entsteht schrittweise:
- Notiere jedes Symbol mit seiner Häufigkeit.
- Verbinde die beiden leichtesten Knoten.
- Wiederhole das Verbinden, bis nur noch ein Baum übrig ist.
- Beschrifte die beiden Äste jeder Verzweigung mit
0und1. - Lies für jedes Symbol den Weg von der Wurzel bis zum Blatt ab.
Die zehn Zeichen AAAAAABBBC enthalten sechs A, drei B und ein C.
Zuerst werden die beiden seltensten Symbole C und B verbunden. Ihr gemeinsames Gewicht ist vier. Danach wird dieser Knoten mit A verbunden. Eine mögliche Beschriftung ergibt:
| Symbol | Häufigkeit | Code | Benötigte Bits |
|---|---|---|---|
| A | 6 | 1 | 6 × 1 = 6 |
| B | 3 | 01 | 3 × 2 = 6 |
| C | 1 | 00 | 1 × 2 = 2 |
Insgesamt werden für die codierten Zeichen 14 Bits benötigt. Ein gleich langer Code für drei Symbole müsste zwei Bits pro Zeichen verwenden und benötigte für zehn Zeichen 20 Bits.
Der Code ist präfixfrei: 1, 01 und 00 sind jeweils vollständige Codewörter, aber keines beginnt mit einem anderen vollständigen Codewort.
In einer vollständigen Datei muss der Decoder außerdem den Codebaum oder eine gleichwertige Beschreibung kennen. Dieser Zusatzaufwand kann den Vorteil bei kurzen Eingaben aufheben.
LZW baut während des Codierens ein Wörterbuch auf
LZW ersetzt wiederkehrende Zeichenfolgen durch Wörterbuchnummern. Encoder und Decoder starten mit demselben Grundwörterbuch und ergänzen es nach festen Regeln. Das Wörterbuch muss deshalb nicht als vollständige Liste übertragen werden.
Für das Beispiel enthält das Grundwörterbuch:
| Index | Eintrag |
|---|---|
| 1 | A |
| 2 | B |
Der Encoder hält das längste bereits bekannte Wort w fest und betrachtet das nächste Zeichen Z:
- Ist
wZschon im Wörterbuch, wirdwZzum neuen Suchwort. - Ist
wZunbekannt, gibt der Encoder den Index vonwaus, trägtwZneu ein und setztwaufZ. - Am Ende gibt er den Index des verbleibenden Wortes aus.
Für ABABABA läuft die Codierung so ab:
| Schritt | Bekanntes Wort w | Nächstes Zeichen | Aktion |
|---|---|---|---|
| 1 | A | B | Ausgabe 1, ergänze AB als Index 3 |
| 2 | B | A | Ausgabe 2, ergänze BA als Index 4 |
| 3 | A | B | AB ist bekannt; lies weiter |
| 4 | AB | A | Ausgabe 3, ergänze ABA als Index 5 |
| 5 | A | B | AB ist bekannt; lies weiter |
| 6 | AB | A | ABA ist bekannt; Eingabe endet |
| Ende | ABA | – | Ausgabe 5 |
Die Ausgabe ist somit 1, 2, 3, 5.
Der Decoder rekonstruiert die Folge schrittweise:
- Index
1ergibtA. - Index
2ergibtB; aus dem vorherigen WortAund dem ersten Zeichen vonBentsteht der neue EintragABmit Index 3. - Index
3ergibtAB; aus dem vorherigen WortBund dem ersten Zeichen vonABentstehtBAmit Index 4. - Index
5ist zu diesem Zeitpunkt noch nicht eingetragen. In diesem besonderen LZW-Fall ergänzt der Decoder das vorherige WortABum dessen erstes ZeichenA. So erhält erABAund trägt es als Index 5 ein.
Die zusammengesetzten Ausgaben A, B, AB und ABA ergeben wieder exakt ABABABA.
Ob die Ausgabe tatsächlich weniger Bits benötigt, hängt unter anderem von der Eingabelänge, den Wiederholungen und der Bitbreite der Indizes ab. Das Zahlenbeispiel zeigt daher vor allem die Wörterbuchbildung.
So wählst du ein Verfahren aus
Untersuche vor der Auswahl, welche Regelmäßigkeit die Daten besitzen:
| Beobachtung | Passendes Grundverfahren | Genutzte Struktur |
|---|---|---|
| Lange Folgen gleicher Elemente | RLE | Lauflängen |
| Stark unterschiedliche Symbolhäufigkeiten | Huffman | kurze Codes für häufige Symbole |
| Wiederkehrende längere Zeichenfolgen | LZW | dynamisches Wörterbuch |
| Kleine Qualitätsabweichungen sind erlaubt | verlustbehaftetes Verfahren | weniger wichtige Informationen können entfallen |
Kompression garantiert keine Verkürzung. Dafür gibt es zwei wichtige Gründe:
- Manche Daten enthalten kaum nutzbare Muster.
- Zähler, Wörterbuchindizes, Codebäume und weitere Zusatzdaten benötigen selbst Platz.
Auch ein grundsätzlich geeignetes Verfahren kann bei einer zu kurzen Eingabe ungünstig sein. Vergleiche deshalb nicht nur die sichtbaren Symbole, sondern die gesamte codierte Darstellung einschließlich nötiger Zusatzinformationen.
Kompression und Verschlüsselung lösen verschiedene Aufgaben. Kompression verkleinert eine Darstellung; Verschlüsselung schützt deren Inhalt vor unbefugtem Lesen. Komprimierte Daten sind nicht allein deshalb sicher.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Datenkompression
- exakte Rekonstruktion: verlustfreie Verfahren
- Qualitätsverlust möglich: verlustbehaftete Verfahren
- gleiche Läufe: RLE
- ungleiche Häufigkeiten: Huffman
- wiederkehrende Folgen: LZW
- Grenze: Muster und Zusatzaufwand entscheiden über die Wirkung
Abschluss-Check
Du kannst ein Verfahren nun anhand der Datenstruktur auswählen: RLE nutzt Läufe, Huffman unterschiedliche Häufigkeiten und LZW wiederkehrende Folgen. Prüfe anschließend immer, ob die Rekonstruktion zum Zweck passt und ob der gesamte Code einschließlich Zusatzinformationen tatsächlich kleiner ist.