Serious Magazine #13

Kompresja arytmetyczna
W poprzednim artykule (w tym samym numerze Seriousa) opisałem pewien sposób kompresji z wykorzystaniem liczb rzeczywistych. Muszę przyznać, że nie jest to nic oryginalnego. Pomysł ten został opisany już w 1963 roku. Jednak właśnie wykorzystanie liczb rzeczywistych komplikowało na tyle cały algorytm, że dopiero w latach osiemdziesiątych podano pierwsze praktyczne wersje tego algorytmu. Spróbujmy pozbyć się liczb rzeczywistych. Rozważaliśmy przedział <0;1). Możemy go przeskalować na przedział <0;65536) i używać liczb całkowitych. Pomimo, że są to liczby całkowite wciąż posługuję się przedziałem otwartym, gdyż mogę w ten sposób oprzeć się o założenia dla liczb rzeczywistych i nie muszę pamiętać o dodawaniu i odejmowaniu 1, co mogłoby zaciemnić wyja śnienia. (Oznaczmy maksymalną wartość przedziału jako M.) Jeśli zaczniemy dzielić przedział <0; 65536) na mniejsze, to w pewnym momencie i tak pojawią się ułamki. Aby temu zapobiec należy zawężony przedział znowu przeskalować tak, aby był zbliżony do rozmiaru początkowego. Jeżeli zawężony przedział znajdował się w przedziale: <0; 32768) to najstarszy bit w obu granicach przedziału jest zerem, więc możemy zapisać zero jako bit wynikowy. Liczba będzie zawarta w tym przedziale, a więc na pewno będzie się rozpoczynać od bitu 0. Teraz należy przedział przeskalować. Ponieważ najstarszy bit już nas nie interesuje (został zapisany), więc przesuwamy bity w obu granicach przedziału w lewo. Do najmłodszego bitu w granicy lewej wstawiamy 0 natomiast prawej 1. Ma to na celu uzyskanie jak największego przedziału po przeskalowaniu.

Podobną sytuację mamy, gdy przedział jest zawarty w przedziale: <32768; 65536), wówczas zapisujemy 1 jako bit wyniku, sprowadzamy przedział do pierwszej połowy (odejmujemy od granic liczbę 32768) i przeskalowujemy tak samo jak przedział <0; 32768). Sytuacja się komplikuje, gdy zawężony przedział zawiera się w obu powyższych połówkach. Wówczas najstarszy bit lewej granicy jest 0, a prawej 1. Jeśli nic nie wyślemy na wyjście i nie będziemy przeskalowywać przedziału to może nam się skończyć zakres liczb. Do tego nie możemy dopuścić, gdyż nie odkodujemy informacji. Jeżeli każda z granic leży w osobnej połówce to mogą wystąpić dwie sytuacje:

nowy przedział jest na tyle duży, że można go dalej dzielić,
przedział jest zbyt mały do podziału (nie można podzielić go na tyle części ile jest kodowanych symboli (zwykle 256)).

Przedział można uważać za wystarczająco duży jeśli jest większy niż 1/4 część całego przedziału. Aby zapobiec sytuacji 2 sprawdzamy, czy dolna granica przedziału jest większa lub równa 1/4 M, a granica górna mniejsza od 3/4 M. Jeśli tak to od obu granic odejmujemy 1/4 M, oraz zwiększamy licznik informujący, że zrobiliśmy taką operację. Standardowo również przeskalowujem tak otrzymany przedział w sposób jak dla przedziału <0; 32768). Co to nam daje? Na pewno unikniemy dzięki temu zbyt dużego zawężenia przedziłu. Ale co z danymi wynikowymi? Zmodyfikowaliśmy zakres a nie ma po tym śladu w danych wynikowych. Przedział został powiększony dwukrotnie, a więc jeden bit powinien trafić na wyjście. Ale jaki skoro jeszcze nie wiemy do którego przedziału trafi liczba reprezentująca kodowane dane?

