LZ77

Z Wikipedii

Lempel-Ziv 77, skracane zwykle do LZ77 (algorytm LZ77) - metoda strumieniowej bezstratnej kompresji słownikowej.

Została opracowana w 1977 przez Abrahama Lempela i Jacoba Ziv i opisana w artykule "A universal algorithm for sequential data compression" opublikowanym w IEEE Transactions on Information Theory (str. 8-19).

Na LZ77 opiera się m.in. algorytm deflate, używany jest również w programach zip, gzip, ARJ, RAR, PKZIP, a także w formacie PNG. Algorytm LZ77 jest wolny od wszelkich patentów co w dużej mierze przyczyniło się do jego popularności i szerokiego rozpowszechnienia.

Spis treści

1 Zasada działania
2 Algorytm kompresji
- 2.1 Przykładowy krok algorytmu
3 Algorytm dekompresji
4 Przykład kompresji
5 Przykład dekompresji
6 Linki zewnętrzne
7 Bibliografia
8 Zobacz też

[edytuj] Zasada działania

Obrazowo patrząc, metoda LZ77 wykorzystuje fakt, iż poszczególne słowa, albo przynajmniej ich części powtarzają się w danym tekście: zapamiętywana jest w słowniku pewna liczba ostatnio kodowanych danych - przeciętnie kilka, kilkadziesiąt kilobajtów - i jeśli jakiś ciąg powtórzy się, to zostanie zastąpiony przez liczby określające jego pozycję w słowniku oraz długość ciągu; do zapamiętania tych dwóch liczb trzeba przeznaczyć zazwyczaj o wiele mniej bitów, niż do zapamiętania zastępowanego ciągu.

Metoda LZ77 zakłada, że ciągi powtarzają się w miarę często, tzn. na tyle często, żeby wcześniejsze wystąpienia można było zlokalizować w słowniku - ciągi powtarzające się zbyt rzadko nie są brane pod uwagę. Wady tej pozbawiona jest metoda LZ78 (również opracowana przez autorów LZ77), w której - przynajmniej teoretycznie - słownik rozszerza się w nieskończoność.

Bardzo dużą zaletą kodowania LZ77 (a także innych metod słownikowych z rodziny LZ, tj. LZSS, LZ78, LZW itp.) jest to, że słownika nie trzeba zapamiętywać i przesyłać wraz z komunikatem - zawartość słownika będzie na bieżąco odtwarzana przez dekoder.

Algorytm kompresji jest bardziej złożony i trudniejszy w realizacji, niż algorytm dekompresji. W metodzie LZ77 można - regulując parametry kodera (rozmiar słownika i bufora kodowania) - wpływać na prędkość kompresji oraz zapotrzebowania pamięciowe.

[edytuj] Algorytm kompresji

Metoda LZ77 korzysta z bufora (okna), które logicznie podzielone jest na dwie części:

bufor słownikowy (słownik), przechowujący $k$ ostatnio przetwarzanych symboli (sufiks);
bufor wejściowy (lub bufor kodowania), przechowujący $n$ symboli do zakodowania.

Bufor słownikowy obejmuje indeksy $0\ldots k-1$ , bufor wejściowy $k\ldots k+n-1$ .

Rozmiary $n$ i $k$ mogą być dowolne, w praktyce dobiera się je tak, aby były całkowitą potęgą dwójki, dzięki czemu w pełni wykorzystywane są słowa bitowe przeznaczone do ich zapamiętania. Rozmiar bufora słownikowego wynosi w praktyce kilka-kilkadziesiąt kilobajtów, bufor kodowania jest dużo mniejszy. Na przykład w programie gzip słownik ma 32kB, bufor kodowania natomiast 258 bajtów.

Algorytm przebiega następująco:

Bufor słownikowy jest wypełniany pierwszym symbolem wejściowym i ten symbol jest zapisywany na wyjście.
Do bufora wejściowego wstawiane jest $n$ pierwszych symboli wejściowych.
Dopóki w buforze wejściowym są jakieś dane:
1. W obrębie bufora słownikowego wyszukiwany jest najdłuższy podciąg równy początkowi bufora wejściowego (najdłuższy prefiks bufora kodowania). Wynikiem wyszukiwania jest indeks $P \in [0\ldots k-1]$ początku wyszukanego podciągu oraz jego długość $C$ , ograniczona z góry przez $n - 1$ . Część podciągu może być wspólna z buforem wejściowym!
  Jeśli podciągu nie uda się znaleźć, to $P$ może mieć dowolną wartość, natomiast $C = 0$ .
2. Na wyjście wyprowadzana jest trójka ( $P$ , $C$ , symbol $S$ z bufora wejściowego następujący po dopasowanym podciągu).
3. Okno (bufor słownikowy + bufor wejściowy) przesuwane jest w lewo o $C + 1$ pozycji i na koniec bufora dopisywane jest tyleż kolejnych symboli wejściowych (o ile jeszcze są jakieś).

Stopień kompresji LZ77 w dużej mierze zależy od długości słownika oraz długości bufora wejściowego (bufora kodowania). Programy wykorzystujące tę metodę mają zwykle możliwość ustalania rozmiaru słownika, istnieją również programy dynamicznie zmieniające rozmiar słownika.

