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:
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
|