Wie funktioniert die adaptive Huffman-Codierung?

Die Huffman-Codierung ist eine weit verbreitete Methode der Entropiecodierung, die zur Datenkomprimierung verwendet wird. Es wird davon ausgegangen, dass wir die Statistik eines Signals vollständig kennen. Es gibt jedoch Versionen der Huffman-Codierung, die mit Streaming-Medien verwendet werden und möglicherweise nicht alles über die Statistik des Signals wissen können. Wie funktionieren diese adaptiven Huffman-Encoder ?

Der Wikipedia-Artikel enthält eine ziemlich gute Beschreibung des adaptiven Huffman-Codierungsprozesses unter Verwendung einer der bemerkenswerten Implementierungen, des Vitter-Algorithmus. Wie Sie bereits bemerkt haben, hat ein Standard-Huffman-Codierer Zugriff auf die Wahrscheinlichkeitsmassenfunktion seiner Eingabesequenz, mit der er effiziente Codierungen für die wahrscheinlichsten Symbolwerte erstellt. In dem prototypischen Beispiel einer dateibasierten Datenkomprimierung kann diese Wahrscheinlichkeitsverteilung beispielsweise durch Histogrammieren der Eingabesequenz berechnet werden, wobei die Anzahl der Vorkommen jedes Symbolwerts gezählt wird (Symbole können beispielsweise 1-Byte-Sequenzen sein). Dieses Histogramm wird verwendet, um einen Huffman-Baum wie diesen zu generieren (entnommen aus dem Wikipedia-Artikel):

Der Baum wird durch Verringern des Gewichts oder der Wahrscheinlichkeit des Auftretens in der Eingabesequenz angeordnet. Blattknoten oben stellen die wahrscheinlichsten Symbole dar, die daher die kürzesten Darstellungen im komprimierten Datenstrom erhalten. Der Baum wird dann zusammen mit den komprimierten Daten gespeichert und später vom Dekomprimierer verwendet, um die (unkomprimierte) Eingabesequenz erneut zu regenerieren. Als eine der frühen Entropiecode-Implementierungen ist die Standard-Huffman-Codierung ziemlich einfach.

Die Struktur des adaptiven Huffman-Codierers ist ziemlich ähnlich; Es verwendet eine ähnliche baumbasierte Darstellung der Statistiken der Eingabesequenz, um effiziente Codierungen für jeden Eingabesymbolwert auszuwählen. Der Hauptunterschied besteht darin, dass als Streaming-Implementierung des Algorithmus keine a priori Kenntnis der Wahrscheinlichkeitsmassenfunktion der Eingabe verfügbar ist; Die Statistiken der Sequenz müssen im laufenden Betrieb geschätzt werden. Wenn dasselbe Huffman-Codierungsschema verwendet werden soll, bedeutet dies, dass der Baum, der zum Generieren der Codierung jedes Symbols im komprimierten Stream verwendet wird, dynamisch erstellt und verwaltet werden muss, während der Eingabestream verarbeitet wird.

Der Vitter-Algorithmus ist eine Möglichkeit, dies zu erreichen. Während jedes Eingabesymbol verarbeitet wird, wird der Baum aktualisiert, wobei die Eigenschaft beibehalten wird, die Wahrscheinlichkeit des Auftretens von Symbolen zu verringern, wenn Sie sich im Baum nach unten bewegen. Der Algorithmus definiert eine Reihe von Regeln dafür, wie der Baum im Laufe der Zeit aktualisiert wird und wie die resultierenden komprimierten Daten im Ausgabestream codiert werden. Während die Eingabesequenz verbraucht wird, sollte die Struktur des Baums eine immer genauere Beschreibung der Wahrscheinlichkeitsverteilung der Eingabe darstellen. Im Gegensatz zum Standardansatz der Huffman-Codierung verfügt der Dekomprimierer nicht über einen statischen Baum, der zum Decodieren verwendet werden kann. Es muss während des Dekomprimierungsprozesses kontinuierlich dieselben Baumpflegefunktionen ausführen.

Zusammenfassend : Der adaptive Huffman-Codierer arbeitet sehr ähnlich wie der Standardalgorithmus. Anstelle einer statischen Messung der Statistik der gesamten Eingabesequenz (Huffman-Baum) wird jedoch eine dynamische, kumulative Schätzung (dh vom ersten Symbol zum aktuellen Symbol) der Wahrscheinlichkeitsverteilung der Sequenz verwendet, um jedes Symbol zu codieren (und zu decodieren) . Im Gegensatz zum Standard-Huffman-Codierungsansatz erfordert der adaptive Huffman-Algorithmus diese statistische Analyse sowohl beim Codierer als auch beim Decodierer.