Aufgabe: Arbeitsblatt

Löse das Arbeitsblatt «Bildformate»

(unknown via CS Unplugged)

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. 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 – Grafik

psd, xcf, afphoto – Grafik (proprietär)

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 müssen, sondern nur noch konsumiert werden

Beispiele

mp3 – Sound

jpg – Grafik

mp4, avi, mov – Video

Huffman-Codierung

David Huffman hat 1952 ein Verfahren entwickelt, mit welchem Zeichen platzsparender codiert werden können. Seine Idee ist, dass Zeichen, welche Text vorkommen, einen kürzeren Code erhalten, als Zeichen, welche selten vorkommen.

Wir schauen die Huffmann-Codierung am Beispiel von Text an. Man kann sie aber auch z.B. in Bildern als Code für Farben verwenden.

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: Huffman

1. Decodiere die folgende Bitfolge mit dem obenstehenden Codebaum. (SP) steht für ein Leerzeichen (engl. space).

0111101011000110110101

2. Codiere den erhaltenen Text nun wahlweise in Pentacode oder in ASCII. Wie lange ist die erhaltene Bitfolge?
3. Findest du einen besseren Code als Pentacode/ASCII?

Lösung: Aufgabe Huffman

Huffman:

$$\stackrel{A}{\mathtt{\text{0}}}\stackrel{N}{\mathtt{\text{11}}}\stackrel{N}{\mathtt{\text{11}}}\stackrel{A}{\mathtt{\text{0}}}\stackrel{S}{\mathtt{\text{101}}}\stackrel{}{\mathtt{\text{100}}}\stackrel{A}{\mathtt{\text{0}}}\stackrel{N}{\mathtt{\text{11}}}\stackrel{A}{\mathtt{\text{0}}}\stackrel{N}{\mathtt{\text{11}}}\stackrel{A}{\mathtt{\text{0}}}\stackrel{S}{\mathtt{\text{101}}}$$

Pentacode:
12 Zeichen à 5 Bit = 60 Bits

00001 01110 01110 00001
10011 00000 00001 01110
00001 01110 00001 10011

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

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

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

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

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: Huffman-Baum

1. Erstelle zu folgendem Text einen Huffman-Baum und codiere den Text entsprechend:

   EXTERNER EFFEKT

2. 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: Sprache

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