# Kompression
Bei der Kompression wird versucht, Daten effizienter abzuspeichern, so dass weniger Speicherplatz belegt wird. Gerade beim Übertragen von Daten – z.B. Streamen eines Films, oder Telefonie – ist dies enorm wichtig. Wir unterscheiden zwei grundsätzlich unterschiedliche Arten von Kompression:
# Verlustfreie Kompression
Bei der verlustfreien Kompression, können die Daten vollständig rekonstruiert werden. D.h. es handelt sich – wie bei der Codierung – um eine eindeutige und umkehrbare Abbildung.
- Anwendung
- Überall dort, wo kein Verlust passieren darf – ein Programm läuft nicht mehr, wenn Befehle fehlen!
- Bilder, Audio und Video während der Produktion und Bearbeitung – sonst würde bei jedem Speichern (also Codieren) die Qualität abnehmen.
- Beispiele
flac– Soundzip,rar– Dateiengif,png,raw,psd,xcf– Grafik
# Verlustbehaftete Kompression
Hier werden beim Speichern Daten entfernt. Dadurch kann entsprechend viel Speicher gewonnen werden, allerdings lassen sich die Original-Daten nur noch teilweise rekonstruieren. Es wird versucht vor allem nicht wichtige Daten wegzulassen.
- Anwendung
- beim Fertigstellen von Medien, also wenn diese nicht mehr weiter bearbeitet werden sollen sondern nur noch dem Konsumenten zur Verfügung gestellt werden.
- Beispiele
mp3– Soundjpg– Grafikmp4, avi, mov– Video
# Grafik
Die verschiedenen Dateiformate bieten dank ihrer unterschiedlichen Kompression alle Vor- und Nachteile. Zudem spielt es eine Rolle ob Text, ein Logo, eine Illustration oder eine Foto komprimiert werden soll.
Aufgabe
Ein einfaches verlustfreies Kompressions-Verfahren für Grafiken, ist das Run Length Encoding, kurz RLE.
Teste das Verfahren mit verschiedenen einfache Grafiken online:
https://www.csfieldguide.org.nz/en/interactives/run-length-encoding/ (opens new window)
Beantworte dabei folgende Fragen:
- Wo ist das Verfahren sehr effizient?
- Für welche Art von Grafiken könnte es eingesetzt werden?
# Huffman-Codierung
David Huffman hat 1952 ein Verfahren entwickelt, mit welchem Zeichen platzsparender codiert werden können. Seine Idee ist, dass Zeichen, welche häufig im Text vorkommen, einen kürzeren Code erhalten, als Zeichen, welche selten im Text vorkommen.
Quelle: Stefan Rothe (opens new window)
# Codebaum
Ein Codebaum ist eine Struktur mit einem Startknoten. Von diesem aus geht es entweder nach links oder rechts unten weiter. Eine 0 im Code bedeutet nach links gehen, eine 1 nach rechts gehen. Wenn ein Knoten mit einem Buchstaben erreicht wird, hat man ein Zeichen decodiert, man beginnt wieder von vorne.
Aufgabe
- Decodiere die folgende Bitfolge mit dem obenstehenden Codebaum. (SP) steht für ein Leerzeichen (engl. space).
0111101011000110110101
- Codiere den erhaltenen Text nun wahlweise in ASCII. Wie lange ist die erhaltene Bitfolge?
- Findest du einen besseren Code als ASCII?
Lösung
Huffmann:
Pentacode:
12 Zeichen à 5 Bit = 60 Bits
00001 01110 01110 00001
10011 00000 00001 01110
00001 01110 00001 10011
2
3
ASCII:
12 Zeichen à 7 Bit = 84 Bits (ursprünglich)
1000001 1001110 1001110 1000001
1010011 0100000 1000001 1001110
1000001 1001110 1000001 1010011
2
3
12 Zeichen à 8 Bit = 96 Bits (mit 0-Bit)
01000001 01001110 01001110 01000001
01010011 00100000 01000001 01001110
01000001 01001110 01000001 01010011
2
3
eigener Code:
Es müssen ja nur 4 Zeichen codiert werden können. Dafür reichen 2 Bits!
| Code | Zeichen |
|---|---|
| 00 | (SP) |
| 01 | A |
| 10 | N |
| 11 | S |
12 Zeichen à 2 Bit = 24 Bits
# Erstellen eines Huffman-Baumes
Am Beispiel der Codierung des Textes «MISSISSIPPI» soll der Huffman-Algorithmus erläutert werden.
Zuerst zählt man, wie oft jedes Zeichen im Text vorkommt und erstellt eine Häufigkeitstabelle.
| Zeichen | M | P | I | S |
|---|---|---|---|---|
| Häufigkeit | 1 | 2 | 4 | 4 |
Nun geht es darum, einen Codierungsbaum zu erstellen. Die Häufigkeiten der Buchstaben bilden je einen Knoten. Die Häufigkeit steht im Knoten, der Buchstaben darunter. Die Knoten werden nach aufsteigender Häufigkeit sortiert:
Nun werden die zwei Knoten mit den kleinsten Häufigkeiten an einen neuen Knoten angehängt. Der neue Knoten enthält die summierte Häufigkeit der ursprünglichen Knoten:
Das wird wiederholt, bis alle Knoten miteinander verbunden sind. Wenn zwei Knoten die gleiche Häufigkeit haben, spielt es keine Rolle, welcher gewählt wird:
Wichtig ist, dass nach jedem Schritt die Knoten wieder neu sortiert werden.
Wenn der Baum fertig ist, werden alle Äste, welche nach links zeigen, mit einer «0» markiert, alle die nach rechts zeigen mit einer «1».
Nun kann eine Codierungstabelle erstellt werden, indem der Code für jedes Zeichen vom Baum abgelesen wird:
| Zeichen | I | M | P | S |
|---|---|---|---|---|
| Code | 11 | 100 | 101 | 0 |
Aufgabe
Erstelle zu folgendem Text einen Huffman-Baum und codiere den Text entsprechend:
EXTERNER EFFEKT1Wie viel Bit beansprucht das Wort in Huffman-Codierung? Wie viel in Pentacode? Wie viel in ASCII?
# Huffman-Baum für Deutsch
Grundsätzlich wird für jeden zu codierenden Text ein Huffman-Baum erstellt. So wird auf die Eigenschaften des Textes eingegangen und sichergestellt, dass häufig vorkommende Zeichen einen kurzen Code zugewiesen erhalten. Der Baum muss aber mit den codierten Daten zusammen abgespeichert werden – er wird ja für die Decodierung verwendet.
Wenn man die Häufigkeit der Buchstaben in der deutschen Sprache anschaut, so können wir auf Grund dieser Daten, einen Huffman-Baum erstellen welcher sich für längere deutsche Texte eignen würde.
Zusatzaufgabe
Kannst du die folgenden Fragen beantworten:
- Wieso spielt die Sprache eine Rolle?
- Wieso gewinnt man beim folgenden Satz keinen Speicherplatz mit Huffman?
Franz jagt im komplett verwahrlosten Taxi quer durch Bayern
https://classic.csunplugged.org/text-compression/ (opens new window) ↩︎
Phrood via Wikipedia: Kompressionsverfahren im Vergleich, https://de.wikipedia.org/wiki/Bildkompression (opens new window) (abgerufen am 24.10.2019) ↩︎