Lempel-Ziv 77 (LZ77)

</p>Nie jest to algorytm bardzo efektywny czy szybki, ale jest bardzo prosty w implementacji.</p>

Algorytm LZ77 należy do tzw. algorytmów kompresji dynamicznej. Plik jest analizowany i kompresowany w trakcie napływania kolejnych bajtów.

Schemat algorytmu jest bardzo prosty:

1. Znajdujemy się w jakimś miejscu pliku. (na rysunku bajt nr n)
2. Odczytujemy n-ty znak.
3. Wyszukujemy taki sam n-ty znak w 256 poprzedzających bajtach.
4. Jeżeli go nie znajdziemy to zapisujemy ten znak w postaci:

nr bitu	wartość	znaczenie
1	0	0 oznacza nie znalezienie takiego samego znaku w poprzednich 256 bajtach
2-9	kod znaku	Jeżeli n-ty znak to 'A' to wpisujemy wartość Ord('A');

5. Jeżeli znajdziemy znak, to: 5a. Sprawdzamy czy kolejny odczytany znak pasuje do kolejnego znaku znalezionego w słowniku (czyli poprzedzających 256 bajtach) 5b. Jeżeli tak, to zwiększamy wartość licznika. I tak aż znajdziemy 9 pasujących znaków, lub więcej kolejnych znaków nie będzie pasować. Wówczas zapisujemy znaki w postaci:

nr bitu	wartość	znaczenie
1	1	1 oznacza, że w poprzedzających ten znak 256 bajtach istnieje taki sam znak jak ten na pozycji n
2-4	Licznik-2	Licznik - liczba znaków znajdujących się zarówno na pozycjach n, n+1, n+2 ... n+8, jak i w poprzedzających znak n 256 bajtach. Maksymalnie może być 9 takich znaków. Zapisuje się tą liczbę pomniejszoną o 2, bo dla mniej niż 2 znaków nie opłaca się stosować kompresji i należy użyć wcześniej podanego sposobu, czyli tak, jakby nie znaleziono znaku.
5-12	Pozycja znaku	Pozycja znaku w poprzedzających 256 bajtach. Jeżeli znak taki sam jak n znajduje się np. 50 znaków wcześniej to wpisywana jest wartość 256-50=206. Jeżeli następny znak po n, czyli n+1 ma swój odpowiednik w znaku 207 to licznik jest zwiększany o 1 itd. aż nie znajdzie się znak, lub licznik osiągnie wartość 9.

Dekompresja jest banalnie prosta: 1. Odczytujemy po kolei bity. 2. Jeżeli odczytany bit ma wartość 0 to kolejne 8 bitów jest wartością jaką trzeba zapisać (kodem znaku) 3. Jeżeli odczytany bit ma wartość 1 to kolejne 3 bity dają liczbę znaków do zapisania zwiększone o 2 (np. te 3 bity to 101b czyli 5d. Mamy więc do zapisania 5+2=7 znaków), a następne 8 wskazuje skąd należy zacząć je odczytywać. (np. te 8 bitów to wartość 206, wobec tego zaczynamy odczytywać znaki z pozycji n-(256-206) = n-50. Z pozycji o 50 wcześniejszej niż miejsce w pliku, gdzie się aktualnie znajdujemy i zapisujemy w naszym przykładzie kolejne 7 znaków)

W ten sposób jeżeli nie znajdziemy w poprzednich 256 bajtach szukanego znaku możemy zwiększyć rozmiar pliku o 1/8. Jeżeli zaś znajdziemy 9 znaków to możemy uzyskać kompresję 6-krotną!!! (9/1,5=6)

Imploding.zip ( 3 kB ) - przykład do artykułu...

Jakub "Dryobates" Stolarski