Kompression
Ein einziges Full-HD-Foto braucht unkomprimiert über 6 Megabyte (das haben wir bei den Datenmengen ausgerechnet). Ein zweistündiger Film in dieser Qualität wären viele Hundert Gigabyte. Trotzdem passt er auf einen kleinen Stick und lässt sich streamen. Wie geht das? Die Antwort heisst Kompression.
💡 Zum Einstieg gibt es eine Präsentation zum Durchklicken.
Die Grundidee
Komprimieren heisst: dieselbe Information mit weniger Bits speichern. Das funktioniert, weil in den meisten Daten Muster und Wiederholungen stecken – man sagt auch Redundanz. Ein paar Beispiele:
- In einem Bild ist der Himmel oft über Tausende Pixel hinweg fast gleich blau.
- In einem Text kommen manche Buchstaben viel häufiger vor als andere (im Deutschen z.B. «e» sehr oft, «q» fast nie).
- In einer Tonaufnahme wiederholen sich Klangmuster.
Ein Kompressions-Verfahren sucht solche Muster und beschreibt sie kürzer. Man unterscheidet grundsätzlich zwei Arten.
Verlustfrei oder verlustbehaftet?
| Verlustfrei | Verlustbehaftet | |
|---|---|---|
| Idee | Daten platzsparend, aber exakt wiederherstellbar | Unwichtige Details werden weggelassen |
| Rückgängig? | ja, Original zu 100 % zurück | nein, das Original ist weg |
| Ersparnis | moderat | oft sehr gross |
| Beispiele | ZIP, PNG, FLAC | JPEG, MP3, MP4 |
| Wofür? | Texte, Programme, Logos | Fotos, Musik, Videos |
Beide haben ihre Berechtigung: Ein Programm oder ein Vertrag darf sich beim Komprimieren kein einziges Bit verändern – hier braucht es verlustfreie Verfahren. Bei einem Urlaubsfoto stört es hingegen kaum, wenn ein paar kaum sichtbare Details verloren gehen – dafür wird die Datei viel kleiner.
Verlustfrei 1: Lauflängencodierung (RLE)
Die einfachste Idee: Wiederholt sich ein Zeichen viele Male hintereinander, speichern wir nicht jedes einzeln, sondern nur wie oft und welches. Aus AAAAA wird 5A. Das nennt man Lauflängencodierung (englisch Run-Length Encoding, RLE).
Probier es aus – achte darauf, was bei einem Text ohne Wiederholungen passiert:
Jeder «Lauf» wird als Anzahl + Zeichen gespeichert (hier je 2 Byte). Bei viel Wiederholung spart das kräftig Platz.
RLE ist ideal für Bilder mit grossen einfarbigen Flächen (z.B. ein Logo oder ein Comic). Bei einem Foto mit vielen feinen Farbverläufen bringt es dagegen fast nichts – oder macht die Datei sogar grösser.
Verlustfrei 2: Huffman-Codierung
Ein cleverer Ansatz nutzt aus, dass manche Zeichen häufiger vorkommen als andere. Statt für jedes Zeichen gleich viele Bits (bei ASCII immer 8) zu verwenden, geben wir häufigen Zeichen kurze Codes und seltenen lange. Das ist die Idee der Huffman-Codierung.
Die Idee ist nicht neu: Schon beim Morsecode ist das häufige «e» nur ein kurzer Punkt, während das seltene «q» aus vier Zeichen besteht.
Das Problem: Wo hört ein Code auf?
Sobald die Codes unterschiedlich lang sind, entsteht ein Problem. Nehmen wir an, wir vergeben A = 0, B = 1 und C = 01. Was bedeutet dann die Bitfolge 01? Ist das ein C – oder ein A gefolgt von einem B? Das lässt sich nicht mehr entscheiden.
Die Lösung heisst Präfix-Eigenschaft: Kein Code darf der Anfang eines anderen Codes sein. Dann ist beim Lesen immer eindeutig, wo ein Zeichen endet. Genau das garantiert der Huffman-Baum: Weil alle Zeichen als Blätter ganz aussen hängen, führt kein Weg zu einem Zeichen an einem anderen Zeichen vorbei.
So baust du den Baum – die Anleitung
Du brauchst nur Papier und diese fünf Schritte:
- Zählen. Notiere für jedes Zeichen, wie oft es im Text vorkommt. Schreibe alle Zeichen mit ihrer Häufigkeit nebeneinander – das ist dein «Vorrat».
- Die zwei kleinsten nehmen. Suche im Vorrat die zwei Knoten mit den kleinsten Zahlen und nimm sie heraus.
- Zusammenfügen. Hänge die beiden unter einen neuen Knoten. Dieser bekommt als Zahl die Summe der beiden.
- Zurücklegen und wiederholen. Der neue Knoten kommt zurück in den Vorrat und zählt ab jetzt wie ein normaler Knoten. Weiter bei Schritt 2 – so lange, bis nur noch ein Knoten übrig ist. Das ist die Wurzel.
- Beschriften und ablesen. Schreibe an jede Kante nach links eine
0und nach rechts eine1. Der Code eines Zeichens ist der Weg von der Wurzel bis zu seinem Blatt.
💡 Bei Gleichstand (zwei Knoten haben dieselbe Zahl) darfst du frei wählen. Dann entstehen unterschiedliche Bäume mit unterschiedlichen Codes – die Gesamtzahl der Bits bleibt aber gleich. Beide Lösungen sind also richtig.
Beispiel von Hand: «KAKAO»
Schritt 1 – zählen: K = 2×, A = 2×, O = 1×.
Schritte 2–4 – zusammenfügen:
| Runde | Vorrat (von klein nach gross) | Die zwei kleinsten | Neuer Knoten |
|---|---|---|---|
| 1 | O:1, K:2, A:2 | O (1) und K (2) | (O+K) = 3 |
| 2 | A:2, (OK):3 | A (2) und (OK) (3) | (A+OK) = 5 ← Wurzel |
Schritt 5 – beschriften und ablesen: Von der Wurzel führt links (0) direkt das Blatt A, rechts (1) geht es weiter zum Knoten (OK); dort liegt links (0) das O und rechts (1) das K.
| Zeichen | Häufigkeit | Weg | Code | Bits total |
|---|---|---|---|---|
A | 2× | links | 0 | 2 × 1 = 2 |
O | 1× | rechts, links | 10 | 1 × 2 = 2 |
K | 2× | rechts, rechts | 11 | 2 × 2 = 4 |
| 8 Bit |
«KAKAO» wird also zu 11 0 11 0 10 – also 8 Bit statt der 40 Bit, die fünf ASCII-Zeichen bräuchten. Und A, das häufigste Zeichen, ist mit einem einzigen Bit am kürzesten.
Schritt für Schritt nachvollziehen
Hier kannst du genau diese Anleitung durchklicken. Die zwei markierten Knoten sind die, die als Nächstes verschmolzen werden:
Wir starten mit den Häufigkeiten – jedes Zeichen ist ein eigener Knoten, sortiert von klein nach gross. Die zwei kleinsten sind jetzt O mit 1 und K mit 2 (hervorgehoben). Klicke «Nächster Schritt», um sie unter einem neuen Knoten mit 3 zu verbinden.
Und wie liest man das wieder?
Zum Decodieren startest du bei der Wurzel und läufst Bit für Bit durch den Baum: 0 = nach links, 1 = nach rechts. Sobald du bei einem Blatt ankommst, hast du ein Zeichen – du notierst es und springst zurück zur Wurzel.
Mit den Codes von oben (A = 0, O = 10, K = 11) liest du 11011010 so: 1→rechts, 1→rechts = K; zurück zur Wurzel, 0 = A; 1,1 = K; 0 = A; 1,0 = O. Zusammen ergibt das wieder «KAKAO». Dank der Präfix-Eigenschaft gibt es dabei nie eine Verwechslung.
Selbst ausprobieren
Gib einen eigenen Text ein und schau, welche Codes und welche Ersparnis herauskommen:
| Zeichen | Häufigkeit | Huffman-Code | Länge |
|---|---|---|---|
| I | 4 | 11 | 2 Bit |
| S | 4 | 0 | 1 Bit |
| P | 2 | 101 | 3 Bit |
| M | 1 | 100 | 3 Bit |
Häufige Zeichen bekommen kurze Codes, seltene lange. So braucht «MISSISSIPPI» statt 88 Bit nur 21 Bit – rund 76 % weniger. (Der Baum selbst muss mitgespeichert werden; bei kurzen Texten fällt das noch ins Gewicht.)
Bei «MISSISSIPPI» reichen dank Huffman 21 Bit statt der 88 Bit, die eine feste 8-Bit-Codierung bräuchte – weil «I» und «S» sehr häufig sind und deshalb kurze Codes bekommen. Genau dieses Prinzip steckt (in ausgefeilterer Form) in ZIP, PNG und vielen anderen Formaten.
⚠️ Ein Haken bleibt: Die Codetabelle (bzw. der Baum) muss mitgespeichert werden, sonst kann niemand die Datei wieder lesen. Bei sehr kurzen Texten frisst das die Ersparnis teilweise wieder auf.
Verlustbehaftet: Weglassen, was kaum auffällt
Bei Fotos, Musik und Videos geht man einen radikaleren Weg: Man wirft Informationen weg, die ein Mensch kaum wahrnimmt. Weil das Original danach nicht mehr exakt rekonstruierbar ist, spricht man von verlustbehafteter Kompression – dafür wird die Datei oft um ein Vielfaches kleiner.
Bilder: JPEG
Das JPEG-Format lässt feine Details weg, die unser Auge kaum bemerkt. Über die Qualität stellt man den Kompromiss zwischen Dateigrösse und Bildqualität ein. Zieh am Regler und beobachte, wie bei niedriger Qualität Artefakte (Blöcke, Unschärfe) sichtbar werden – und wie stark die Datei schrumpft:
JPEG lässt Details weg, die kaum auffallen – das spart viel Speicher. Bei niedriger Qualität werden aber Blöcke und Artefakte sichtbar, besonders an scharfen Kanten und Schrift.
Ton: MP3
Auch MP3 arbeitet verlustbehaftet. Es nutzt Eigenschaften des menschlichen Gehörs aus: Sehr hohe oder sehr leise Töne, die neben lauteren kaum hörbar sind, werden einfach weggelassen. So wird aus einer unkomprimierten Aufnahme (WAV, ~30–40 MB pro Lied) eine MP3-Datei von nur 3–4 MB – rund zehnmal kleiner, ohne dass die meisten Menschen einen Unterschied hören.
Welches Verfahren gewinnt?
Es gibt kein bestes Verfahren – es kommt auf die Daten an. Vergleiche selbst, wie unkomprimiert, RLE und Huffman bei verschiedenen Texten abschneiden:
Zusammenfassung
- Kompression speichert dieselbe Information mit weniger Bits, indem sie Muster und Redundanz ausnutzt.
- Verlustfreie Verfahren (RLE, Huffman, ZIP, PNG) stellen das Original exakt wieder her. Verlustbehaftete (JPEG, MP3, MP4) lassen kaum wahrnehmbare Details weg und sparen dafür viel mehr Platz.
- RLE fasst Wiederholungen zusammen, Huffman gibt häufigen Zeichen kurze Codes.
- Welches Verfahren am besten passt, hängt immer von den Daten und vom Zweck ab.
Teste dich selbst
Selbsttest: Kompression
Frage 1 von 5
Aufgaben
Löse die Aufgaben und überprüfe erst danach deine Lösung im Dropdown.
Aufgabe 1: Wie lautet die Lauflängencodierung (RLE) von AAAABBBCCCCCCCC?
Lösung anzeigen
4A3B8C. Das Original hat 15 Zeichen (15 Byte), die RLE-Form braucht 3 Läufe × 2 Byte = 6 Byte.
Aufgabe 2: Warum wird der Text ABCDEF durch RLE grösser statt kleiner?
Lösung anzeigen
Es gibt keine Wiederholungen – jeder «Lauf» ist nur ein Zeichen lang. RLE speichert also 6 Läufe × 2 Byte = 12 Byte statt der ursprünglichen 6 Byte. RLE lohnt sich nur bei Wiederholungen.
Aufgabe 3: Im Text AAAAB – welches Zeichen sollte bei Huffman den kürzeren Code bekommen, A oder B?
Lösung anzeigen
A, weil es häufiger vorkommt (4×) als B (1×). Häufige Zeichen bekommen kurze Codes – das spart insgesamt am meisten Bits.
Aufgabe 4: Nenne je ein verlustfreies und ein verlustbehaftetes Format – einmal für Bilder, einmal für Ton.
Lösung anzeigen
Bilder: PNG (verlustfrei) und JPEG (verlustbehaftet). Ton: FLAC (verlustfrei) und MP3 (verlustbehaftet).
Aufgabe 5: Ein 100 × 100 Pixel grosses Schwarz/Weiss-Bild zeigt eine grosse weisse Fläche mit einem kleinen schwarzen Punkt. Warum ist RLE hier ideal?
Lösung anzeigen
Fast alle Pixel sind gleich (weiss), es gibt also sehr lange Läufe derselben Farbe. RLE muss dann nur ganz wenige Läufe speichern (z.B. «viele weisse, ein paar schwarze, wieder viele weisse») – das spart enorm viel Platz.
Aufgabe 6: Baue den Huffman-Baum für den Satz OMA MAG MAMA (das Leerzeichen zählt als eigenes Zeichen mit!). Gehe nach der Anleitung vor: zählen → zwei kleinste zusammenfügen → wiederholen → beschriften. Notiere danach die Codetabelle und rechne aus, wie viele Bits der Satz braucht.
Lösung anzeigen
Schritt 1 – zählen (12 Zeichen, davon 2 Leerzeichen ␣):
M = 4×, A = 4×, ␣ = 2×, O = 1×, G = 1×
Schritte 2–4 – zusammenfügen:
| Runde | Vorrat (von klein nach gross) | Die zwei kleinsten | Neuer Knoten |
|---|---|---|---|
| 1 | O:1, G:1, ␣:2, M:4, A:4 | O (1) und G (1) | (O+G) = 2 |
| 2 | ␣:2, (OG):2, M:4, A:4 | ␣ (2) und (OG) (2) | (␣+OG) = 4 |
| 3 | (␣OG):4, M:4, A:4 | M (4) und A (4) | (M+A) = 8 |
| 4 | (␣OG):4, (MA):8 | (␣OG) (4) und (MA) (8) | 12 ← Wurzel |
Schritt 5 – Codes ablesen:
| Zeichen | Häufigkeit | Code | Bits total |
|---|---|---|---|
M | 4× | 10 | 4 × 2 = 8 |
A | 4× | 11 | 4 × 2 = 8 |
␣ | 2× | 00 | 2 × 2 = 4 |
O | 1× | 010 | 1 × 3 = 3 |
G | 1× | 011 | 1 × 3 = 3 |
| 26 Bit |
Der Satz braucht also 26 Bit statt 12 × 8 = 96 Bit – rund 73 % weniger.
Hast du in Runde 3 eine andere Zwei gewählt (dort sind drei Knoten mit der Zahl 4 im Vorrat)? Dann sehen deine Codes anders aus – die Summe ist trotzdem 26 Bit. Prüfen kannst du alles im Applet oben, indem du OMA MAG MAMA eingibst.
Aufgabe 7: Decodiere mit der Codetabelle aus Aufgabe 6 (M = 10, A = 11, ␣ = 00, O = 010, G = 011) die Bitfolge 10110110010111011.
Lösung anzeigen
Von links nach rechts: 10 = M, 11 = A, 011 = G, 00 = ␣, 10 = M, 11 = A, 10 = M, 11 = A → MAG MAMA.
Weil kein Code der Anfang eines anderen ist (Präfix-Eigenschaft), gibt es an keiner Stelle eine zweite Möglichkeit – du brauchst keine Trennzeichen zwischen den Codes.
Aufgabe 8: Der Satz aus Aufgabe 6 besteht aus nur 5 verschiedenen Zeichen. Mit 3 Bit lassen sich 8 Zeichen unterscheiden – man käme also auch mit einem festen 3-Bit-Code aus. Wie viele Bits wären das? Und lohnt sich Huffman dann überhaupt noch?
Lösung anzeigen
Fester 3-Bit-Code: 12 Zeichen × 3 Bit = 36 Bit. Huffman braucht 26 Bit, also immer noch rund 28 % weniger.
Der Gewinn ist kleiner als der Vergleich mit 8 Bit vermuten liess – aber er bleibt, weil M und A zusammen zwei Drittel des Textes ausmachen und nur je 2 Bit brauchen. Huffman lohnt sich immer dann, wenn die Häufigkeiten ungleich verteilt sind. Kämen alle Zeichen gleich oft vor, wäre ein fester Code genauso gut.