Rechnernetze

Adaptive Huffmann-Kodierung

Der Nachteil der Huffmann-Kodierung ist, dass eine Statistik der Daten vorliegen muss, was beispielsweise bei sich dynamisch ändernden Daten oder dynamisch erzeugten Daten (wie Bildern oder Video) in der Regel nicht der Fall ist. Außerdem kann dieses Verfahren sehr viel Overhead erzeugen, beispielsweise wenn Zeichenkombinationen (qu) betrachtet werden, da dann die Tabellen sehr groß werden. Daher wird eine adaptive Huffmann-Kodierung verwendet, bei der sich der Codebaum während des Durchlaufs durch die Daten aufbaut und sogar verändert werden kann, was gegebenenfalls bedeutet, dass gleiche Daten verschieden kodiert werden können, weil sich zwischenzeitlich der Codebaum verändert hat.

Die Idee ist, dass bei Kodierung und Dekodierung jeweils der gleiche Codebaumgenerator verwendet wird. Bei der adaptiven Huffmann-Kodierung werden jeweils zwei Zeichen, die noch nicht vorhanden sind, zusammengefasst und ihre Zähler verändert; ist ein Zeichen bereits im Codebaum vorhanden, so wird nur sein Zähler inkrementiert. Wird der Zählerwert größer als ein bereits vorhandener Wert, so wird dieser Knoten mit dem größten Knoten mit dem Zählerwert Z vertauscht. Auf diese Weise wandert ein in einem gewissen Kontext häufiger auftretendes Zeichen immer höher im Codebaum und wird somit mit immer kürzerer Bitfolge kodiert. Dieses Konzept wird bei verschiedenen adaptiven Techniken angewendet.