LZ77
Lempel-Ziv 77,skracane zwykle doLZ77(algorytm LZ77) – metoda strumieniowejsłownikowej kompresji danych.Metoda LZ77 wykorzystuje fakt, że w danych powtarzają się ciągibajtów(np. w tekstach naturalnych będą to słowa, frazy lub całe zdania) – kompresja polega na zastępowaniu powtórzonych ciągów o wiele krótszymi liczbami wskazującymi, kiedy wcześniej wystąpił ciąg i z ilu bajtów się składał; z punktu widzenia człowieka jest to informacja postaci „taki sam ciąg o długości 15 znaków wystąpił 213 znaków wcześniej”.
Algorytm LZ77 jest wolny od wszelkichpatentów,co w dużej mierze przyczyniło się do jego popularności i szerokiego rozpowszechnienia. Doczekał się wielu ulepszeń i modyfikacji, dających lepsze współczynniki kompresji albo dużą szybkość działania. Na LZ77 opiera się m.in. algorytmdeflate,używany jest również w formatachZIP,gzip,ARJ,RAR,PKZIP,a takżePNG.
Algorytm został opracowany w1977przezAbrahama LempelaiJa’akowa Ziwai opisany w artykuleA universal algorithm for sequential data compressionopublikowanym wIEEE Transactions on Information Theory(s. 8–19)[1].Rok później autorzy opublikowali ulepszoną wersję metody, znaną pod nazwąLZ78.
OrganizacjaIEEEuznała algorytm Lempel-Ziv za kamień milowy w rozwoju elektroniki i informatyki[2].
Zasada działania
[edytuj|edytuj kod]W LZ77 zapamiętywana jest wsłownikupewna liczba ostatnio kodowanych danych – przeciętnie kilka do kilkudziesięciu kilobajtów. 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, 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,LZWitp.) 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 wpływać na prędkość kompresji oraz zapotrzebowania pamięciowe, regulując parametry kodera (rozmiar słownika i bufora kodowania).
Algorytm kompresji
[edytuj|edytuj kod]Metoda LZ77 korzysta zbufora(okna), który logicznie podzielony jest na dwie części:
- bufor słownikowy(słownik), przechowującyostatnio przetwarzanych symboli (sufiks);
- bufor wejściowy(lub bufor kodowania), przechowującysymboli do zakodowania.
Bufor słownikowy obejmuje indeksybufor wejściowy
Rozmiaryimogą 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ątkilobajtów,bufor kodowania jest dużo mniejszy. Na przykład w programiegzipsłownik ma 32 kB, 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[3].
- Do bufora wejściowego wstawiane jestpierwszych symboli wejściowych.
- Dopóki w buforze wejściowym są jakieś dane:
- W obrębie bufora słownikowego wyszukiwany jest najdłuższy podciąg równy początkowi bufora wejściowego (najdłuższyprefiksbufora kodowania). Wynikiem wyszukiwania jest indekspoczątku wyszukanego podciągu oraz jego długośćograniczona z góry przezCzęść podciągu może być wspólna z buforem wejściowym!
Jeśli podciągu nie uda się znaleźć, tomoże mieć dowolną wartość, natomiast - Na wyjście wyprowadzana jest trójka (symbolz bufora wejściowego następujący po dopasowanym podciągu).
- Okno (bufor słownikowy + bufor wejściowy) przesuwane jest w lewo opozycji i na koniec bufora dopisywane jest tyleż kolejnych symboli wejściowych (o ile jeszcze są jakieś).
- W obrębie bufora słownikowego wyszukiwany jest najdłuższy podciąg równy początkowi bufora wejściowego (najdłuższyprefiksbufora kodowania). Wynikiem wyszukiwania jest indekspoczątku wyszukanego podciągu oraz jego długośćograniczona z góry przezCzęść podciągu może być wspólna z buforem wejściowym!
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 programiegzipużywa siętablicy haszującejadresowanej 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.
Przykładowy krok algorytmu
[edytuj|edytuj kod]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 opozycji, 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 |... +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---------------------
Przykład
[edytuj|edytuj kod]![](https://upload.wikimedia.org/wikipedia/commons/thumb/1/10/LZ77_0.svg/600px-LZ77_0.svg.png)
![](https://upload.wikimedia.org/wikipedia/commons/thumb/5/50/LZ77_1.svg/600px-LZ77_1.svg.png)
![](https://upload.wikimedia.org/wikipedia/commons/thumb/6/6a/LZ77_2.svg/600px-LZ77_2.svg.png)
![](https://upload.wikimedia.org/wikipedia/commons/thumb/7/75/LZ77_3.svg/600px-LZ77_3.svg.png)
![](https://upload.wikimedia.org/wikipedia/commons/thumb/1/13/LZ77_4.svg/600px-LZ77_4.svg.png)
![](https://upload.wikimedia.org/wikipedia/commons/thumb/8/88/LZ77_5.svg/600px-LZ77_5.svg.png)
![](https://upload.wikimedia.org/wikipedia/commons/thumb/f/f3/LZ77_6.svg/600px-LZ77_6.svg.png)
![](https://upload.wikimedia.org/wikipedia/commons/thumb/3/3d/LZ77_7.svg/600px-LZ77_7.svg.png)
![](https://upload.wikimedia.org/wikipedia/commons/thumb/c/cf/LZ77_8.svg/600px-LZ77_8.svg.png)
![](https://upload.wikimedia.org/wikipedia/commons/thumb/9/99/LZ77_9.svg/600px-LZ77_9.svg.png)
Algorytm dekompresji
[edytuj|edytuj kod]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ąpierwszych pozycji i bufor wyjściowy zajmującykolejnych pozycji.
Dekodowanie przebiega następująco:
- Bufor słownikowy jest wypełniany początkowym symbolem
- Dla wszystkich trójek () wykonuj:
- Skopiuj z bufora słownikowego do bufora wyjściowego symbole z zakresu
- Doklej na koniec bufora wyjściowego symbol
- Na wyjście wyprowadźpoczątkowych symboli z bufora wyjściowego.
- Przesuń zawartość bufora opozycji 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. Podciągi takie mają strukturę xYxYx, gdzie x to pojedynczy symbol, a Y 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 symbolebca
znajdują się w słowniku, to odtworzony ciąg ma postać:bcabcabc
.Nie ma potrzeby fizycznego rozszerzania słownika i kopiowania danych – wystarczy odpowiednio przeliczać indeksy.
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.
Modyfikacja algorytmu
[edytuj|edytuj kod]Algorytm LZ77 stał się podstawą dla wielu rozwiązań:
- LZR(1981) – słownik o nieograniczonej wielkości (indeksy do słownika kodowanekodem omega Eliasa)
- LZSS(1982) – słowa kodowe dwojakiego rodzaju: pojedynczy symbol albo para: (pozycja dopasowania, długość dopasowania)
- LZB(1987) – wariant LZSS, w którym zarówno odległość dopasowania, jak i jego długość nie są ograniczone (długość kodowanakodem gamma Eliasa)
- LZH(1987) – zarówno indeks, jak i długość dopasowania kodowanekodem Huffmana
- LZS– algorytm używany w komercyjnym programie Stacker
- LZO.
Przykład kompresji
[edytuj|edytuj kod]Niech długość słownika i bufora wejściowego będą równe 4, tzn.Do zapisu pozycji w słowniku (P), jak i długości ciągu (C) wystarczą 2bity.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ę odd ;bufor jest przesuwany o 1 pozycję w lewo
|
6 | bbcd/ddc
|
(3,2,c )
|
wbuforzeznajduje 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 |
Zakodowanych zostało 13 symboli; symbole to przeważniebajty(8 bitów), więc cały komunikatbity.
Dane wyjściowe kodera to:
- początkowy symbol – 8 bitów,
- 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 wynosi 68 bitów, co daje współczynnik kompresji ok. 34%.
Przykład dekompresji
[edytuj|edytuj kod]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 | 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
.
Zobacz też
[edytuj|edytuj kod]Przypisy
[edytuj|edytuj kod]- ↑Praca w 1979 roku uznana przez IEEE Information Theory Society za najlepszą publikację z dziedzinie teorii informacji;A universal algorithm for sequential data compression.itsoc.org. [dostęp 2010-09-23].(ang.).
- ↑IEEE History Center: Milestones:Lempel-Ziv Data Compression Algorithm, 1977.ieee.org: IEEE. [dostęp 2013-09-21].(ang.).
- ↑Sposób inicjowania słownika może być inny, jedynym wymogiem jest, aby został jednakowo przeprowadzony przy kodowaniu i dekodowaniu.
Bibliografia
[edytuj|edytuj kod]- Adam Drozdek:Wprowadzenie do kompresji danych.Warszawa: Wydawnictwa Naukowo-Techniczne, 1999.ISBN83-204-2303-1.
- Artur Przelaskowski:Kompresja danych: podstawy, metody bezstratne, kodery obrazów.Warszawa: BTC, 2005, s. 158.ISBN83-60233-05-5.
Linki zewnętrzne
[edytuj|edytuj kod]- Jacob Ziv, Abraham Lempel;A Universal Algorithm for Sequential Data Compression,IEEE Transactions on Information Theory, 23(3), s. 337–343, May 1977.