Datenkompression


Kriterien

Übersicht Formate

Grundlagen

Kompressionsverfahren

Datenformate


Huffman-Kodierung

Beispiel

Eigenschaften

Varianten

dynamische Kodierung

adaptive Kodierung

Initialisierung

Algorithmus

Tabelle Kodebaum

Update-Prozedur

neue Zeichen

Baum aktualisieren

Dekodierung

Beispiel


Glossar

Stichwortverzeichnis


Download


www.BinaryEssence.de

Algorithmus adaptive Huffman-Kodierung


Zur Entwicklung eines Huffman-Baums mit adaptiver Kodierung sind eine Reihe von Regeln und Konventionen erforderlich, die für die Realisierung der Algorithmen essentiell sind. Ausgegangen wird von einem Verfahren, das mit einem sich entwickelnden Baum arbeitet, ohne präventive Annahmen über die Ausgangsverteilung der Zeichen zu machen.

Steuerzeichen für nicht im Baum enthaltene Zeichen
Zusätzlich zum Zeichenvorrat der Quelldaten wird ein Steuerzeichen definiert, das bisher nicht im Baum enthaltene Zeichen signalisiert. In der Literatur wird dieses Steuerzeichen als NYA oder NYT (Not Yet Available oder Transmitted) bezeichnet.

Knotengewicht
Jeder Knoten erhält als Attribut ein Knotengewicht. Das Gewicht eines Endknotens ist gleich der Häufigkeit, mit der das zugeordnete Zeichen in den bisher kodierten Daten auftrat. Das Gewicht der inneren Knoten ist gleich der Summe der beiden untergeordneten Knoten. Das Steuerzeichen NYA erhält das Gewicht 0.

Struktur der Kodetabelle
Alle Knoten werden entsprechend ihres Gewichts sortiert, beginnend mit dem Knoten mit dem niedrigsten Gewicht. Damit stellt der NYA-Knoten immer den niederwertigsten Knoten in der Hierarchie.

Sibling Property
Jedes benachbarte Knotenpaar in der Hierarchie (Knoten 2n-1 und 2n, also 1&2, 3&4, 5&6, etc.) verweist auf den gleichen übergeordneten Knoten. Da der übergeordnete Knoten ("Elternknoten") als Gewicht die Summe der beiden untergeordneten Knoten aufweist, ist er in der Hierarchie immer höher eingeordnet. Diese beiden Aussagen werden als Sibling Property bezeichnet (Sibling: Geschwister; Property: Eigenschaft).

Wurzel
Der Knoten mit dem höchsten Gewicht ist in der Hierachie am weitesten oben angesiedelt und stellt die aktuelle Wurzel des Baums dar.

Intitialer Baum
Der initiale Baum enthält nur ein den NYA-Knoten, der das Gewicht 0 trägt.

Datenformat für unkodierte Zeichen
Im einfachsten Fall werden Zeichen, die nicht im Kodebaum enthalten sind linear kodiert (z.B. 8 Bit bei einem Zeichenvorrat von 256 Zeichen). Da die Anzahl der nicht im Baum enthalten Zeichen aber kontinuierlich abnimmt, lässt sich eine bessere Kodeeffizienz erreichen, wenn das Datenformat an die Zahl der "fehlenden" Zeichen angepaßt wird. Dazu stehen mehrere Verfahren zur Verfügung.

maximale Anzahl von Knoten
Bei einem Zeichenvorrat von n Zeichen ergibt sich eine maximalen Anzahl von Knoten (Endknoten plus innere Knoten) von 2n-1. Legt man die Basiseinheit eines Bytes zugrunde, so ergibt sich ein Zeichenvorrat von 256 Zeichen und eine maximale Anzahl von 511 Knoten.

Block
Alle Knoten mit identischem Gewicht werden logisch zu einem "Block" zusammengefasst. In einer Tabelle, die den Kodebaum repräsentiert sind die Knoten, die zu einem Block gehören, stets benachbart.


 <   ^   > 

adaptive Kodierung Vor- und Nachteile der Initialisierungsmethoden Tabelle Kodebaum



Anzeigen:

Informations- und Kodierungstheorie