Kodowanie Arytmetyczne

Kodowanie arytmetyczne i ułamkowe długości kodów

Kodowanie Huffmana przypisuje symbolom słowa kodowe o zmiennej długości na podstawie ich prawdopodobieństw. Dla ustalonego modelu jest optymalne w klasie binarnych kodów prefiksowych, ponieważ żaden inny kod z tej klasy nie daje mniejszej średniej długości. Ograniczeniem jest całkowita długość każdego słowa kodowego. Znak może otrzymać kod 3-bitowy lub 4-bitowy, lecz nie kod o długości 3.5 bitu.

Entropia źródła często nie jest liczbą całkowitą. Dla przykładu symbol może mieć informację równą 2.58 bitu. Kod Huffmana przybliża taki wynik całkowitymi długościami słów kodowych. Kodowanie arytmetyczne omija to ograniczenie przez reprezentowanie sekwencji za pomocą końcowego podprzedziału [0,1), co pozwala uzyskać średnią długość bliższą entropii modelu. .

Kodowanie arytmetyczne koduje sekwencję przez sukcesywne zawężanie podprzedziału od 0 do 1. W ujęciu idealnym końcowy podprzedział jest reprezentowany przez jedną liczbę, natomiast implementacje emitują bity stopniowo i stosują renormalizację. Taki sposób kodowania pozwala uzyskać średnią długość kodu bliższą granicy wyznaczonej przez entropię modelu. W każdym kroku szerokość przedziału jest mnożona przez prawdopodobieństwo wybranego symbolu, dlatego dłuższe wiadomości wymagają większej precyzji liczbowej.

Podstawowa koncepcja kodowania arytmetycznego

Kodowanie arytmetyczne nie podstawia osobnego słowa kodowego pod każdy symbol. Algorytm stopniowo zawęża przedział liczbowy, zachowując proporcje wynikające z modelu prawdopodobieństwa.

Przedział początkowy

Proces rozpoczyna się od zdefiniowania przedziału początkowego, zazwyczaj od 0.0 do wartości mniejszej od 1.0, co zapisuje się jako $[0, 1)$ . Przedział opisuje zakres reprezentacji używany dla wszystkich wiadomości zgodnych z modelem.

Podział przedziału według prawdopodobieństwa

Następnym krokiem jest podzielenie tego przedziału początkowego na mniejsze podprzedziały, po jednym dla każdego możliwego symbolu w alfabecie. Rozmiar podprzedziału każdego symbolu jest wprost proporcjonalny do jego prawdopodobieństwa wystąpienia.

Symbol o wysokim prawdopodobieństwie (jak 'a' w języku polskim) otrzyma duży podprzedział.
Symbol o niskim prawdopodobieństwie (jak 'ź') otrzyma bardzo mały podprzedział.

Ten początkowy podział przedziału $[0, 1)$ stanowi podstawę modelu statystycznego, który musi być wspólny dla kodera i dekodera.

Kodowanie jako zawężanie przedziału

Gdy algorytm przetwarza wiadomość wejściową symbol po symbolu, sukcesywnie zawęża przedział.

Gdy odczytywany jest pierwszy symbol wiadomości, algorytm wybiera podprzedział odpowiadający temu symbolowi. Ten podprzedział staje się nowym "bieżącym przedziałem".
Dla drugiego symbolu algorytm bierze ten nowy, mniejszy bieżący przedział i dzieli go w dokładnie takich samych proporcjach jak pierwotny przedział $[0, 1)$ .
Następnie wybiera kolejny podprzedział odpowiadający drugiemu symbolowi. Staje się on kolejnym bieżącym przedziałem.
Proces jest kontynuowany, a każdy symbol wybiera coraz mniejszy fragment przedziału liczbowego.

Po przetworzeniu ostatniego symbolu algorytm otrzymuje końcowy przedział liczb. Przy ustalonej długości wiadomości i wspólnym modelu każda liczba z tego przedziału identyfikuje zakodowaną sekwencję. Koder emituje binarną reprezentację liczby lub przedziału, wybierając strumień wystarczająco krótki, który nadal wskazuje ten przedział.

Przykład kodowania

Proces można prześledzić na konkretnym przykładzie. Zakodujemy słowo "CACAO".

Krok 0: ustalenie modelu prawdopodobieństwa

Dla przykładu przyjęto następujący model prawdopodobieństwa dla alfabetu:

Symbol	Prawdopodobieństwo	Przedział Początkowy
'C'	0.3	[0.0, 0.3)
'A'	0.2	[0.3, 0.5)
'O'	0.5	[0.5, 1.0)

