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.

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

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

Wartości ${\displaystyle n}$ i ${\displaystyle 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ą (${\displaystyle P\in [0\ldots k-1],}$ ${\displaystyle C\in [2\ldots n]}$), gdzie ${\displaystyle P}$ – indeks początku podciągu, ${\displaystyle C}$ – jego długość. Symbol w buforze następujący po dopasowanym ciągu oznaczmy jako ${\displaystyle S.}$

Algorytm LZ77 wypisuje na wyjście trójki ${\displaystyle (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 ${\displaystyle (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 ${\displaystyle S'.}$ W celu odróżnienia symbolu od pary, poprzedza się je pojedynczym bitem:

• (0, ${\displaystyle S'}$),
• (1, ${\displaystyle P,}$ ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle P}$ i ${\displaystyle C.}$
      • Jeśli rozmiar pary (${\displaystyle P,}$ ${\displaystyle C}$) jest mniejszy od rozmiaru znalezionego podciągu, zapisz na wyjście trójkę (1,${\displaystyle P,}$${\displaystyle C}$), przesuń cały bufor o ${\displaystyle C}$ pozycji w lewo i wprowadź do bufora wejściowego tyle samo kolejnych symboli.
      • W przeciwnym razie wypisz na wyjście parę (0, ${\displaystyle 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 ${\displaystyle C}$ nigdy nie będzie miała wartości 0 ani 1, toteż można zmniejszyć liczbę bitów wymaganą do zapisania ${\displaystyle C}$ poprzez przypisanie wartości binarnej 0 liczby 2, wartości binarnej 1 liczby 3 itd. Np. dla ${\displaystyle n=4}$ do zapisania ${\displaystyle C}$ należałoby przeznaczyć 3 bity, a przy takim przyporządkowaniu wystarczą 2 bity.

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 | ...
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+-----

Do dekompresji potrzebny jest bufor o dokładnie takim samym rozmiarze jak przy kompresji; jest on podzielony na słownik (${\displaystyle k}$ symboli) i bufor wyjściowy (${\displaystyle 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,${\displaystyle P,}$${\displaystyle C}$) to skopiuj ze słownika na początek bufora wyjściowego symbole z zakresu ${\displaystyle P\ldots P+C-1,}$ wypisz na wyjście skopiowane symbole i przesuń cały bufor o ${\displaystyle C}$ pozycji w lewo.
   2. Jeśli mamy do czynienia z dwójką (1,${\displaystyle S}$) to skopiuj symbol ${\displaystyle S}$ na początek bufora wyjściowego, wypisz na wyjście ten symbol i przesuń cały bufor o jedną pozycję w lewo.

Słownik i bufor wejściowy będą miały rozmiar 4 ${\displaystyle (n=k=4),}$ a więc do zapisu liczby ${\displaystyle P}$ i ${\displaystyle 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.

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

Rozmiar danych po kompresji:

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

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

Zostaną zdekompresowane dane z poprzedniego przykładu.

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

• LZ78
• LZW

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