Poza Bity Całkowite: Nowy Paradygmat w Kompresji

W naszej eksploracji kompresji bezstratnej, zgłębiliśmy kodowanie Huffmana, genialną metodę, która przypisuje kody o zmiennej długości symbolom w oparciu o ich częstotliwość. Jest ona optymalna w pewnym sensie: żaden inny kod prefiksowy nie jest w stanie osiągnąć lepszej średniej długości kodu. Ma ona jednak wrodzone ograniczenie. Kodowanie Huffmana musi przypisać każdemu symbolowi całkowitą, liczbę bitów. Na przykład znak może otrzymać kod 3-bitowy lub 4-bitowy, ale nigdy 3.5-bitowy.

Jak jednak dowiedzieliśmy się z Teorii Informacji Shannona, prawdziwa zawartość informacyjna symbolu, jego entropia, często nie jest liczbą całkowitą. Symbol może teoretycznie przenosić 2.58 bitu informacji. Będąc ograniczonym do kodów o długości całkowitej, kodowanie Huffmana może tylko przybliżyć ten teoretyczny limit. Nasuwa to naturalne pytanie: czy istnieje metoda, która może uwolnić się od tego ograniczenia całkowitoliczbowego i zbliżyć się jeszcze bardziej do prawdziwej entropii danych? Odpowiedź brzmi "tak" i jest nią potężna i elegancka technika znana jako Kodowanie Arytmetyczne.

Kodowanie arytmetyczne reprezentuje fundamentalnie inne i potężniejsze podejście do kodowania entropijnego. Zamiast zastępować każdy symbol odrębnym kodem binarnym, koduje ono całą wiadomość jako pojedynczą, wysokoprecyzyjną liczbę ułamkową z przedziału od 0 do 1. Ta genialna metoda w efekcie pozwala na przydzielenie ułamkowej liczby bitów do każdego symbolu, umożliwiając osiągnięcie współczynników kompresji, które są konsekwentnie bliższe teoretycznemu limitowi wyznaczonemu przez entropię.

Podstawowa Koncepcja: Wiadomość jako Punkt na Osi Liczbowej

Aby zrozumieć kodowanie arytmetyczne, najlepiej odrzucić ideę podstawiania kodów jeden do jednego, a zamiast tego wyobrazić sobie proces jako stopniowe zawężanie przedziału na osi liczbowej.

Przedział Początkowy

Proces rozpoczyna się od zdefiniowania przedziału początkowego, zazwyczaj od 0.0 do (ale nie włączając) 1.0, co możemy zapisać jako $[0, 1)$. Ten przedział reprezentuje cały wszechświat możliwych wiadomości, które można zakodować.

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 naszym alfabecie. Co kluczowe, 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ę naszego modelu statystycznego, który musi być wspólny zarówno dla kodera, jak i dekodera.

Kodowanie jako Proces Przybliżania

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

1. Gdy odczytywany jest pierwszy symbol wiadomości, algorytm wybiera podprzedział odpowiadający temu symbolowi. Ten podprzedział staje się nowym "bieżącym przedziałem".
2. 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)$.
3. Następnie wybiera pod-podprzedział odpowiadający drugiemu symbolowi. Staje się on kolejnym bieżącym przedziałem.
4. Proces ten jest kontynuowany, a każdy symbol powoduje, że algorytm "przybliża się" do coraz mniejszego fragmentu osi liczbowej.

Po przetworzeniu ostatniego symbolu, algorytm pozostaje z ostatecznym, niezwykle wąskim przedziałem liczb. Każda liczba, która mieści się w tym ostatecznym przedziale, jednoznacznie identyfikuje oryginalną wiadomość. Wyjściem kodera jest po prostu binarna reprezentacja dowolnej takiej liczby, wybrana tak, aby była jak najkrótsza, a jednocześnie wciąż mieściła się w tym ostatecznym przedziale.

Szczegółowy Przykład Kodowania

Prześledźmy proces kodowania na konkretnym przykładzie. Zakodujemy słowo "CACAO".

Po pierwsze, potrzebujemy prawdopodobieństw dla każdego znaku w naszym alfabecie. Dla tego przykładu załóżmy następujący model:

Będziemy śledzić nasz bieżący przedział za pomocą dwóch zmiennych: $\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}$.

