Kurs Assemblera cz. 7
- TeBe / MadTeam
Metody kompresji danych
Informacje tu przedstawione zostały zebrane z różnych plików RFC, opisów formatów walających się po sieci, własnych przemyśleń i doświadczeń zdobytych w czasie pisania kompresora plików RIP. Kompresor jest na PC, depaker na Atari, żeby była jasność. Nie namawiam Was żebście napisali np. RAR-a na Atari :)
Może przydadzą się te informacje jakiemuś ambitnemu człowiekowi :), który potrafi coś zrobić ze zdobytą wiedzą (baloisa należałoby wykluczyć).
1. Huffman coding (Squezzing).
Kompresja ta polega na zaprezentowaniu najczęściej występujacych danych na mniejszej liczbie bitów. Znajduje najoptymalniejszą kombinację bitów, jest lepszy od kodowania Shannon Fano. Stosowanie tego algorytmu ma sens tylko wtedy gdy częstotliwość występowania elementów jest w stosunku 1/2. Gdy w ciągu będzie 256 różnych elementów to najdłuższy kod Huffmana bedzie miał 16 bitów.
Zakładamy, że na początku wszystkie 256 elementów występują po 1 razie. Kody tworzymy dla wszystkich 256 elementów. Czytamy cały ciąg danych, zliczając poszczególne elementy. Następnie wybieramy 128 (połowa występujących elementów) największych wartości i sumujemy. Jeśli stosunek tej sumy do liczby wszystkich elementów jest większy od 0.5 to kompresja sie opłaca.
Liczbę bitów potrzebnych do zakodowania danej wartości można obliczyć ze wzoru:
L=-log2(P(A)) gdzie P(A) - częstotliwość wystąpienia wartości A
L - szukana liczba bitów
1a. Huffman Codes. Obliczanie kodów Huffmana
- Liczymy elementy danego ciągu.
- Bierzemy dwie najmniejsze wartości reprezentujące liczbę elementów. Pierwsza wartość będzie binarnym 0, druga binarnym 1. Zaznaczamy wybrane elementy, by później traktować je jako jedność (suma).
- Powtarzamy pkt.1 dopóki nie połączymy wszystkich par.
- Rewersujemy kombinacje bitów.
np. A A A A B C A D B E C B
A-5, B-3, C-2, D-1, E-1
| | | Reverse | 0 / \ 1
--------+---+------+---------+ / \
3 | A | 0 | 0 | / 0 / \ 1
3 2 | B | 01 | 10 | / / \
3 2 1 | C | 011 | 110 | / / 0 / \ 1
3 2 1 0| D | 0111 | 1110 | / / / \
3 2 1 0| E | 1111 | 1111 | / / / 0 / \ 1
--------+---+------+---------+ A B C D E
12 7 4 2|
Do pliku wyjściowego należy przesłać informację o rozkładzie elementów, co spowoduje zmniejszenie stopnia kompresji. Sprytne upakowanie tej informacji nie wpłynie znacznie na końcowy wynik kompresji np.
1) 256 kodów Huffmana i 256 wartości z zakresu 0-15 (4 bity) określajacych długość kodów+1 np. 0000 0 0001 10 0010 110 0011 1110 0011 1111 0000 0 oznacza kod o długości 0000+1 bitów, w naszym w/w przykładzie tym bitem jest 0 0001 10 oznacza kod o długości 0001+1 bitów = 2 bity, w naszym przykładzie to 10 ... 0011 1110 oznacza kod o długości 0011+1 bitów = 4, w naszym przykładzie 1110 2) 256 kodów Huffmana i bajty w których bity 4-7 oznaczają liczbę kodów+1, a bity 0-3 długość kodów+1 np. 00 01 12 13 a6 00 czyli 1 kod o długości 1 bita 12 czyli 2 kody o długości 3 bitów a6 czyli 11 kodów o długości 7 bitów
Można spakować kody obiema w/w metodami i wybrać najlepszą zaznaczając to w pliku wyjściowym.
1b. Dekompresja kodów Huffmana
BitLenght = 0
loop
read(bit)
Byte(BitLenght) = bit : BitLenght=BitLenght + 1
Value = 257
Count = 0
loop while ( Value = 257 )
if (LenghtCode(Count) = BitLenght) and (Code(Count) = Byte(0..7)) then
Value = Count
endif
Count = Count + 1
end loop
end loop
Aby zdekodowac kod, musimy go czytac bit po bicie i porownywac z tablicami gotowych kodow i ich dlugosciami. Przy tym sposobie dekompresja bedzie szybsza jesli tablice beda posortowane wg. rosnacych wartosci 'dlugosci kodow'. Najkrotsze kody zostana zdekodowane najszybciej.
1c. Dynamic Huffman Codes.
Ta metoda eliminuje konieczność przeczytania wszystkich elementów i przesłania kodów do wyjścia, jednak proces dekompresji jest wolniejszy w porównaniu do klasycznego sposobu.
Na początku liczbę poszczególnych 256 elementów ustawiamy na 1. Czytamy element i odpowiednio modyfikujemy drzewo binarne.
Dekompresja w tym przypadku przebiega podobnie jak kompresja.
2. Shannon-Fano coding.
Zasada tego kodowania jest taka sama jak Huffmana. Zastąpić symbole krótszymi symbolami, tyle że tutaj podajemy jakiej długości mają być te kody. Zostają stworzone kody o zadanej długości.
1) Obliczamy na ilu bitach reprezentowany jest dany symbol (Bit Lenght).
2) Sortujemy wartości Bit Lenght (ciąg rosnący).
3) Generujemy kody:
Code = 0
CodeIncrement = 0
LastBitLength = 0
i = numer kodu Shannon-Fano - 1
loop while (i >= 0)
Code = Code + CodeIncrement
if BitLength(i) <> LastBitLength then
LastBitLength=BitLength(i)
CodeIncrement = 1 shifted left (16 - LastBitLength)
endif
ShannonCode(i) = Code
i = i - 1
end loop
4) Dokonujemy rewersji bitów poszczególnych kodów.
5) Przywracamy stare uporządkowanie wartości Bit Lenght.
np. Bit Lenght = 3, 3, 3, 3, 3, 2, 4, 4 (kody od 0-7)
Reversed Order Original
Val Sorted Constructed Code Value Restored Length
--- ------ ----------------- -------- -------- ------
0: 2 1100000000000000 11 101 3
1: 3 1010000000000000 101 001 3
2: 3 1000000000000000 001 110 3
3: 3 0110000000000000 110 010 3
4: 3 0100000000000000 010 100 3
5: 3 0010000000000000 100 11 2
6: 4 0001000000000000 1000 1000 4
7: 4 0000000000000000 0000 0000 4
3. LZW78 (Lempel-Ziv-Welch).
Algorytm ten stosowany jest w m.in. w kompresji GIF'a. Jest to kompresja używająca słownika. Kody generowane są z zakresu od 9-13 bitów, w przypadku GIF'a 9-12.
Symbole reprezentowane są przez wartości z zakresu 0-255, kody słownika 256-... Jeśli zabraknie bitów do zaprezentowania kodu słownika liczba bitów jest zwiększana o 1, aż do pewnej ustalonej granicy (12 lub 13), wtedy generowany jest kod 256 - Clear Dictionary (czyść słownik), kod 257 - End Data (Koniec).
np. A B C C B D D D C A B EOF Input | Output | Dictionary -----------+---------+-------------- AB | A | 258=(A,B) BC | B | 259=(B,C) CC | C | 260=(C,C) CB | C | 261=(C,B) BD | B | 262=(B,D) DD | D | 263=(D,D) DD 263,C | 263 | 264=(263,C) CA | C | 265=(C,A) AB 258,EOF | 258 |
4. Arithmetic coding.
Metoda ta opiera się podobnie jak Huffman czy ShanonFano o rozkład prawdopodobieństwa. Z ciągu wejściowego pobieramy ciąg, w którym występują max 2 symbole. Dla tych 2 symboli szukamy 1-nej kombinacji bitów X (ciąg 2 symboli zakodujemy jedną kombinacją bitów), którą znajdujemy dzieląc przedział <0,1) na 2 części (górną lub dolną), równe częstotliwości występowania tych elementów. Przedział zawężamy od góry lub od dołu tak długo, aż nie przeczytamy wszystkich elementów.
4a. Ograniczanie przedziału.
np. (27/64,36/64) - ograniczyć o 3/4 od góry
27/64 36/64
+----------+-----+
3/4 1/4
czyli to jest 3/4 obszaru (36/64 - 27/64) = 9/64 * 3/4 = 27/256, ten wynik dodajemy do dolnej granicy (lewej), czyli (27/64 + 27/256) = 135/256 nowy obszar to (27/64,135/256) np. (0,9/16) - ograniczyć 1/4 od dołu
0 9/16
+----------+-----+
3/4 1/4
podobnie jak poprzednio jest to 1/4 obszaru (0 - 9/16) = 9/16 * 1/4 = 9/64, ten wynik odejmujemy od górnej granicy (prawej), czyli (9/16 - 9/64) = 27/64 nowy obszar to (27/64,9/16)
4b. Reprezentacja binarna ułamka.
Mnożymy licznik *2, jeżeli jest większy od mianownika to zapisujemy binarne 1 i odejmujemy od licznika mianownik, w przeciwnym wypadku zapisujemy binarne 0 (licznik < mianownika). Kończymy gdy licznik = mianownik.
np.
27/64 | 135/256 |
54/64 | 0 135/256*2=270/256 | 1
108/64| 1 14/256*2=28/256 | 0
44/64*2=88/64 | 1 56/256 | 0
24/64*2=48/64 | 0 112/256 | 0
96/64 | 1 224/256 | 0
32/64*2=64/64 | 1 224/256*2=448/256 | 1
192/256*2=384/256 | 1
128/256*2=256/256 | 1
27/64 = 0.011011 135/256 = 0.10000111
4c. Przykład kompresji.
np. AABACAD wybieramy AABA zliczamy elementy A-3 B-1, razem 4, czyli A=3/4, B=1/4 - na początku nasza szukana wartość X jest w przedziale <0,1), przedział ten dzielimy na 2 części 3/4 i 1/4 (musimy z góry przyjąć jak będziemy dzielić nasz przedział, zawsze tak samo).
0<= X <1
0 1
+----------+-----+
3/4 1/4
bierzemy pierwszy symbol - A, ograniczamy przedział od góry do 3/4, nasz nowy przedzial to: 0<= X <3/4 i dzielimy go na 2 części 3/4 i 1/4, następny symbol to znowu - A, przedział <0,3/4) ograniczamy o 3/4, czyli 9/16 (((3/4 - 0) * 3/4) + 0) = 9/16 ), nowy przedział to <0,9/16), następny symbol to B - tym razem wybieramy dolną część przedziału <0,9/16), czyli 1/4, nowy przedział to <27/64,9/16), ostatni symbol to A - przedział <27/64,9/16) ograniczamy o 3/4 od góry, nasz nowy, ostateczny przedział to (27/64,135/256).
Ułamki musimy teraz zaprezentować binarnie, czyli
27/64 <= X < 135/256
0.011011 <= X < 0.10000111
teraz wybieramy z powyzszego przedzialu liczbe, reprezentowana przez najmniejsza liczbe bitow, czyli 0.1 (0.01 ma wiecej bitow), odrzucamy 0. i otrzymujemy 1, a wiec 4 elementy AABA zakodujemy 1 bitem = 1.
4d. Dekompresja.
W spakowanym ciągu musi znaleźć się informacja o rozkładzie prawdopodobieństwa naszych elementów, czyli A=3/4, B=1/4. Bierzemy bit, jest nim 1, dokładamy 0. czyli 0.1, jest to binarne 1/2. 1/2 zawiera się w 3/4 pierwszego przedziału czyli szukanym znakiem jest A, obcinamy teraz przedział do 3/4 - <0,3/4). 1/2 ponownie mieści się w dolnej części tego przedziału czyli nasz znak to A. Przedział jeszcze raz obcinamy o 3/4 - <0,9/16), tym razem 1/2 mieści się w górnej części przedziału, dekodujemy więc B itd.
5. RLE (Run Lenght Encode).
Najprostsza z metod kompresji, aż dziw bierze że dopiero w tym miejscu się ona pojawia :) Sprawdza się w przypadku danych które nader często się powtarzają i występują "jeden za drugim".
np.
AAAABBBCDDDDDDD
po kompresji RLE dane powinny wyglądać tak:
4A 3B 1C 7D
Czyli w skrócie, w ciągu wynikowym znajdą się pary: "liczba elementów" x "element"
6. LZSS (Lempel-Ziv-Storer-Szymanski).
Jeden z lepszych sposobów kompresji, jego różne kombinacje znalazły zastosowanie w Zip-ie jako deflating, lub w okrojonej formie w Cruncherach na 8-bitowce, albo w RIP-ie :). Są różne kombinacje tej metody, ale założenia są takie same.
W ciągu wejściowym szukamy identycznych fraz. Po znalezieniu identycznej frazy, w ciągu wynikowym zapisujemy jej ofset i długośc, jeśli nie znaleziono powtarzającej się frazy wysyłamy jej fragment do pliku wynikowego. Np:
alamakota,akotmaale
- Zakładamy, że szukamy 3 elementowych fraz. Pierwsza 3 elementowa fraza to "ala", przeszukujemy pozostały ciąg od znaku 4 do ostatniego, brak takiej samej frazy. Wysyłamy do pliku wynikowego 1 znak "a" (UNPACK).
- Teraz bierzemy fraze "lam", od znaku 2 do 4, przeszukujemy od 5 do ostatniego, brak identycznej frazy. Wysyłamy do pliku wynikowego 1 znak "l".
- Bierzemy fraze "ama", od znaku 3 do 5, przeszukujemy od 6 do ostatniego, brak powtarzających się fraz. Zapisujemy "a".
- Bierzemy fraze "mak", od znaku 4 do 6, przeszukujemy od 7 do ostatniego, brak takich samych fraz. Zapisujemy "m".
- Bierzemy fraze "ako", od znaku 5 do 7, przeszukujemy od 8 do ostatniego, znajdujemy na pozycji 11 fraze "ako". Teraz sprawdzamy maksymalną jej długość, tak długo dopóki znaki są identyczne z frazą porównywaną. Okazuje się, że nasza najdłuższa fraza to "akot". Zamiast 4 znaków zapiszemy OFSET, czyli odległość do frazy z którą porównywaliśmy 11-5=6, oraz długośc (MATCH_LEN) frazy, czyli 4.
- Omijamy znalezioną frazę, bierzemy nową od znaku 10 do 12, przeszukujemy od 13 do ostatniego. Itd.....
Nasz przykładowy ciąg był krótki, normalnie mamy do czynienia z dłuższymi ciągami, przekraczającymi zakres 1 bajtu 0..255, a pozatym ciągle mamy wartości 8bitowe: OFSET, MATCH_LEN, UNPACK. Te 3 rodzaje danych powinniśmy teraz zacząć pakować Huffmanem, albo inną probalistyczną metodą, wtedy dopiero uzyskamy zadowalającą kompresję.
W kompresji RIP-a ofset jest z zakresu 0..255, minimalna długość frazy =3. Gdyby Fox wcześniej udostępnił swój DEFLATE.EXE, nie trzebaby było kombinować :)
7. Kodowanie stratne. (by Rocky)
Obraz może być kodowany kolumnami (z góry na dół) lub wierszami (z lewej do prawej). Zapisywana jest różnica pomiędzy poszczególnymi wartościami, za pomocą bitów.
Jeśli poprzednia wartość jest mniejsza od aktualnej zapiszemy jako 0, w przeciwnym wypadku gdy większa lub równa jako 1. Wartość 8 bitową zapiszemy w ten sposób za pomocą 1 bitu.
W przypadku gfx ATARI kodowanie to można zastosować w trybie 16 odcieni szarości 9 Basica. Przeglądamy gfx pionowymi kolumnami i zapisujemy różnicę np. na 1 bicie. 4 bity (pixel) zapiszemy na 1 bicie. Obraz zostanie rozmazany, straci na ostrości. W przypadku animacji nie powinno być to tak mocno zauważalne.
Przykładem zastosowania tego typu kompresji jest 16kb intro "Vasco", w którym jest sporo grafik udających HIP-a.
8. Zastosowanie. czyli luźne myśli i nie tylko :)
HF - Huffman
SF - Shannon-Fano
AR - Arithmetic coding
Power Packer (Amiga) pakuje długości ciągów za pomoca 2 bitów, i w zależności od potrzeb zwiększa tą liczbę np.
0 - 00 3 - 1100 6 - 111100 1 - 01 4 - 1101 7 - 111101 2 - 10 5 - 1110 8 - 111110
Gdy wystąpi kombinacja 11 tzn. że należy czytać dalej kod, długość ciągu jest zwiększana, powtarzamy operacje dopóki nie wystąpi kombinacja bitów różna od 11.
W programie kompresującym trzeba zastosować obie metody HF i SF. HF służyć będzie do obliczenia długości kodów, a SF do ich bitowej reprezentacji. Jeśli nie zastosujemy SF musielibyśmy przesłać do pliku wynikowego całe drzewo HF (ok. 576*3 byte) zamiast 288 byte (1byte = 2nible, 288*2=576 byte), które są długościami kodów (1..15, 0 - brak kodu).
Natomiast AR możnaby zastosować zamiast HF i SF. Ze względu jednak na skomplikowanie tej metody i dużą liczbę obliczeń nie jest ona tak popularna.
Dekompresja w przypadku gdy czytamy bit po bicie i porównujemy czy przeczytany kod jest już naszym szukanym, trwa stosunkowo długo. Proces dekompresji powinien w jak najmniejszej liczbie kroków znaleźć szukany kod. Pewnym rozwiązaniem jest posortowanie wartości, ale najlepszym wydaje się zastosowanie drzewa. Drzewo pozwoli, że w każdym kroku jednoznacznie wyznaczymy właściwą drogę do szukanego kodu.
Stosowanie tylko kompresji HF, SF lub AR nie jest zbyt opłacalne, stosuje się je tylko na końcu kompresji słownikowej. Pakuje się tymi 3-ema metodami kody słownika i pozostałe dane. Tak działają pakery ZIP, RAR, LHA itp. Niektóre z pakerów na samym początku starają się ocenić kompresowalność danych, jeśli żadna z kompresji nie daje pozytywnych rezultatów paker zapisuje dane jako STORE (bez kompresji).
8a. Reprezentacja drzewa binarnego w pamięci komputera.
Drzewo to tablica n-elementowa, w której znajdują się wartości szukane 0..255 (lub np. A..Z) i wartości 256..N, które oznaczają numer pary w drzewie.
0 1
256| 257|259| A 010
257| F |258| B 011
258| A | B | C 100
259| 260|261| D 101
260| C | D | E 110
261| E |262| F 00
262| G | H | G 1110
H 1111
Tworzenie drzewa:
- zliczamy częstotliwości wszystkich elementów
- bierzemy 2 najmniejsze elementy (kolejność znalezionych elementów gra rolę)
- 1-wszy z elementów zachowujemy i zaznaczamy jako nową parę identyfikatorem
>255, zaznaczamy nową wartość tej pary (suma)
2-ugi element zaznaczamy jako usunięty, nie będziemy go brali pod uwagę
przy następnym przeszukiwaniu
- wstawiamy te 2 znalezione elementy do drzewa jako nową gałąź
np.
Frq 0 1
A-1 0 / \ 1 256| A | C | <- najniższa gałąź w drzewie
B-2 / \ 257| 256| F |
C-1 / \ / \ 258| B |257|
D-3 / / \ D E 259| D | E |
E-3 / / \ \ 260| 258|259| <- wierzchołek drzewa
F-1 B A C F
Dekompresja danych zapisanych na drzewie:
- zaczynamy od znalezienia szukanego elementu X najniżej w drzewie
- szukamy wyżej odwołania do gałęzi w której wystąpił nasz element
powtarzamy obydwa pkt. aż do wierzchołka
- otrzymane kombinacje bitów rewersujemy
W naszym w/w przykładzie mamy drzewko z wierzchołkami od 256..260, teraz odczytamy przy jego pomocy jak wygląda binarna reprezentacja elementu A.
0 1
260| 258|259| <- wierzchołek drzewa
259| D | E |
258| B |257|
257| 256| F |
256| A | C | <- najniższa gałąź w drzewie
Chcemy zdekodować A. Znajdujemy ten element najniżej w drzewie, jest na pozycji (wierzchołku) 256, po lewej stronie czyli binarne 0. Odwołanie do pozycji 256 występuje na pozycji 257 i znajduje się po lewej stronie, czyli znowu 0. Odwołanie do 257 znajduje się pod 258 i jest po prawej stronie, czyli binarne 1. Odwołanie do 258 jest na pozycji 260, po lewej stronie (binarne 0) i jest to wierzchołek, więc kończymy nasze poszukiwania. Otrzymaliśmy 0010, rewersujemy i mamy 0100 i to jest binarny kod reprezentujący A, sprawdzcie na drzewku.
Ok, to był przykład odczytania z drzewa reprezentowanego przez tablice, kodu reprezentującego konkretny element, ale w czasie dekompresji nie mamy podanej informacji jaki element będziemy właśnie rozpakowywać. Dekompresując czytamy bit po bicie i na tej podstawie dokonujemy wyboru jak poruszać się po drzewie, aż dojdziemy do elementu, który szukamy.
0 1
260| 258|259| <- wierzchołek drzewa
259| D | E |
258| B |257|
257| 256| F |
256| A | C | <- najniższa gałąź w drzewie
Np. 0100. Czytamy ciag bitów i dekodujemy. Bit 0 oznacza że mamy wybrać element po lewej stronie. Po lewej stronie w wierzchołku występuje 258. A więc skaczemy do wierzchołka 258, mamy tam dwie wartości B i 257, którą wybrać? Odczytujemy więc następny bit i on nam odpowie co mamy zrobić. Następny bit to 1, więc wybieramy z prawej strony element 257. Skaczemy pod 257, tam mamy 256 i F, odczytujemy bit, jest nim 0, wiec wybieramy z lewej 256. Skaczemy pod 256 tam mamy A i C, odczytujemy bit, jest nim 0, więc naszym elementem zdekodowanym jest A.
8b. Budowa drzewa z kodów binarnych.
- bierzemy bit i wstawiamy na 1-wsze wolne miejsce w drzewie (w zależności od
wartości np. 0-lewy 1-prawy liść) wartość określającą nastepną wolną gałąź
- kończymy wstawiając wartość 0..255 (A..Z)
np 1.
zakodowane
drzewko informacje A..H
------- ---------------
0 1
256| 257|259| A 010
257| F |258| B 011
258| A | B | C 100
259| 260|261| D 101
260| C | D | E 110
261| E |262| F 00
262| G | H | G 1110
H 1111
np 2.
0 1
256| A |257| A 0
257| B |258| B 10
258| 259|260| C 1100
259| C | F | D 11110
260| 262|261| E 11100
261| D | | F 1101
262| E | G | G 11101
P.S. balois by tego nie wiedział ;P
