LZSS jest nazwą słownikowej metody bezstratnej kompresji danych. LZSS jest to ulepszony wariant metody LZ77. Nazwa metody pochodzi od nazwisk: Lempel-Ziv-Storer-Szymanski, została opracowana przez J.A. Storera i T.G. Szymanskiego i opisana w 1982 roku w Jurnal of the ACM, w artykule pt. "Data compression via textual substitution" (str. 928-951). Algorytm LZSS jest używany między innymi w programach PKZIP i ARJ.
Algorytm: Metoda LZSS, tak samo jak LZ77, używa bufora, podzielonego na część słownikową (przechowującą k ostatnio przetwarzanych symboli, obejmujący indeksy 0...k-1) oraz bufor wejściowy (przechowujący n symboli, które mają zostać zakodowane, obejmujący indeksy k...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,C, 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 symbol 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: 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ę (0,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ę (1, 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.

Source: Wiki