Datenkompression


Kriterien

Übersicht Formate

Grundlagen

Kompressionsverfahren

Datenformate


Huffman-Kodierung

Beispiel

Eigenschaften

Varianten

dynamische Kodierung

Aufbau des Kodebaums

1. Schritt

2. Schritt

3. Schritt

4. Schritt

Kodierungstabelle

Enkodierung

Dekodierung

alternative Sortierung

Varianz

adaptive Kodierung


Glossar

Stichwortverzeichnis


Download


www.BinaryEssence.de

Aufbau des Kodebaums


Mit den nachfolgend aufgelisteten Regeln kann ein Huffman-Baum erstellt werden, der, bei gegebener Häufigkeit der einzelnen Zeichen, einen möglichst effizienten Kode erzeugt:

  • suche die beiden Einträge, die die geringste Häufigkeit aufweisen und noch nicht verknüpft sind
  • fasse diese Einträge zu einem neuen Knoten zusammen
  • addiere die beiden Häufigkeiten und weise diesen Wert dem neuen Knoten zu

Diese Aktionen werden solange wiederholt, bis alle Einträge in einem Wurzelknoten zusammengefaßt sind.


Quelldaten:  "abrakadabra"

   Zeichen   Häufigkeit
        a      5
        b      2
        r      2
        k      1
        d      1

Entsprechend der oben skizzierten Kodierungsvorschrift werden im ersten Schritt die beiden Zeichen "d" und "k" zusammengefasst und bilden einen neuen Knoten mit der Häufigkeit 2.


 <   ^   > 

dynamische Kodierung dynamische Kodierung 1. Schritt



Anzeigen:

Informations- und Kodierungstheorie