Pierwszy symbol to 'C'. Zgodnie z naszym modelem, przedział dla 'C' to [0.0, 0.3). Wybieramy odpowiadający mu podprzedział wewnątrz bieżącego przedziału (skalując według szerokości bieżącego przedziału).

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

Teraz pracujemy w całości w naszym nowym przedziale [0.0, 0.3). Dzielimy ten nowy, mniejszy przedział, używając tych samych pierwotnych proporcji, czyli bierzemy kumulatywny start i koniec symbolu w skali 0–1 i skalujemy je względem 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)

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)

Cała nasza wiadomość "CACAO" jest teraz reprezentowana przez ostateczny przedział [0.0972, 0.099). Możemy wybrać dowolną liczbę z tego przedziału jako naszą zakodowaną wiadomość. W praktyce wybiera się liczbę, której binarna reprezentacja ułamkowa jest najkrótsza spośród liczb mieszczących się w tym przedziale.

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

Proces Dekompresji: Odwracanie Przybliżenia

Proces dekompresji jest lustrzanym odbiciem kodowania. Dekoder musi zacząć z dokładnie tym samym początkowym modelem prawdopodobieństwa. Otrzymuje on pojedynczą zakodowaną liczbę (np. 0.09765625).

1. 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'.
2. 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.
3. 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'.
4. Powtarzaj: Proces jest kontynuowany. Dekoder "przybliża" przedział 'A', ponownie renormalizuje wartość, odkrywa, że odpowiada ona 'C' itd., aż cała wiadomość "CACAO" zostanie idealnie odtworzona.

Kodowanie Arytmetyczne a Kodowanie Huffmana: Głębsze Porównanie

Teraz możemy w pełni docenić, dlaczego kodowanie arytmetyczne jest teoretycznie lepsze od kodowania Huffmana.

W istocie liczba bitów potrzebna do zakodowania symbolu w kodowaniu arytmetycznym wynosi $-\log_2(P(\text{symbol}))$, co bezpośrednio odzwierciedla jego zawartość informacyjną. Kodowanie Huffmana jest zmuszone zaokrąglić tę wartość do najbliższej liczby całkowitej. Ta separacja modelu statystycznego od silnika kodującego bity jest główną zaletą kodowania arytmetycznego, czyniąc je niezwykle elastycznym i adaptowalnym.

Rzeczywistość Praktyczna i Współczesne Zastosowanie

Mimo swojej teoretycznej wyższości, kodowanie arytmetyczne potrzebowało więcej czasu na szeroką adaptację niż kodowanie Huffmana. Było to częściowo spowodowane jego większą złożonością obliczeniową, ale w dużej mierze także kwestiami patentowymi. Kluczowe aspekty algorytmu zostały opatentowane przez firmy takie jak IBM i AT&T w latach 80-tych, co zniechęcało do jego stosowania w otwartych standardach i wolnym oprogramowaniu.

Po wygaśnięciu tych patentów w latach 2000-nych kodowanie arytmetyczne stało się kluczowym składnikiem wielu najnowocześniejszych standardów kompresji, gdzie osiągnięcie najlepszej możliwej kompresji jest najważniejsze. Jest kluczową częścią:

• Nowoczesnej Kompresji Obrazu: Jest podstawowym elementem standardu obrazu JPEG2000.
• Wysokowydajnego Kodowania Wideo: Jest używane w schemacie kodowania entropijnego CABAC (context-adaptive binary arithmetic coding) w ramach standardów wideo H.264/AVC i H.265/HEVC, które napędzają większość nowoczesnego streamingu wideo.
• Innych Specjalistycznych Kompresorów: Jest używane w różnych innych wysokowydajnych kompresorach danych, gdzie koszt obliczeniowy jest drugorzędny w stosunku do współczynnika kompresji.

Kodowanie arytmetyczne pozostaje pięknym przykładem tego, jak głęboka idea matematyczna może dostarczyć niemal idealnego rozwiązania praktycznego problemu inżynieryjnego. Przedstawiając całą wiadomość jako pojedynczy punkt w przestrzeni liczbowej, oferuje najwydajniejszą możliwą ekspresję danych zgodnie z ich właściwościami statystycznymi, ugruntowując swoje miejsce jako jeden z najważniejszych algorytmów w historii kompresji danych.