Bieżący przedział opisują dwie zmienne: $\text{dolna}$ i $\text{górna}$ . Początkowo $\text{dolna} = 0.0$ i $\text{górna} = 1.0$ . Szerokość bieżącego przedziału to $\text{szerokość} = \text{górna} - \text{dolna}$ .

Krok 1: zakoduj pierwszy symbol, 'C'

Pierwszy symbol to 'C'. Zgodnie z modelem jego przedział to [0.0, 0.3). Odpowiadający mu podprzedział jest wybierany wewnątrz bieżącego przedziału przez skalowanie do jego szerokości.

Bieżący przedział: $[0.0, 1.0)$ , więc $\text{szerokość} = 1.0 - 0.0 = 1.0$ .
Nowa granica $\text{dolna}$ staje się starą dolną granicą plus szerokość pomnożona przez początek przedziału 'C' (kumulatywny start w skali 0-1): $0.0 + (1.0 \times 0.0) = 0.0$ .
Nowa granica $\text{górna}$ staje się starą dolną granicą plus szerokość pomnożona przez koniec przedziału 'C' (kumulatywny koniec w skali 0-1): $0.0 + (1.0 \times 0.3) = 0.3$ .
Nowy Bieżący Przedział: [0.0, 0.3)

Krok 2: zakoduj drugi symbol, 'A'

Obliczenia pozostają w nowym przedziale [0.0, 0.3). Ten mniejszy przedział jest dzielony według pierwotnych proporcji: początek i koniec skumulowanego przedziału symbolu w skali 0-1 są skalowane do bieżącej szerokości.

Bieżący przedział: $[0.0, 0.3)$ , więc $\text{szerokość} = 0.3 - 0.0 = 0.3$ .
Przedział dla 'A' to [0.3, 0.5). To oznacza, że w skali 0-1 'A' zaczyna się w 0.3 i kończy w 0.5. Stosujemy te wartości, mnożąc przez szerokość bieżącego przedziału i dodając dolną granicę.
Nowa $\text{dolna}$ granica: $0.0 + (0.3 \times 0.3) = 0.0 + 0.09 = 0.09$ .
Nowa $\text{górna}$ granica: $0.0 + (0.3 \times 0.5) = 0.0 + 0.15 = 0.15$ .
Nowy Bieżący Przedział: [0.09, 0.15)

Krok 3, 4, 5: powtórz dla 'C', 'A', 'O'

Proces jest kontynuowany dla pozostałych znaków, za każdym razem bierzemy kumulatywny start i koniec symbolu (w skali 0-1), mnożymy przez aktualną szerokość i dodajemy do bieżącej dolnej granicy, aby uzyskać nowy podprzedział.

Po 'C': Przedział staje się $[0.09, 0.108)$ . (obliczenia: szerokość = 0.15 - 0.09 = 0.06; dla 'C' [0.0,0.3): dolna = 0.09 + 0.06*0.0 = 0.09; górna = 0.09 + 0.06*0.3 = 0.09 + 0.018 = 0.108)
Po 'A': Przedział staje się $[0.0954, 0.099)$ . (obliczenia: szerokość = 0.108 - 0.09 = 0.018; dla 'A' [0.3,0.5): dolna = 0.09 + 0.018*0.3 = 0.09 + 0.0054 = 0.0954; górna = 0.09 + 0.018*0.5 = 0.09 + 0.009 = 0.099)
Po 'O': Ostateczny Przedział: [0.0972, 0.099). (obliczenia: szerokość = 0.099 - 0.0954 = 0.0036; dla 'O' [0.5,1.0): dolna = 0.0954 + 0.0036*0.5 = 0.0954 + 0.0018 = 0.0972; górna = 0.0954 + 0.0036*1.0 = 0.0954 + 0.0036 = 0.099)

Krok 6: finalizacja i wygenerowanie kodu

Wiadomość "CACAO" reprezentuje ostateczny przedział [0.0972, 0.099). Dowolna liczba z tego przedziału może być zakodowaną wiadomością. W praktyce wybiera się liczbę o krótkiej binarnej reprezentacji ułamkowej spośród liczb należących do tego przedziału.

Na przykład liczba 0.09765625 znajduje się w tym przedziale. Jej binarna reprezentacja ułamkowa to $0.00011001$ . Ten ciąg binarny jest skompresowanym wyjściem.

Dekodowanie przez odtwarzanie przedziału

Dekoder odtwarza te same podziały co koder. Musi rozpocząć pracę z identycznym początkowym modelem prawdopodobieństwa i otrzymuje zakodowaną liczbę, na przykład 0.09765625.

