Kompression | EF Informatik 2021

# 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 – Sound; zip, rar – Dateien; gif, 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 – Sound; jpg – Grafik; mp4, 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.

Huffman-Baum für «Anna»

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

1
2
3

ASCII:
12 Zeichen à 7 Bit = 84 Bits (ursprünglich)

1000001 1001110 1001110 1000001
1010011 0100000 1000001 1001110
1000001 1001110 1000001 1010011

1
2
3

12 Zeichen à 8 Bit = 96 Bits (mit 0-Bit)

01000001 01001110 01001110 01000001
01010011 00100000 01000001 01001110
01000001 01001110 01000001 01010011

1
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.

Zeichenhäufigkeit «MISSISSIPPI»
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:

Knoten mit Zeichenhäufigkeit

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:

Knoten zusammenfassen 1

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:

Knoten zusammenfassen 2

Wichtig ist, dass nach jedem Schritt die Knoten wieder neu sortiert werden.

Knoten zusammenfassen 3

Wenn der Baum fertig ist, werden alle Äste, welche nach links zeigen, mit einer «0» markiert, alle die nach rechts zeigen mit einer «1».

Kanten benennen

Nun kann eine Codierungstabelle erstellt werden, indem der Code für jedes Zeichen vom Baum abgelesen wird:

Codierungstabelle «MISSISSIPPI»
Zeichen	I	M	P	S
Code	11	100	101	0

Aufgabe

Erstelle zu folgendem Text einen Huffman-Baum und codiere den Text entsprechend:
```
EXTERNER EFFEKT
```
1
Wie 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.

Hufmann-Baum für Zeichen-Häufigkeit der deutschen Sprache

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) ↩︎

← Textcodierung