Czy istnieje uogólnienie Kodowania Huffmana na kodowanie arytmetyczne?

Próbując zrozumieć związki między kodowaniem Huffmana, kodowaniem arytmetycznym i kodowaniem zakresu, zacząłem myśleć o niedociągnięciach kodowania Huffmana związanych z problemem częściowego upakowania bitów .

To znaczy, załóżmy, że masz 240 możliwych wartości dla symbolu i potrzebujesz zakodować to w bitach, utkniesz z 8 bitami na symbol, nawet jeśli nie potrzebujesz „pełnej” 8, ponieważ 8 może wyrazić 256 możliwych wartości za symbol. Rozwiązaniem tego problemu jest coś, co widziałem jako „ułamkowe pakowanie bitów”, w którym można „przesunąć bitem” przez brak potęgi dwóch przy użyciu mnożenia. Podobnie jak mnożenie potęg dwóch jest przesunięciem x * 2 == x << 1i x * 4 == x << 2tak dalej dla wszystkich potęg dwóch, tak też możesz „przesunąć” z nie-potęgą-2 poprzez pomnożenie zamiast tego i spakować w ułamkowe bity wielkości .

Problem jest podobny w przypadku kodowania Huffmana: kończy się na kodach, które muszą mieć niefrakcjonalnie małe bity, a zatem mają tę nieefektywność pakowania. Jednak nie można po prostu użyć rozwiązania fracitonal-bit-packing, ponieważ to rozwiązanie zakłada symbole o stałej wielkości.

Pytanie brzmi: czy są jakieś dokumenty lub rozwiązania, które mogłyby poprawić kodowanie huffmana z podobnym pomysłem jak ułamkowe pakowanie bitów, aby osiągnąć coś podobnego do kodowania arytmetycznego? (lub jakiekolwiek przeciwne wyniki).

Spójrzmy na nieco inny sposób myślenia o kodowaniu Huffmana.

Załóżmy, że masz alfabet trzech symboli, A, B i C, z prawdopodobieństwem 0,5, 0,25 i 0,25. Ponieważ wszystkie prawdopodobieństwa są odwrotnymi potęgami dwóch, ma on optymalny kod Huffmana (tzn. Jest identyczny z kodowaniem arytmetycznym). W tym przykładzie użyjemy kodu kanonicznego 0, 10, 11.

Załóżmy, że naszym stanem jest duża liczba całkowita, którą nazwiemy . Możesz myśleć o kodowaniu jako o funkcji, która przyjmuje bieżący stan oraz symbol do zakodowania i zwraca nowy stan:$s$

$$\begin{align*} \hbox{encode}(s, A) &= 2s\\ \hbox{encode}(s, B) &= 4s + 2\\ \hbox{encode}(s, C) &= 4s + 3\\ \end{align*}$$

Zacznijmy więc od stanu 11 (który jest 1011 w systemie binarnym), kodujemy symbol B. Nowy stan to 46, czyli 101110 w trybie binarnym. Jak widać, jest to „stary” stan z sekwencją 10 dodaną na końcu. Mamy w zasadzie „wyjście” sekwencji bitów 10.

Na razie w porządku.

