programowanie asembler algorytmy

kompresja statystyczna

Kodowanie ogólne.

Kompresowanie tą metodą polega na przypisaniu wszystkim symbolom takiej samej, jak najmiejszej ilości bitów. Ilość bitów potrzebną do zakodowania informacji obliczamy według następującego sposobu (zakładamy, że mamy co najmiej dwa różne symbole do zakodowania):

Obliczona liczba jest najmniejszą liczbą bitów potrzebną, by zakodować każdy dany symbol różną sekwencją bitów. Liczba symboli jest nieograniczona, ale nie może być mniejsza od dwóch (logiczne - gdy mamy tylko jeden powtarzający się symbol to możemy zapisać tylko ilość jego powtórzeń).

Spróbujmy 'skompresować' przykładowy tekst:

Ala ma kota. Kot ma AIDS.

Zakładamy, że w postaci oryginalnej każdy symbol kodowany jest ośmioma bitami. Tak więc rozmiar danych nieskompresowanych wynosi: 25 znaków * 8 bitów = 200 bitów. Teraz obliczamy minimalną ilość bitów dla każdego symbolu:

Przypisujemy każdej liczbie określony kod:

. = 0000
  = 0001
A = 0010
D = 0011
I = 0100
K = 0101
S = 0110
a = 0111
k = 1000
l = 1001
m = 1010
o = 1011
t = 1100

I w końcu zamieniamy oryginalny ciąg znaków na natępujący ciąg bitów:

0010 1001 0111 0001 1010 0111 0001 1000 1011 1100 0111 0000 0001
0101 1011 1100 0001 1010 0111 0001 0010 0100 0011 0110 0000

Ma on długość: 25 znaków * 4 bity = 100 bitów. Tak więc skompresowaliśmy dane o połowę.

Kodowanie przedrostkowe.

Jednak nie musimy każdemu znakowi przypisywać takiej samej ilości bitów. W praktyce częstotliwości poszczególnych znaków znacznie się różnią. Możemy więc użyć różnej długości kodów dla poszczególnych znaków. Musimy pamiętać o tym, żeby żaden kod nie był początkiem (przedrostkiem) drugiego. Taka sytuacja doprowadziłaby do niejednoznaczności przy dekodowaniu otrzymanego strumienia bitów. Teraz pozostaje jedynie problem przydziału kodów do poszczególnych znaków.

Algorytm Shannon-Fano.

Pierwsi rozwiązali ten problem panowie Shannon i Fano. Przedstawię skrótowo ich algorytm:

Efektywność tego algorytmu zależy przede wszystkim od początkowego ułożenia (kolejności) elementów w zbiorze.

Sprawdźmy działanie algorytmu dla podanego wcześniej przykładowego tekstu. Zbiór zawiera pary elementów: częstotliwość i symbol. Przedtawiam kolejne kroki dzielenia zbioru (na zbiorami znajdują się ich wagi):

 25
.=2, =5,A=2,D=1,I=1,K=1,S=1,a=4,k=1,l=1,m=2,o=2,t=2
 13                                     | 12
.=2, =5,A=2,D=1,I=1,K=1,S=1             | a=4,k=1,l=1,m=2,o=2,t=2
7         | 6                           | 6               | 6
.=2, =5   | A=2,D=1,I=1,K=1,S=1         | a=4,k=1,l=1     | m=2,o=2,t=2
2   | 5   | 3         | 3               | 4   | 2         | 4         | 2
.=2 |  =5 | A=2,D=1   | I=1,K=1,S=1     | a=4 | k=1,l=1   | m=2,o=2   | t=2
2   | 5   | 2   | 1   | 2         | 1   | 4   | 1   | 1   | 2   | 2   | 2
.=2 |  =5 | A=2 | D=1 | I=1,K=1   | S=1 | a=4 | k=1 | l=1 | m=2 | o=2 | t=2
2   | 5   | 2   | 1   | 1   | 1   | 1   | 4   | 1   | 1   | 2   | 2   | 2
.=2 |  =5 | A=2 | D=1 | I=1 | K=1 | S=1 | a=4 | k=1 | l=1 | m=2 | o=2 | t=2

Zakładając, że elementom z 'lewego' zbioru dołączamy jedynkę, a z 'prawego' zero to kody znaków są następujące:

. = 000
  = 001
A = 0100
D = 0101
I = 01100
K = 01101
S = 0111
a = 100
k = 1010
l = 1011
m = 1100
o = 1101
t = 111

Zobaczmy jak wygląda zakodowany strumień bitów:

0100 1011 100 001 1100 100 001 1010 1101 111 100 000 001
01101 1101 111 001 1100 100 001 0100 01100 0101 0111 000

Obliczmy długość strumienia bitów: 2 * 3 + 5 * 3 + 2 * 4 + 1 * 4 + 1 * 5 + 1 * 5 + 1 * 4 + 4 * 3 + 1 * 4 + 1 * 4 + 2 * 4 + 2 * 4 + 2 * 3 = 6 + 15 + 8 + 4 + 5 + 5 + 4 + 12 + 4 + 4 + 8 + 8 + 6 = 89 bitów. Jak widać otrzymaliśmy lepszą kompresję niż przy kodach stałej długości.