Na razie wiemy tylko tyle, że jest w przedziale <1/4 M; 3/4 M). Warto tutaj zauważyć pewną właściwość. Liczby z przedziału <0; 1/4 M) - zaczynają się dwoma najstarszymi bitami równymi zero.

      <1/4 M; 1/2 M) - "01..."
      <1/2 M; 3/4 M) - "10..."
      <3/4 M; M) - "11..."

My rozpatrujemy drugą i trzecią ćwiartkę, więc widać, że bity są przeciwne. Jeśli więc w kolejnych operacjach dolna granica przedziału wzrośnie to cały przedział będzie w górnej połówce czyli najstarszy bit będzie 1, natomiast kolejny na pewno zerem. Jeśli jednak w kolejnych operacjach górna granica przedziału zmniejszy się, to zapisujemy "01". Może się zdażyć, że po kolejnej operacji dolna i górna granica dalej są w różnych połówkach. Wówczas sytuacja się powtarza, więc możemy ponownie zwiększyć wcześniej wspomniany licznik i kontynuować tak jak zostało to opisane powyżej. Krótko mówiąc, zapisując bit sprawdzamy również licznik i zapisujemy dodatkowo tyle przeciwnych bitów ile wynosi wartość licznika (po tym go zerujemy). Może mały przykład:

Sytuacja początkowa wyglądała następująco:

  L = 25000 = %0110000110101000
  P = 37000 = %1001000010001000

 |--------+--+-----+-----+--+--------|
 0           L   32768   P        65536

W następnym kroku otrzymaliśmy (rozważmy dwa przypadki):

 a) L = 20000 = %0100111000100000
    P = 30000 = %0111010100110000

 b) L = 35000 = %1000100010111000
    P = 40000 = %1001110001000000

a) Po zawężeniu przedziału obie granice są w lewej połowie, więc pierwszymi bitami są "01".
b) Po zawężeniu przedziału obie granice są w prawej połowie, więc pierwszymi bitami są "10".

Kodując symbol wykonujemy pętlę tak długo, aż żaden z powyższych warunków nie będzie spełniony. Celem tego jest zapewnienie operacji na możliwie długim przedziale. Zapiszmy to może w jakiś bardziej czytelny sposób ;-)

 etykieta1:
   pobierz_symbol
   wyznacz_nowe_L
   wyznacz_nowe_P

 etykieta2:

     if P<32768 to zapisz_bit(0)
     else if L>=32768 to
     [
       zapisz_bit(1)
       L:=L-32768
       P:=P-32768
     ]
     else if L>=16384 i P<49152 to
     [
       Licznik++
       L:=L-16384
       P:=P-16384
     ]
     else goto etykieta3
     L:=L*2
     P:=P*2+1
   goto etykieta2
 etykieta3:
   if nie koniec to goto etykieta1
   zapisanie_reszty_bitów

Gdzie zapisz_bit(x) można opisać jako:

      zapisz bit x
      zapisz Licznik bitów przeciwnych x
      wyzeruj Licznik

To może jakiś przykład kompresji, żeby rozwiać wszelkie wątpliwości. Standardowo weźmy wyraz "TEST". Prawdopodobieństwa:

      T = 0,5
      E = 0,25
      S = 0,25

Czyli teraz jako przeskalowane granice przedziału:

T = 0,5	* 65536 = 32768
E = 0,25	* 65536 = 16384
S = 0,25	* 65536 = 16384

Standardowo odcinek. Tym razem o innej długości.

      E        S           T
 |--------+--------+----------------|
 0      16384    32768            65536

Najpierw ustawmy warunki początkowe:

L = 0; P = 65535; Licznik = 0;

Kodujemy. Symbol "T"

L = 32768; P = 65535

Obie wartością są w prawej połowie, więc na wyjście wysyłamy bit "1", a przedziały modyfikujemy:

