Algorytmy » Kompresja

Lempel-Ziv 77 (LZ77)

  • 2007-03-24 23:57
  • 5 komentarzy
  • 1860 odsłon
  • Oceń ten tekst jako pierwszy
</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.


imp.gif

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 bituwartośćznaczenie
100 oznacza nie znalezienie takiego samego znaku w poprzednich 256 bajtach
2-9kod znakuJeż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 bituwartośćznaczenie
111 oznacza, że w poprzedzających ten znak 256 bajtach istnieje taki sam znak jak ten na pozycji n
2-4Licznik-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-12Pozycja 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

5 komentarzy

wegi 2013-02-11 19:27

Bardzo dobry opis Dryobatesa - na nim się uczyłem. Praktycznie można założyć, że są dwa istotne etapy takiej kompresji. Pierwszy to scanning drugi to kodowanie. O ile scanner daje bliźniacze wyniki w każdym przypadku, istnieje wiele opcji ulepszania wyników. Pierwsza rzecz, to jak ustawić scanner druga niesłychanie istotna to sposób zakodowania skompresowanych danych. Do zakodowania używano wielu epickich wręcz sztuczek. Scanner podaje wyniki - znaleziono sekwencję o długości x bajtów i offsecie wstacznym y. Koder natomiast ma to "zbić" w taki sposóby aby dało się to rozpakować bez utraty bitu i z jak największym uzyskiem. Koder może np. zajmować się "trippletami" danych uzyskanych od scannera tzn. 1 - crunchbytes 2. offset 3 rawdata bytes. Można założyć taką kolejność kodowania i dekodowania, następnie parować podobieństwa trippletów do statycznej tablicy. Kodowanie przeprowadziłem do dwóch "przeplecionych" buforów - jeden z danymi drugi z bitowym infostreamem opisującym rozkazy dla decrunchera. Bitowy "infostream" dla oszczędności zakodowanych danych zawiera proste informacje : np. bit

1  =0/1 crunchdata/rawdata

jeżeli 1 - kopiowanie danych to
4 bity - ich warość określa ilość następnych bitów do pobrania będących wielkością ilości bajtów do skopiowania
x bitów określona poprzednimi 4ma bitami - to właśnie "many raw data value"

jeżeli 0 to
3 bity o ilości danych do zdecrunchowania (daje możliwość info o sekwencji 1 do 255 bajtów)
x bitów określona poprzednimi trzema bitami - to ilość bajtów do decrunchingu
4 bity - info o ilości napływających bitów offsetu
x bitów określona poprzednimi 4ma bitami (daje zakres do 65535 bajtów wstecz offsetu wyszukiwania)

można założyć, że nieopłacalne jest kodowanie jednobajtowych sekwencji i np. znalezienie infa o scrunchowanej jednobajtowej sekwencji oznacza EOF

Nieograniczone możliwości zależne tylko od inwencji programisty

Dryobates 2002-10-13 22:56

Obraz wart tysiąca słów... Teraz lepiej?

Adam Boduch 2002-10-12 10:31

Masz racje. Jak dodawałem do bazy to Dryobates nie był jeszcze zarejestrowany. Teraz już jest więc mogę zmienić autora... :) Sorki, Dyrobates...

Vrok 2002-10-11 20:28

Autorem jest Dryobates, a pisze ze Adam Boduch:)))

Poza tym jest to wytlumaczone troche mgliscie...