LZSS

LZSS – Metoda Kompresji Danych

LZSS to słownikowa metoda bezstratnej kompresji danych, będąca ulepszonym wariantem LZ77. Opracowana przez Jamesa A. Storera i Thomasa G. Szymanskiego, została opisana w 1982 roku w artykule „Data compression via textual substitution”. Algorytm LZSS jest wykorzystywany w programach takich jak PKZIP i ARJ.

Algorytm Kompresji

Algorytm LZSS operuje na dwóch buforach:

• Słownik – przechowuje $k$ ostatnio przetwarzanych symboli.
• Bufor wejściowy – przechowuje $n$ symboli do zakodowania.

W każdym kroku algorytmu wyszukiwany jest najdłuższy podciąg w słowniku, odpowiadający początkowi bufora wejściowego, określony parą ($P,\; C$), gdzie $P$ to indeks podciągu, a $C$ to jego długość. W odróżnieniu od LZ77, LZSS wypisuje na wyjście tylko pary ($P,\; C$) lub pojedyncze symbole, w zależności od tego, co jest bardziej efektywne.

Przebieg Algorytmu

Algorytm kompresji przebiega według następujących kroków:

1. Wypełnij słownik pierwszym symbolem i bufor wejściowy $n$ pierwszymi symbolami.
2. Wyszukuj najdłuższy podciąg w słowniku:
• Jeśli para ($P,\; C$) jest mniejsza od kodowanego podciągu, wypisz trójkę (1, $P,\; C$), przesuń bufor o $C$.
• W przeciwnym razie wypisz parę (0, $S’$), przesuń bufor o 1.

Algorytm Dekompresji

Dla dekompresji potrzebny jest identyczny bufor (słownik i bufor wyjściowy). Proces dekompresji obejmuje:

1. Wypełnienie słownika pierwszym symbolem.
2. Dla kolejnych danych (par i trójek) powtarzaj:
• Dla trójki (1, $S$) skopiuj symbol $S$ do bufora wyjściowego.
• Dla pary (0, $P,\; C$) skopiuj symbole z zakresu $P$ do $P+C-1$ do bufora wyjściowego.

Przykłady Kompresji i Dekompresji

Przykład kompresji z danymi „aabbcabbcabd” wykazuje, że przed kompresją zajmowały one 96 bitów, a po kompresji 55 bitów, co daje współczynnik kompresji na poziomie 42%. Po dekompresji uzyskano te same symbole, które były pierwotnie kompresowane.