Odkoduj Symbol 1: Dekoder patrzy na swój początkowy przedział [0, 1). Sprawdza, do którego podprzedziału symbolu wpada wartość 0.09765625. Wpada ona do [0.0, 0.3), więc pierwszym symbolem jest 'C'.
Zaktualizuj Przedział:Dekoder wie teraz, że pierwszy symbol to 'C', więc aktualizuje swój bieżący przedział do [0.0, 0.3), dokładnie tak, jak zrobił to koder.
Zrenormalizuj Wartość i Odkoduj Symbol 2: Aby znaleźć następny symbol, dekoder przemapowuje otrzymaną wartość do tego nowego przedziału. Oblicza $(0.09765625 - 0.0) / 0.3 \approx 0.3255$ . Następnie sprawdza, gdzie ta nowa wartość mieści się w oryginalnym modelu. 0.3255 mieści się w przedziale dla 'A' [0.3, 0.5). Drugi symbol to 'A'.
Powtarzaj:Proces jest kontynuowany. Dekoder zawęża przedział dla 'A', ponownie renormalizuje wartość i odczytuje 'C' oraz kolejne symbole, aż odtworzy wiadomość "CACAO".

Kodowanie arytmetyczne i kodowanie Huffmana

Obie metody korzystają z modelu statystycznego, lecz różnią się sposobem reprezentacji symboli i sekwencji.

Aspekt	Kodowanie Huffmana	Kodowanie arytmetyczne
Alokacja bitów	Przypisuje każdemu symbolowi słowo kodowe o całkowitej długości. Długości mogą różnić się między symbolami.	Daje ułamkową średnią liczbę bitów na symbol, obliczaną dla całej wiadomości.
Optymalność	Dla ustalonego modelu jest optymalne w klasie kodów prefiksowych, lecz całkowite długości słów powodują odstęp od entropii.	Przy zgodnym modelu średnia długość może zbliżać się do entropii modelu. Pozostaje narzut opisu modelu i zakończenia.
Separacja modelu i kodera	Model statystyczny i drzewo kodu są powiązane w konstrukcji kodu prefiksowego, dlatego zmiana rozkładu zwykle wymaga nowego drzewa.	Mechanizm kodowania jest oddzielony od modelu statystycznego. Ten sam koder może współpracować z modelami stałymi i adaptacyjnymi, w tym z modelami Markowa.
Szybkość i złożoność	Zwykle wymaga zliczania, sortowania i przechodzenia przez drzewo, więc kodowanie jest proste obliczeniowo.	Wymaga aktualizacji przedziału i renormalizacji. Implementacje mogą używać arytmetyki całkowitoliczbowej, a koszt zależy od modelu.

Idealny wkład informacyjny symbolu o prawdopodobieństwie $P(\text{symbol})$ wynosi $-\log_2(P(\text{symbol}))$ bitu. Huffman musi używać całkowitych długości słów kodowych, natomiast koder arytmetyczny może zbliżyć średnią długość do tego wkładu. Oddzielenie modelu statystycznego od mechanizmu kodowania ułatwia używanie modeli stałych i adaptacyjnych. Wartość jest średnią dla modelu. Długość kodu pojedynczego symbolu może być inna. W modelu adaptacyjnym prawdopodobieństwa zmieniają się podczas kodowania i dekodowania.

Zastosowania praktyczne

Upowszechnienie kodowania arytmetycznego trwało dłużej niż kodowania Huffmana. Wpływały na to koszty implementacji oraz patenty obejmujące wybrane rozwiązania, szczególnie w latach 80. i 90. Ograniczenia licencyjne zmniejszały zainteresowanie stosowaniem tej metody w otwartych standardach i oprogramowaniu.

Po wygaśnięciu części patentów ograniczenie licencyjne osłabło. Kodowanie arytmetyczne jest obecne w standardach, które stosują modelowanie kontekstowe i wymagają krótkiego strumienia wynikowego:

Kompresji obrazów: JPEG 2000 stosuje binarny koder arytmetyczny MQ w kodowaniu bloków.
Kodowaniu wideo: CABAC, czyli kontekstowe binarne kodowanie arytmetyczne, jest elementem standardów H.264/AVC i H.265/HEVC.
Innych kompresorach specjalistycznych: Metoda jest używana w kompresorach, w których koszt obliczeń można uzasadnić krótszym strumieniem wynikowym.

Kodowanie arytmetyczne pokazuje, jak model statystyczny i operacje na przedziałach mogą ograniczyć średnią długość bezstratnego strumienia. Jego przydatność zależy od modelu, precyzji, sposobu renormalizacji oraz kosztu obliczeń. Strumień musi dodatkowo przekazywać informację o modelu albo korzystać z uzgodnionego modelu po stronie dekodera. Dekoder potrzebuje także ustalonej kolejności symboli i reguły zakończenia, ponieważ sam podprzedział nie wyznacza wiadomości o nieograniczonej długości.