Jak działa adaptacyjne kodowanie Huffmana?

Kodowanie Huffmana jest szeroko stosowaną metodą kodowania entropijnego stosowaną do kompresji danych. Zakłada się, że mamy pełną wiedzę na temat statystyki sygnału. Istnieją jednak wersje kodowania Huffmana, które są używane z mediami strumieniowymi i nie mogą wiedzieć wszystkiego o statystykach sygnału. Jak działają te adaptacyjne kodery Huffmana ?

Artykuł w Wikipedii ma całkiem niezły opis adaptacyjnego procesu kodowania Huffmana z wykorzystaniem jednej z godnych uwagi implementacji, algorytmu Vittera. Jak zauważyłeś, standardowy koder Huffmana ma dostęp do funkcji masy prawdopodobieństwa swojej sekwencji wejściowej, którą wykorzystuje do konstruowania wydajnego kodowania najbardziej prawdopodobnych wartości symboli. Na przykład w prototypowym przykładzie kompresji danych opartej na plikach ten rozkład prawdopodobieństwa można obliczyć przez histogramowanie sekwencji wejściowej, zliczając liczbę wystąpień każdej wartości symbolu (symbole mogą być na przykład sekwencjami 1-bajtowymi). Ten histogram służy do wygenerowania drzewa Huffmana, takiego jak ten (zaczerpnięte z artykułu z Wikipedii):

Drzewo jest ułożone według malejącej masy lub prawdopodobieństwa wystąpienia w sekwencji wejściowej; węzły liści u góry reprezentują najbardziej prawdopodobne symbole, które otrzymują zatem najkrótsze reprezentacje w skompresowanym strumieniu danych. Drzewo jest następnie zapisywane wraz ze skompresowanymi danymi, a następnie jest wykorzystywane przez dekompresor do późniejszej regeneracji (nieskompresowanej) sekwencji wejściowej. Jako jedna z pierwszych implementacji kodu entropijnego, standardowe kodowanie Huffmana jest dość proste.

Struktura adaptacyjnego kodera Huffmana jest dość podobna; wykorzystuje podobną do drzewa reprezentację statystyk sekwencji wejściowej, aby wybrać wydajne kodowanie dla każdej wartości symbolu wejściowego. Główna różnica polega na tym, że jako implementacja algorytmu przesyłania strumieniowego nie jest dostępna a priori wiedza na temat funkcji masy prawdopodobieństwa wejściowego; statystyki sekwencji muszą być oszacowane w locie. Jeśli chcemy zastosować ten sam schemat kodowania Huffmana, oznacza to, że drzewo użyte do wygenerowania kodowania każdego symbolu w skompresowanym strumieniu musi być budowane i utrzymywane dynamicznie podczas przetwarzania strumienia wejściowego.

Algorytm Vittera jest jednym ze sposobów osiągnięcia tego; w trakcie przetwarzania każdego symbolu wejściowego drzewo jest aktualizowane, zachowując jego charakterystykę zmniejszania prawdopodobieństwa wystąpienia symbolu podczas przesuwania się w dół drzewa. Algorytm określa zestaw reguł dotyczących sposobu aktualizowania drzewa w czasie oraz sposobu kodowania uzyskanych skompresowanych danych w strumieniu wyjściowym. Gdy sekwencja wejściowa jest wykorzystywana, struktura drzewa powinna reprezentować coraz dokładniejszy opis rozkładu prawdopodobieństwa danych wejściowych. W przeciwieństwie do standardowego podejścia do kodowania Huffmana, dekompresor nie ma statycznego drzewa do użycia do dekodowania; musi on wykonywać te same funkcje konserwacji drzewa w sposób ciągły podczas procesu dekompresji.

Podsumowując : Adaptacyjny koder Huffmana działa bardzo podobnie do standardowego algorytmu; jednak zamiast statycznego pomiaru statystyk całej sekwencji wejściowej (drzewa Huffmana), dynamiczne, skumulowane (tj. od pierwszego symbolu do bieżącego symbolu) oszacowanie rozkładu prawdopodobieństwa sekwencji jest wykorzystywane do kodowania (i dekodowania) każdego symbolu . W przeciwieństwie do standardowego podejścia do kodowania Huffmana, adaptacyjny algorytm Huffmana wymaga tej analizy statystycznej zarówno w koderze, jak i dekoderze.