Zastanów się teraz, jak działa kodowanie arytmetyczne. Jeśli umieścisz prawdopodobieństwa nad wspólnym mianownikiem, symbol A faktycznie reprezentuje zakres symbol B reprezentuje zakres[$[\frac{0}{4},\frac{2}{4})$a symbol C reprezentuje zakres[$[\frac{2}{4},\frac{3}{4})$.$[\frac{3}{4},\frac{4}{4})$

Zasadniczo mnożymy wszystko przez wspólny mianownik. Wyobraź sobie, że stan faktycznie znajdował się w bazie 4. Kodowanie symbolu B naprawdę wypisuje cyfrę 2 z tej bazy, a kodowanie symbolu C wypisuje cyfrę 3 z tej bazy.

Jednak symbol A jest nieco inny, ponieważ nie jest to cała cyfra w bazie 4.

Zamiast tego możemy myśleć o alfabecie jako o zestawie symboli A_0, A_1, B, C, z jednakowym prawdopodobieństwem. To znowu ma optymalny kod Huffmana 00, 01, 10, 11. Lub znowu, możemy pomyśleć o tym w bazie 4. Aby zakodować symbol, po prostu:

$$\begin{align*} \hbox{encode}(s, A_0) &= 4s + 0\\ \hbox{encode}(s, A_1) &= 4s + 1\\ \hbox{encode}(s, B) &= 4s + 2\\ \hbox{encode}(s, C) &= 4s + 3 \end{align*}$$

Więc teraz jest jasne, jak zakodować symbole B i C, ale aby zakodować symbol A, mamy wybór. Które z i A 1 powinniśmy użyć?$A_0$$A_1$

Teraz tutaj jest mądry pomysł: kradniemy jeden bit informacji ze stanu :$s$

i=smod

$$s' = \left\lfloor \frac{s}{2} \right\rfloor$$ $$i = s \bmod 2$$

a następnie .$\hbox{encode}(s', A_i)$

Korzystając z naszego poprzedniego przykładu, , stwierdzamy, że s ′ = 5 i i = 1 , a następnie kodujemy ( 5 , A 1 ) = 4 × 5 + 1 = 21 . Nowy stan to 10101 w systemie binarnym.$s=11$$s'=5$$i=1$$\hbox{encode}(5, A_1) = 4\times 5+1 = 21$

Teraz nie daje to dokładnie takiego samego wyniku bitowego jak kodowanie Huffmana, ale generuje wyjście o tej samej długości. Mam nadzieję, że zobaczycie, że jest to również wyjątkowo dekodowalne. Aby zdekodować symbol, bierzemy resztę po podzieleniu przez 4. Jeśli wartość wynosi 2 lub 3, wówczas symbolem jest odpowiednio B lub C. Jeśli jest to 0 lub 1, to symbolem jest A, a następnie możemy cofnąć kawałek informacji, mnożąc stan przez 2 i dodając 0 lub 1.

$\frac{3}{5}$$\frac{2}{5}$

$$\begin{align*} \hbox{encode}(s, A_0) &= 5s + 0\\ \hbox{encode}(s, A_1) &= 5s + 1\\ \hbox{encode}(s, A_2) &= 5s + 2\\ \hbox{encode}(s, B_0) &= 5s + 3\\ \hbox{encode}(s, B_1) &= 5s + 4 \end{align*}$$

$s' = \left\lfloor \frac{s}{3} \right\rfloor$$i = s \bmod 3$$\hbox{encode}(s', A_i)$

$\frac{p}{q}$

Powodem, dla którego jest to rodzina metod kodowania, jest to, że to, co tu widzieliśmy, jest samo w sobie niepraktyczne; potrzebuje pewnych modyfikacji, aby poradzić sobie z faktem, że prawdopodobnie nie masz liczb całkowitych o nieskończonej precyzji, aby skutecznie manipulować zmienną stanu, i istnieją różne sposoby, aby to osiągnąć. Kodowanie arytmetyczne ma oczywiście podobny problem z precyzją swojego stanu.

Praktyczne warianty obejmują rANS („r” oznacza „stosunek”) i tANS („sterowany tabelą”).

ANS ma kilka interesujących zalet w porównaniu z kodowaniem arytmetycznym, zarówno praktycznych, jak i teoretycznych:

• W przeciwieństwie do kodowania arytmetycznego „stan” jest pojedynczym słowem, a nie parą słów.
• Ponadto koder ANS i odpowiadający mu dekoder mają identyczne stany, a ich operacje są całkowicie symetryczne. Rodzi to kilka interesujących możliwości, takich jak możliwość przeplatania różnych strumieni zakodowanych symboli i wszystko synchronizuje się idealnie.
• Praktyczne implementacje muszą oczywiście „wysyłać” informacje na bieżąco, a nie tylko gromadzić je w dużej liczbie całkowitej, którą należy zapisać na końcu. Jednak rozmiar „wyjścia” można skonfigurować w zamian za (zwykle niewielką) utratę kompresji. Tak więc tam, gdzie kodery arytmetyczne muszą wypisywać bit po czasie, ANS może wysyłać bajt lub wątek jednocześnie. Zapewnia to bezpośredni kompromis między prędkością a kompresją.
• Wydaje się, że jest tak szybki na sprzęcie obecnej generacji, jak binarne kodowanie arytmetyczne, a zatem jest konkurencyjny w stosunku do kodowania Huffmana. To sprawia, że ​​jest on znacznie szybszy niż kodowanie arytmetyczne dużymi alfabetami i jego warianty (np. Kodowanie zakresu).
• Wydaje się być wolny od patentów.

Nie sądzę, żebym kiedykolwiek ponownie używał kodowania arytmetycznego.

Jako prosty przykład, jeśli miałbyś trzy symbole z prawdopodobieństwem 1/3 każdego, twoje optymalne kodowanie Huffmana użyłoby trzech symboli 0, 10 i 11 ze średnią 5/3 bitów.

Istnieją 243 symbole utworzone przez połączenie 5 oryginalnych symboli, każdy z prawdopodobieństwem 1/243. Co jest znacznie bliższe 1/256. Optymalne kodowanie Huffmana koduje 13 tych grup w 7 bitach i 230 grup w 8 bitach, średnio średnio 7,9465 bitów na grupę lub 1,5893 bitów na oryginalny symbol, w porównaniu z 1,6667 bitów dla oryginalnego kodowania Huffmana, z kodowaniem arytmetycznym zajmującym 1,5850 bitów

Teoretycznie możesz po prostu połączyć dwa symbole w jeden większy symbol lub trzy symbole w jeden większy symbol i użyć kombinacji Hufmana dla kombinacji.