L = (L-32768) << 1 = 0
P = ((P-32768) << 1) + 1 = 65535

<< oznacza tutaj obrót bitów o jedną pozycję w lewo i z wpisaniem zera do bitu najmłodszego.

Nasze przedziały wyglądają teraz tak:

      E        S           T
 |--------+--------+----------------|
 0      16384    32768            65536

Teraz symbol "E"

L = 0; P = 16383

Połowa lewa, wysyłamy bit "0", modyfikujemy przedział:

L = 0
P = 32767

Wciąż lewa połowa, więc "0" na wyjście i modyfikacja przedziału

L = 0
P = 65535

Nowy podział:

      E        S           T
 |--------+--------+----------------|
 0      16384    32768            65536

Symbol "S"

L = 16384; P = 32767

Połowa lewa, więc bit "0", przedział po przeskalowaniu:

L = 32768
P = 65535

Połowa prawa, znowu modyfikujemy przedział i wysyłamy "1":

L = 0
P = 65535

Nowy podział:

      E        S           T
 |--------+--------+----------------|
 0      16384    32768            65536

Symbol "T"

L = 32768; P = 65535

Połowa prawa, więc bit "1", przedział po aktualizacji:

L = 0
P = 65535

Ponieważ są to już wszystkie symbole jakie miały być zakodowane, więc teraz pozostaje tylko wysłać na wyjście liczbę z tego przedziału. Początek przedziału to:

0000000000000000 binarnie,

koniec to:

1111111111111111 również binarnie ;).

Zapisać można równie dobrze początek jak i koniec (lub inną dowolną liczbę z tego przedziału). Widać jednak, że mogą to być dowolne bity i każdy spełni ten warunek. Dlatego w tym przypadku nie ma sensu jej zapisywać. Jednak jest to uzależnione od wartości granicy lewej i prawej. Przypadków jest jednak sporo. Pozostawiam to jednak do przemyślenia Czytelnikowi. Ostatecznie zakodowane dane to: "100011". Przykład ten nie jest w stanie powiedzieć za wiele o wydajności tej metody. Ponieważ zalicza się ona do metod probabilistycznych więc wypadałoby porównać ją z metodą Huffmana. Czy jest lepsza? Zdecydowanie. Zaletą tej metody jest to, że na jednym bicie można zapisać więcej niż jeden symbol!

Niemożliwe? To może przykład. Załóżmy, że mamy do spakowania 100 symboli "A" oraz 1 "B". Prawdopodobieństwa:

A =	100/101
B =	1/101

Granice przedziałów:

A = 64887
B = 649

Wygląda to tak:

               A                B
 |---------------------------+------|
 0                         64887  65536

Kodujemy:

Załóżmym, że początkowo mamy tylko symbole "A"

L = 0; P = 64887

Przedział ten nie jest w całości ani w lewej połowie, ani w prawej, ani nie spełnia warunku

L >= 1/4 M i P < 3/4 M,

więc nic nie wysyłamy na wyjście. Również przedział nie jest poszerzany. Więc nadal:

L = 0; P = 64887

Nowy przedział dla kolejnego "A".

               A                B
 |---------------------------+------|
 0                         64246  64888

L = 0; P = 64246

Znowu żaden z warunków nie jest spełniony - nie wysyłamy żadnego bitu na wyjście. W ten sposób można jeszcze zakodować kilka symboli, więc faktycznie w jednym bicie można "upchać" więcej niż jeden symbol.

To może teraz jakieś porównanie metod Huffmana i metody arytmetycznej. Tradycyjne pliki:

QA.COM

niespakowany	:	12329
Huffman	:	11634
arytmetyczna	:	11479

DEMO.ASM

niespakowany	:	6362
Huffman	:	3151
arytmetyczna	:	3117

W obu przypadkach kompresja arytmetyczna okazała się lepsza od metody Huffmana.

Glonisz/Quasimodos