Algorytm Huffmana.

Algotym Huffmana jest jakby odwróceniem algorytmu Shannon-Fano. Zamiast dzielić zbiór na podzbiory, Huffman łączy elementy. Oto kroki kompresji w jego algorytmie:

Teraz pokażę przykład. Algorytm Huffmana zaprezentuję jednak w postaci drzewa binarnego. Tak będzie wygodniej i czytelniej.

D=1  I=1 K=1  S=1  l=1  k=1  
 \    /   \    /    \    /
  DI=2     KS=2      lk=2   .=2  A=2  m=2 o=2  t=2
    \        /         \     /    \    /   \    /
      DIKS=4            lk.=4      Am=4     ot=4   a=4   =5
             \         /              \      /      \    /
              DIKSlk.=8                Amot=8        a =9
                       \              /               /
                        DIKSlk.Amot=16               /
                                     \              /
                                     DIKSlk.Amota =25

Kody odczytujemy idąc od korzenia drzewa i dołączając do kodu zero, gdy idziemy w lewo lub jedynkę, gdy idziemy w prawo. Wobec tego wyglądają one tak:

. = 0011
  = 11
A = 0100
D = 00000
I = 00001
K = 00010
S = 00011
a = 10
k = 00101
l = 00100
m = 0101
o = 0110
t = 0111

Zobaczmy jak wygląda zakodowany strumień bitów:

0100 00100 10 11 0101 10 11 00101 0110 0111 10 0011 11
00010 0110 0111 11 0101 10 11 0100 00001 00000 00011 0011

Obliczmy długość strumienia bitów: 2 * 4 + 5 * 2 + 2 * 4 + 1 * 5 + 1 * 5 + 1 * 5 + 1 * 5 + 4 * 2 + 1 * 5 + 1 * 5 + 2 * 4 + 2 * 4 + 2 * 3 = 8 + 10 + 8 + 5 + 5 + 5 + 5 + 8 + 5 + 5 + 8 + 8 + 8 = 88 bitów. Jak widać otrzymaliśmy lepszą kompresję nawet niż przy zastosowaniu algorytmu Shannon-Fano. W praktyce algorytm Huffmana jest prawie zawsze lepszy od algorytmu Shannon-Fano i nigdy nie jest od niego gorszy.

Ograniczanie długości kodów.

Czasami może się zdarzyć, że najdłuższy kod ma bardzo dużą długość, trudną do obsługiwania. W takim przypadku jesteśmy zmuszeni do ograniczenia ich długości. Najlepszym sposobem na to jest manipulowanie statystykami według następującej pętli:

Uwaga: stała k jest stała tylko w danym powtórzeniu pętli. Możesz obliczać ją od nowa na początku pętli. Oto przykładowy sposób na obliczanie wartości stałej k:

Należy uważać na to, by nie ustawić za małej maksymalnej długości kodu. W takim przypadku nigdy jej nie osiągniemy. Sposób obliczenia takiej minimalnej długości kodu jest podany na początku artykułu. Należy mieć uwagę na to, że każda operacja ogranicznia maksymalnej długości kodu zmniejsza kompresję. Strata jest tym większa, im bardziej skróciliśmy najdłuższe kody.

Tryb statyczny i dynamiczny.

Tryb statyczny polega na tym, że cały strumień danych jest kodowany jednakowo, tzn. kody symboli nie zmianiają się w trakcie kompresowania. Ma on dużą wadę - nie można zacząć kompresji dopóki nie otrzymamy całej porcji danych do zakodowania. Z tego względu nie nadaje się do kompresji np. danych wysyłanych za pośrednictwem sieci. Do takich celów jest przeznaczony tryb dynamiczny (adaptatywny). W tym trybie nie ma konieczności otrzymywania od razu całej porcji danych. Statystyki częstotliwości, a dzięki nim kody symboli, są tworzone i aktualizowane na bieżąco. Nie trzeba także przechowywać nigdzie kodów symboli. Wadą jest natomiast niska prędkość (kilkukrotnie niższa od trybu statycznego) oraz (zazwyczaj) trochę gorsza kompresja.

W większości szybkich algorytmów kompresji używa się trybu statycznego. Jest on, jak już wspomniałem, prostszy w implementacji i szybszy w działaniu. Jedyną trudnością jest zapisywanie kodów symboli.

Zapisywanie kodów symboli.

Istnieje wiele sposobów zapisywania kodów symboli. Różnią się one złożonością i efektywnością. Tutaj chodzi o to, by nagłówek zajmował jak najmniej. Nie przejmujemy się zbytnio złożonością algorytmu, gdyż zazwyczaj kodujemy nie więcej niż 256 symboli (czyli bardzo mało).