Prędkość kompresji natomiast jest uzależniona głównie od efektywności procedury wyszukującej najdłuższy prefiks. Używane są tutaj różne rozwiązania. Np. w programie gzip używa się tablicy haszującej adresowanej pierwszymi trzema literami z bufora kodowania. Stosowane są również zwykłe tablice, a do lokalizacji prefiksu używa się algorytmów wyszukiwania wzorca, np. algorytmu Karpa-Rabina.

Jeśli słownik jest realizowany jako tablica, to aby uniknąć fizycznego, czasochłonnego przesuwania danych w oknie (punkt 3. algorytmu), używa się buforów cyklicznych.

[edytuj] Przykładowy krok algorytmu

1. Wyszukanie najdłuższego podciągu równego początkowi bufora wejściowego (tutaj: aac).

          słownik               |  bufor wejściowy  | nieprzetworzone symbole
  0   1   2   3   4   5   6   7 | 0   1   2   3   4 |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+-----
| a | a | a | a | c | c | a | b | a | a | c | b | a | c | a | b | a | c | ...
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+-----
|                      okno                         |

2. Wynik wyszukiwania:

P = 2 (pozycja w słowniku)
C = 3 (długość podciągu)
S = b (symbol z bufora wejściowego następujący po dopasowanym podciągu)

3. Przesunięcie bufora o $C + 1$ pozycji, dopisanie do bufora wejściowego nieprzetworzonych symboli.

          słownik               |  bufor wejściowy  | nieprzetworzone symbole
  0   1   2   3   4   5   6   7 | 0   1   2   3   4 |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---------------------
| c | c | a | b | a | a | c | b | a | c | a | b | a | c | ...
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---------------------

[edytuj] Algorytm dekompresji

Dekompresja danych w metodzie LZ77 jest o wiele prostsza i szybsza niż kompresja. Do zdekodowania wymagane jest istnienie bufora (okna) o dokładnie takich samych parametrach jak przy kodowaniu - bufor podzielony jest na część słownikową obejmującą $k$ pierwszych pozycji i bufor wyjściowy zajmujący $n$ kolejnych pozycji.

Dekodowanie przebiega następująco:

Bufor słownikowy jest wypełniany początkowym symbolem
Dla wszystkich trójek (P,C,S) wykonuj:
1. Skopiuj z bufora słownikowego do bufora wyjściowego symbole z zakresu $P\ldots P+C-1$ .
2. Doklej na koniec bufora wyjściowego symbol $S$
3. Na wyjście wyprowadź $C + 1$ początkowych symboli z bufora wejściowego.
4. Przesuń zawartość bufora o $C + 1$ pozycji w lewo.

Ad 1) Jeśli przy kompresji podciąg obejmował także bufor wejściowy, to należy bufor słownikowy tymczasowo "przedłużyć" i wypełnić brakującymi symbolami. Tego specjalnego przypadku można uniknąć na etapie kompresji, biorąc pod uwagę tylko te podciągi, które w całości znajdują się w słowniku - przy dużych rozmiarach słownika i niewielkich bufora wejściowego praktycznie nie rzutuje to na stopień kompresji i jest to rozwiązanie stosowane w rzeczywistych zastosowaniach.

Podciągi takie mają strukturę xXxXx, gdzie x to pojedynczy symbol, a X ciąg znajdujący się już w buforze słownikowym. Uzupełnienie polega na cyklicznym kopiowaniu końcówki bufora słownikowego (którą obejmuje początek podciągu). Np. jeśli podciąg ma długość 8 i tylko 3 symbole bca znajdują się w słowniku, to odtworzony ciąg ma postać: bcabcabc. W praktyce nie ma potrzeby fizycznego rozszerzania słownika i kopiowania danych - wystarczy, że indeksy będą odpowiednio przeliczane.

[edytuj] Przykład kompresji

Niech długość słownika i bufora wejściowego będą równe 4, tzn. $n = k = 4$ . Do zapisu pozycji w słowniku (P) jak i długości ciągu (C) wystarczą 2 bity. Kodowany komunikat składa się z trzynastu symboli: aabbcabbcdddc.

#	słownik\|bufor wejściowy	wyjście kodera	uwagi
1	`aaaa\|aabb`	a	słownik wypełniany jest pierwszym symbolem, symbol ten jest zapisywany
2	`aaaa\|aabb`	(0,2,`b`)	w słowniku znajduje się 2-elementowy podciąg równy początkowi bufora wejściowego; bufor jest przesuwany o 3 pozycje w lewo
3	`aaab\|bcab`	(3,1,`c`)	w słowniku znajduje się 1-elementowy podciąg równy początkowi bufora wejściowego; bufor jest przesuwany o 2 pozycje w lewo
4	`abbc\|abbc`	(0,3,`c`)	w słowniku znajduje się 3-elementowy podciąg równy początkowi bufora wejściowego; bufor jest przesuwany o 4 pozycje w lewo
5	`abbc\|dddc`	(0,0,`d`)	w słowniku nie ma żadnego podciągu zaczynającego się od `d`; bufor jest przesuwany o 1 pozycję w lewo
6	`bbcd\|ddc`	(3,2,`c`)	w buforze znajduje się 2-elementowy podciąg równy początkowi bufora wejściowego: pierwszy element ciągu znajduje się w słowniku, drugi w buforze wejściowym; bufor jest przesuwany o 3 pozycje w lewo

