Herzlich Willkommen bei XALAX.DE

Komprimierungsverfahren

Huffman Verfahren

Allgemeines: bekannteste und weit verbreiteste Verfahren; einfach und klar und Qualität leicht zu beweisen; Huffman hat es bereits 1951 beschrieben

Die Ausführliche theoretische Ausarbeitung findesn sie hier!

Überlegung: gespeicherte Zeichen verbrauchen 8 bit; für häufig vorkommende weniger Speicher und für seltenere mehr Speicher

  1. Verfahren: Statisch: Häufigkeit unabhängig von den Daten einmal berechnet; Vorteil: schnellere Verarbeitung; Nachteil: keine präzise Vorhersage möglich (ASCII,binär); Anwendung: Nachbereitung; Fax-Geräten
  2. Dynamisch: Häufigkeit jedes mal neu berechnet; Vorteil: bessere Komprimierung; Nachteil: Code muss immer mit übertragen werden; Anwendung: innerhalb von PKZIP
  3. Adaptiv: Verbindung beider Verfahren; verändern des Codierungsschema im Verlauf der Kompression;

Zu komprimierender Text hat N Zeichen
Zeichen: z1,...,zn
Informationsgehalt: -å i = 1, ..., n log(pi)
Wahrscheinliche Codelänge pro Zeichen: å i = 1, ..., n pi * (Bit-Code-Länge von zi)
Häufigkeit (pi): pi = (Anzahl von zi) / N
Häufigkeiten sortieren (beginnend mit größter)


Beispiel:

Wort "abrakadabra"

Zu komprimierender Text hat 11 Zeichen
Davon 5 verschieden Zeichen: z1,...,z5

Häufigkeit (pi) à pi = (Anzahl von zi) / 11

Häufigkeiten bestimmen:
05 x a = 05/11 = 0,45
02 x b = 02/11 = 0,18
02 x r = 02/11 = 0,18
01 x d = 01/11 = 0,09
01 x k = 01/11 = 0,09
---------------------
11 x zi = 11/11 = 1,00

Häufigkeiten sortieren (beginnend mit größter)


1.Variante:
Die kleinsten Häufigkeiten addieren und zu einem Knoten zusammen fassen.

Danach wird neu sortiert (in diesem Fall nicht nötig) und wieder die beiden kleinsten Häufigkeiten verknüpft

neu sortiert und verknüpft bis kein Knoten mehr übrig ist


Man erhält also nun die folgenden eindeutigen Kodeworte:

a -> 1
b -> 01
r -> 000
d -> 0010
k -> 0011

Der Ausgangstext `abrakadabra' wird somit als 10100010011100101010001 kodiert
Kodierter Text = 23 Bit
Ausgangs Text = 88 Bit (bei 1 Byte / Zeichen)
Komprimierung von 26,136%
Wahrscheinliche Codelänge pro Zeichen: 11,11
Informationsgehalt: 3,9


Jedes Zeichen wird zu einem Knoten eines Binärbaumes
Knoten mit der geringsten Häufigkeit werden verbunden


das wiederholt sich bis weniger als zwei Knoten übrig sind

danach die neuen knoten mit den letzten beginnend verbinden

zum Schluss müssen die Knoten noch mit 0 und 1 markiert werden
nach links laufende mit 0, nach rechts laufende mit 1


Man erhält also nun die folgenden eindeutigen Kodeworte:

a -> 0
b -> 100
r -> 101
d -> 110
k -> 111

Der Ausgangstext `abrakadabra' wird somit als 01001010111011001001010 kodiert

Kodierter Text = 23 Bit
Ausgangs Text = 88 Bit (bei 1 Byte / Zeichen

Letzte Änderung: 03.01.2008