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

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 ein Foto komprimiert werden soll.

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.

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.

0111101011000110110101

Lösung: Aufgabe Huffman

Huffman:

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.

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:

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.

Franz jagt im komplett verwahrlosten Taxi quer durch Bayern