Na początek najłatwiejszy sposób, czyli zapisywanie każdego symbolu oddzielnie. Jest on najmniej efektywny - zajmuje najwięcej miejsca. Wariacji tego sposobu jest dużo, przykładowo można zapisywać każdy symbol w postaci rekordu:

Uwaga: wszytko zapisujemy jako strumień bitów, bez podziału na bajty. Dzięki temu zaoszczędzamy dużo miejsca. Dodatkowo długość kodu nie musi zajmować całego bajtu. Gdy mamy, powiedzmy, ograniczenie długości kodu do 30 bitów to na zapisanie długości kodu wystarczy pięć bitów.

Jeżeli chcemy zmniejszyć rozmiar nagłówka musimy jakoś uporządkować kody symboli. Na początek uporządkujmy kodu wzrastająco według ich długości. Tak nasz przykład wygląda przd uporządkowaniem:

. = 0011
  = 11
A = 0100
D = 00000
I = 00001
K = 00010
S = 00011
a = 10
k = 00101
l = 00100
m = 0101
o = 0110
t = 0111

A tak po uporządkowaniu:

  = 11
a = 10
. = 0011
A = 0100
m = 0101
o = 0110
t = 0111
D = 00000
I = 00001
K = 00010
S = 00011
k = 00101
l = 00100

Teraz zobaczymy jak można to wykorzystać. Zamiast zapisywać z każdym symbolem długość jego kodu, możemy utworzyć zmienną, która będzie przechowywała aktualną długość kodu. Nazwijmy tą zmienną n. Na początku będzie miała wartość jeden. Teraz rekord opisujący symbol wygląda tak:

Dodatkowo wprowadzimy flagę (czyli bit) kontrolujący dekodowanie. Oto jak teraz wygląda proces dekodowania kodów symboli:

A proces kodowania wygląda tak:

Zauważmy, że stopień kompresji nie zależy bezpośrednio od kodów, ale od ich długości. Dlatego nie ma większego sensu zapisywanie ich w nagłówku. Zamiast tego możemy posłużyć się innym schematem. W pliku zapisujemy kolejno:

To są przykładowe kody:

  = 11
a = 10
. = 0011
A = 0100
m = 0101
o = 0110
t = 0111
D = 00000
I = 00001
K = 00010
S = 00011
k = 00101
l = 00100

Dla tego przykładu zawartość nagłówka będzie wyglądała tak:

5,
0,2,0,5,6,
,
 ,a,
,
.,A,m,o,t,
D,I,K,S,k,l,

Oczywiście w pliku nie powinno być żadnych odstępów. Widzimy, że taki zapis znacznie zmniejsza to rozmiar nagłówka. Jako ciekwostkę podam, że w taki sposób zapisuje się kody symboli w plikach JPEG i nosi on nazwę zapisu regularnego. Kod początkowo będzie zawierał wartość binarną zero. Dodatkowo przyjmijmy, że poziom to zbiór wszystkich symboli, które mają kody o długości aktualnego kodu. Proces odtwarzania kodów przebiega następująco:

Dla naszego przykładu odtworzone kody będą miały następujący wygląd:

  = 00
a = 01
. = 1000
A = 1001
m = 1010
o = 1011
t = 1100
D = 11010
I = 11011
K = 11100
S = 11101
k = 11110
l = 11111

Procedura tworzenia kodów musi być wykonana zarówno w koderze, jak i dekoderze. Zawsze musi dawać takie same wyniki. W moim programie do kompresji omawianym sposobem, nagłówki są zapisywane pokazanym wcześniej sposobem. Zamiast odczytywania kodów z drzewa binarnego, odczytuję tylko długości kodów symboli, a potem symbole te tworzę za pomocą powyższego algorytmu.

Taka organizacja kodów znacznie ułatwia i przyspiesza ich dekodowanie. Wystarczy zauważyć, że wartości kodów na danym poziomie są nie większe od wartości kodu ostaniego symbolu na tym poziomie. Dekodowanie symbolu ze zakodowanego strumienia bitów można więc przedstawić następująco:

To jest jeden z najszybszych sposobów dekodowania. Zaimplementowałem go w swoim programie i osiąga on prędkość nawet czterech megabajtów skompresowanych danych (strumienia bitów) na sekundę na moim starym celeronie 337.5 mhz. Prędkość dekodowania zależy przede wszystkim od stopnia kompresji, gdyż krótsze kody dekodowane są szybciej.

Uwagi.

Przedstawione tutaj sposoby można ulepszyć. Wymyśliłem jeszcze lepszy sposób zapisu nagłówka, stosując dodatkową kompresję. Pozwala ona na zmniejszenie rozmiaru nagłówka o średnio 40 do 60 procent. Wykorzystuje ona dwa fakty:

Napisałem już prowizoryczny kod dokonujący kompresji i dekompresji nagłówka. Będzie on w przyszłości zaimplementowany w kompresorze lzt0 i może w kompresorze huffmana.