Datenkomprimierung (u. -expansion)

Kriterien, nach denen Daten komprimiert werden:

- Zeit

- Speicherplatz

Im Augenblick besitzen Daten einen hohen Grad von Redundanz (=Weitschweifigkeit)

Lauflängencodierung

Einfachster Typ der Redundanz sind lange Folgen sich wiederholender Zeichen, sog. Läufe (runs).

Codierung variabler Lauflängen

Codierung von Buchstaben mit 5 Bits unter Verwendung des Indexs i des Buchstabens innerhalb des Alphabets:

Feste Länge der Zahlen ist Voraussetzung!

Kodierung mit variabler Länge:

Platzeinsparung dadurch, dass häufig verwendete Zeichen mit möglichst wenig Bits verschlüsselt werden.

Bsp.: A=>0 , B=>1 , R=>01 , C=>10 , D=>11

ABRACADABRA => 0|1|01|0|11|0|11|0|1|01|0

Bei diesem Code ist es notwendig, dass ein Begrenzer, ein zusätzliches Zeichen, den Code zwischen zwei Zeichen abtrennt.

Andere Überlegung:

Code ersetzen, bei dem kein Zeichencode mit dem Anfang eines anderen übereinstimmt => spart den Begrenzer

Bsp.: A=>11, B=>00, C=>010, D=10, R=>011

=> codierte Zeichenfolge:

1100011110101110110001111

(ohne Begrenzer möglich)

=> einfachste und zugleich wirksame Methode zur Kodierung ist der

TRIE.

oder:

=> 01101001111011100110100

Erzeugung des Huffman-Codes

1952 von D. Huffman (franz. Math.) entwickelt.

Schritte zur Erzeugung:

1)

Ermittlung der Häufigkeit des Auftretens der verwendeten Zeichen

2)

Aufbau des Kodierungs-Tries nach der Häufigkeit der Zeichen.

(während der Erzeugung des Tries betrachtet man ihn als Binärbaum mit Häufigkeiten, die in den Knoten gespeichert sind)

Es werden jeweils die beiden Knoten (Teil-Tries) mit den geringsten Häufigkeiten ausgewählt, aus denen ein neuer Knoten mit der Summe der beiden Häufigkeiten gebildet wird.

Nachfolger dieses Knotens sind die beiden Ausgangsknoten

(Teil-Tries).

3)

Der Hoffman-Code wird aus den Tries abgeleitet, indem man den Trie von der Wurzel bis zu einem Blatt (codiertes Zeichen) durchläuft und dabei nach "links" den Wert 0 und nach "rechts" den Wert 1 codiert.

Bsp.: Datei: EIN_SONNIGES_WOCHENENDE

Hoffman-Code: 01 111 10 0010 0011 0000 10 10 111 1101 01 0011 0010 11000 0000 11001 00010 01 10 01 10 00011 01

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

beim Codieren sind die Zeichen mit der größten Häufigkeit am weitesten oben

=> kürzester Code

E: 01

_: 0010

G: 1101

H: 00010

N: 10

S: 0011

W: 11000

D: 00011

I: 111

O: 0000

C: 11001