Zakodowane zostało 13 symboli; symbole to przeważnie bajty, tak więc każdy zajmie 8 bitów, a cały komunikat 104 bity.

Dane wyjściowe kodera to: 1) początkowy symbol (8 bitów), 2) pięć trójek; każda trójka zajmuje 12 bitów (2 bity na indeks podciągu, 2 na jego długość i 8 bitów na symbol). Ostatecznie rozmiar skompresowanych danych to 68 bitów; współczynnik kompresji wynosi ok. 34%.

[edytuj] Przykład dekompresji

Dekompresji zostaną poddane dane otrzymane we wcześniejszym przykładzie:

symbol początkowy a;
trójki: (0,2,b), (3,1,c), (0,3,c), (0,0,d), (3,2,c).

#	wejście dekodera	słownik\|bufor wyjściowy	wyjście dekodera	uwagi
1	a	`aaaa\|`		słownik jest wypełniany początkowym symbolem
2	(0,2,`b`)	`aaaa\|aab`	`aab`	ze słownika do bufora wyjściowego kopiowane są 2 symbole i "doklejany" 3. symbol z trójki; bufor wyjściowy jest wyprowadzany na wyjście, a cały bufor przesuwany o 3 pozycje w lewo
3	(3,1,`c`)	`aaab\|bc`	`bc`	ze słownika do bufora wyjściowego kopiowany jest jeden symbol i "doklejany" 2. symbol z trójki; bufor wyjściowy jest wyprowadzany na wyjście, a cały bufor przesuwany o 2 pozycje w lewo
4	(0,3,`c`)	`abbc\|abbc`	`abbc`	ze słownika do bufora wyjściowego kopiowane są 3 symbole i "doklejany" 4. symbol z trójki; bufor wyjściowy jest wyprowadzany na wyjście, a cały bufor przesuwany o 4 pozycje w lewo
5	(0,0,`d`)	`abbc\|d`	`d`	do bufora wyjściowego wprowadzany jest tylko jeden symbol zapisany w trójce; bufor przesuwany jest o 1 pozycję w lewo
6	(3,2,`c`)	`bbcd\|ddc`	`ddc`	przed wypełnieniem bufora wyjściowego słownik zawiera 4 symbole: `bbcd`, kopiowane na wyjście mają być 2 symbole, w tym jeden nie zapisany w słowniku - istniejący symbol jest powielany i słownik na chwilę wydłużany: `bbcdd`; podkreślone symbole są kopiowane do bufora wyjściowego, dopisywany jest symbol z trójki, a cały bufor wyjściowy kopiowany na wyjście

Ostatecznie zdekodowany komunikat ma postać: aabbcabbcdddc.

[edytuj] Linki zewnętrzne

Jacob Ziv, Abraham Lempel; A Universal Algorithm for Sequential Data Compression, IEEE Transactions on Information Theory, 23(3), pp.337-343, May 1977.

[edytuj] Bibliografia

Adam Drozdek: Wprowadzenie do kompresji danych. Warszawa: Wydawnictwa Naukowo-Techniczne, 1999. ISBN 83-204-2303-1.

[edytuj] Zobacz też

ASTD współorganizatorem Międzynarodowego Kongresu Kadry

W dniach 24-27 listopada odbędzie się Międzynarodowy Kongres Kadry - VIII edycja Kongresu Kadry, po raz pierwszy w wydaniu międzynarodowym.

Obrady WTO na razie bez przełomu

W toczących się od poniedziałku rozmowach w Genewie na temat zniesienia barier w światowym handlu w ramach tzw. rundy z Dauhy do soboty nie udało się wypracować porozumienia.

Absurdalne zapisy blokują unijne dotacje

Bardzo dobry projekt może nie dostać dofinansowania, jeżeli np. przedsiębiorca wypełni wniosek... czarnym długopisem. Takie wątpliwe wymogi wymyślają urzędnicy - czytamy w "Rzeczpospolitej".

KE zamroziła ponad 2 mld euro dla Bułgarii

Komisja Europejska zamroziła znacznie więcej środków dla Bułgarii, niż ogłoszone w środę 825 mln euro z przedakcesjnych funduszy ISPA, PHARE i SAPARD - napisał bułgarski dziennk "Sega".

Betacom: 35 proc. zysku na dywidendę?

Zarząd Betacom zamierza wnioskować do Rady Nadzorczej i WZA o przeznaczenie na wypłatę dywidendy około 35 proc. zysku netto za rok obrotowy 2007/08. W kolejnych latach zarząd planuje rekomendować wypłatę dywidendy na poziomie 25-35 proc. zysku - poinformowała spółka w raporcie rocznym.

Linki: Strona g��wna

Encyklopedia