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).

— Realz Slaw
źródło

Kodowanie arytmetyczne jest już optymalne. Nie ma potrzeby go poprawiać.

— Yuval Filmus,

@YuvalFilmus tak, miałem na myśli, jak poprawić kodowanie Huffmana, aby dostosować go do kodowania arytmetycznego.

— Realz Slaw

Sugeruje się, że kodowanie w Asymmetric Numeral System (ANS) jest łatwiejsze do zrozumienia niż kodowanie arytmetyczne. W szczególności nieco łatwiej jest zobaczyć ten konkretny preparat jako „ułamkowe upakowanie bitów”.

— pseudonim

@Pseudonim Znalazłem tę stronę, która wydaje się tworzyć to połączenie między rANS i Huffman Coding. Nie mogę powiedzieć, że jeszcze to rozumiem, ale myślę, że to wystarczy. Jeśli podasz komentarz jako odpowiedź, zaakceptuję.

— Realz Slaw

@YuvalFilmus Mam nadzieję, że przedstawiłem argument, że kodowanie arytmetyczne wymagało poprawy, a ANS jest poprawą.

— pseudonim

Odpowiedzi:

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{aligned} kodować (s, ZA) & = 2) s \\ kodować (s, b) & = 4 s + 2) \\ kodować (s, do) & = 4 s + 3) \end{aligned}

$\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{aligned} kodować (s, {ZA}_{0}) & = 4 s + 0 \\ kodować (s, {ZA}_{1}) & = 4 s + 1 \\ kodować (s, b) & = 4 s + 2) \\ kodować (s, do) & = 4 s + 3) \end{aligned}

$\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 powinniśmy użyć? $A_0$ $A_1$

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

s^{'} = ⌊ \frac{s}{2} ⌋

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

i = s mod 2

$i = s \bmod 2$

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

Korzystając z naszego poprzedniego przykładu, , stwierdzamy, że i , a następnie . 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{aligned} encode (s, A_{0}) & = 5 s + 0 \\ encode (s, A_{1}) & = 5 s + 1 \\ encode (s, A_{2}) & = 5 s + 2 \\ encode (s, B_{0}) & = 5 s + 3 \\ encode (s, B_{1}) & = 5 s + 4 \end{aligned}

$\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.

— Pseudonim
źródło

To najjaśniejsze wyjaśnienie kodowania ANS, jakie kiedykolwiek widziałem.

— Michael Deardeuff,

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.

— gnasher729
źródło