LZSS

LZSS – słownikowa metoda bezstratnej kompresji danych. LZSS jest ulepszonym wariantem metody LZ77.

Nazwa metody pochodzi od nazwisk: Lempel-Ziv-Storer-Szymanski, została opracowana przez Jamesa A. Storera i Thomasa G. Szymanskiego i opisana w 1982 roku w Journal of the ACM, w artykule pt. Data compression via textual substitution (s. 928–951).

Algorytm LZSS jest używany między innymi w programach PKZIP i ARJ.

Algorytm kompresji

Metoda LZSS, tak samo jak LZ77, używa bufora, podzielonego na dwie części:

• słownik (bufor słownikowy) – przechowującą $k$ ostatnio przetwarzanych symboli, obejmujący indeksy $0\ldots k-1;$
• bufor wejściowy (bufor kodowania) – przechowujący $n$ symboli, które mają zostać zakodowane, obejmujący indeksy $k\ldots k+n-1.$

Wartości $n$ i $k$ są dobierane tak, aby były potęgami dwójki. Rozmiar słownika jest dużo większy niż bufora wejściowego, w praktyce ma kilka-kilkadziesiąt kilobajtów.

W każdym kroku algorytmu w słowniku wyszukiwany jest najdłuższy podciąg równy początkowi bufora wejściowego, charakteryzowany parą ($P\in [0\ldots k-1],$ $C\in [2\ldots n]$), gdzie $P$ – indeks początku podciągu, $C$ – jego długość. Symbol w buforze następujący po dopasowanym ciągu oznaczmy jako $S.$

Algorytm LZ77 wypisuje na wyjście trójki $(P,C,S),$ nawet wtedy, gdy trójka ma większą długość niż opisywaną przez nią ciąg. Algorytm LZSS wypisuje na wyjście tylko pary $(P,C),$ ale bierze przy tym pod uwagę fakt, czy para nie zajmuje więcej bitów niż opisywany przez nią ciąg symboli. Jeśli kodowany ciąg jest dłuższy niż para, wówczas opłaca się wypisać na wyjście parę, w przeciwnym razie na wyjście wypisywany jest tylko pierwszy symbol z bufora wejściowego $S'.$ W celu odróżnienia symbolu od pary, poprzedza się je pojedynczym bitem:

• (0, $S'$),
• (1, $P,$ $C$).

Formalnie algorytm kompresji przebiega następująco:

1. Wypełnij słownik pierwszym symbolem, wypisz ten symbol na wyjście; wypełnij bufor wejściowy $n$ pierwszymi symbolami wejściowymi.
2. Dopóki w buforze wejściowym są dane:
   1. Wyszukaj w słowniku najdłuższy podciąg równy początkowi bufora wejściowego – wynikiem są liczby $P$ i $C.$
      • Jeśli rozmiar pary ($P,$ $C$) jest mniejszy od rozmiaru znalezionego podciągu, zapisz na wyjście trójkę (1,$P,$$C$), przesuń cały bufor o $C$ pozycji w lewo i wprowadź do bufora wejściowego tyle samo kolejnych symboli.
      • W przeciwnym razie wypisz na wyjście parę (0, $S'$), przesuń cały bufor o 1 pozycję w lewo i wprowadź do bufora wejściowego kolejny symbol wejściowy.

Uwaga: ponieważ w przypadku wypisywania pary liczba $C$ nigdy nie będzie miała wartości 0 ani 1, toteż można zmniejszyć liczbę bitów wymaganą do zapisania $C$ poprzez przypisanie wartości binarnej 0 liczby 2, wartości binarnej 1 liczby 3 itd. Np. dla $n=4$ do zapisania $C$ należałoby przeznaczyć 3 bity, a przy takim przyporządkowaniu wystarczą 2 bity.

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 | a | 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)

3. Przyjmując, że para (P,C) zajmuje mniej niż ciąg aac – przesunięcie bufora o C 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 |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---------------------
| a | a | c | a | b | a | a | c | b | a | c | a | b | a | c | ...
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---------------------

4. Przyjmując, że para (P,C) zajmuje więcej bitów niż kodowany ciąg – przesunięcie bufora o 1 pozycję, wprowadzenie do bufora wejściowego jednego symbolu.

          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 | a | b | a | a | c | b | a | c | a | b | a | c | ...
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+-----

Algorytm dekompresji

Do dekompresji potrzebny jest bufor o dokładnie takim samym rozmiarze jak przy kompresji; jest on podzielony na słownik ($k$ symboli) i bufor wyjściowy ($n$ symboli).

1. Wypełnij słownik pierwszym symbolem.
2. Dla kolejnych danych (par i trójek) powtarzaj:
   1. Jeśli mamy do czynienia z trójką (0,$P,$$C$) to skopiuj ze słownika na początek bufora wyjściowego symbole z zakresu $P\ldots P+C-1,$ wypisz na wyjście skopiowane symbole i przesuń cały bufor o $C$ pozycji w lewo.
   2. Jeśli mamy do czynienia z dwójką (1,$S$) to skopiuj symbol $S$ na początek bufora wyjściowego, wypisz na wyjście ten symbol i przesuń cały bufor o jedną pozycję w lewo.

Przykład kompresji

Słownik i bufor wejściowy będą miały rozmiar 4 $(n=k=4),$ a więc do zapisu liczby $P$ i $C$ wystarczą po 2 bity. Przyjmijmy także, że kodowane symbole to bajty (tak jest najczęściej). Wówczas:

• rozmiar trójki (0,P,C) – 1+2+2 = 5 bitów;
• rozmiar pary (1,S) – 1+8 = 9 bitów.

Kompresji zostanie poddany 12-elementowy ciąg aabbcabbcabd.

#	słownik/bufor wejściowy	wyjście kodera	komentarz
1	aaaa/aabb	a	słownik jest wypełniany pierwszym symbolem, bufor wejściowy pierwszymi czterema symbolami wejściowymi
2	aaaa/aabb	(0,0,2)	w słowniku znajduje się 2-elementowy podciąg równy początkowi bufora wejściowego – jego rozmiar wynosi 16 bitów, a rozmiar trójki 5 bitów, zatem na wyjście wypisywana jest trójka, a bufor przesuwany o 2 pozycje
3	aaaa/bbca	(1,b)	w słowniku nie ma ciągu rozpoczynającego się od b, zatem na wyjście wypisywana jest para, a bufor przesuwany o jedną pozycję
4	aaab/bcab	(0,3,1)	w słowniku znajduje się 1-elementowy podciąg równy początkowi bufora wejściowego – jego rozmiar wynosi 8 bitów, a rozmiar trójki 5 bitów, zatem na wyjście wypisywana jest trójka, a bufor przesuwany o 1 pozycje
5	aabb/cabb	(1,c)	w słowniku nie ma ciągu rozpoczynającego się od c, zatem na wyjście wypisywana jest para, a bufor przesuwany o jedną pozycję
6	abbc/abbc	(0,0,4)	w słowniku znajduje się 4-elementowy podciąg równy początkowi bufora wejściowego – jego rozmiar wynosi 32 bity, a rozmiar trójki 5 bitów, zatem na wyjście wypisywana jest trójka, a bufor przesuwany o 4 pozycje
7	abbc/abd	(0,0,2)	w słowniku (na jego początku) znajduje się 2-elementowy podciąg równy początkowi bufora wejściowego; na wyjście wypisywana jest trójka, a bufor przesuwany o 2 pozycje
8	bcab/d	(1,d)	w słowniku nie ma ciągu rozpoczynającego się od d, zatem na wyjście wypisywana jest para, a bufor przesuwany o jedną pozycję

Rozmiar danych przed kompresją: $12\cdot 8=96$ bitów.

Rozmiar danych po kompresji:

• symbol początkowy: 8 bitów.
• trzy pary: $3\cdot 9=27$ bitów,
• cztery trójki: $4\cdot 5=20$ bitów.

W sumie 55 bitów, co daje współczynnik kompresji ok. 42%.

Przykład dekompresji

Zostaną zdekompresowane dane z poprzedniego przykładu.

#	wejście dekodera	wyjście dekodera	słownik	komentarz
1	a		aaaa	wypełnienie słownika pierwszym symbolem
2	(0,0,2)	aa	aaaa	skopiowanie do bufora wyjściowego i na wyjście 2-elementowego ciągu; przesunięcie całego bufora o 2 pozycje w lewo
3	(1,b)	b	aaab	dopisanie do bufora wyjściowego symbolu, wypisanie go na wyjście i przesunięcie całego bufora o jedną pozycję w lewo
4	(0,3,1)	b	aabb	skopiowanie do bufora wyjściowego i na wyjście 1-elementowego ciągu; przesunięcie całego bufora o 1 pozycje w lewo
5	(1,c)	c	abbc	dopisanie do bufora wyjściowego symbolu, wypisanie go na wyjście i przesunięcie całego bufora o jedną pozycję w lewo
6	(0,0,4)	abbc	abbc	skopiowanie do bufora wyjściowego i na wyjście 4-elementowego ciągu; przesunięcie całego bufora o 4 pozycje w lewo
7	(0,0,2)	ab	bcab	jw.
8	(1,d)	d	cabd	dopisanie do bufora wyjściowego symbolu, wypisanie go na wyjście i przesunięcie całego bufora o jedną pozycję w lewo

Jak widać na wyjście zostały wypisane dokładnie te same symbole, które zostały uprzednio skompresowane.

Zobacz też

• LZ78
• LZW

Bibliografia

• Adam Drozdek: Wprowadzenie do kompresji danych. Warszawa: Wydawnictwa Naukowo-Techniczne, 1999. ISBN 83-204-2303-1.brak strony w książce