Tekst źródłowy strony LZSS

'''LZSS''' – [[Kodowanie słownikowe|słownikowa]] metoda [[kompresja bezstratna|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 [[bufor]]a, podzielonego na dwie części:
* '''słownik''' ('''bufor słownikowy''') – przechowującą <math>k</math> ostatnio przetwarzanych symboli, obejmujący indeksy <math>0\ldots k-1;</math>
* '''bufor wejściowy''' ('''bufor kodowania''') – przechowujący <math>n</math> symboli, które mają zostać zakodowane, obejmujący indeksy <math>k\ldots k+n-1.</math>

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

Algorytm LZ77 wypisuje na wyjście trójki <math>(P,C,S),</math> nawet wtedy, gdy trójka ma większą długość niż opisywaną przez nią ciąg. Algorytm LZSS wypisuje na wyjście tylko pary <math>(P,C),</math> 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 <math>S'.</math> W celu odróżnienia symbolu od pary, poprzedza się je '''pojedynczym bitem''':
* (0, <math>S'</math>),
* (1, <math>P,</math> <math>C</math>).

Formalnie algorytm kompresji przebiega następująco:

# Wypełnij słownik pierwszym symbolem, wypisz ten symbol na wyjście; wypełnij bufor wejściowy <math>n</math> pierwszymi symbolami wejściowymi.
# 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 <math>P</math> i <math>C.</math>
##* Jeśli rozmiar pary (<math>P,</math> <math>C</math>) jest mniejszy od rozmiaru znalezionego podciągu, zapisz na wyjście trójkę (1,<math>P,</math><math>C</math>), przesuń cały bufor o <math>C</math> pozycji w lewo i wprowadź do bufora wejściowego tyle samo kolejnych symboli.
##* W przeciwnym razie wypisz na wyjście parę (0, <math>S'</math>), 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 <math>C</math> nigdy nie będzie miała wartości 0 ani 1, toteż można zmniejszyć liczbę bitów wymaganą do zapisania <math>C</math> poprzez przypisanie wartości binarnej 0 liczby 2, wartości binarnej 1 liczby 3 itd. Np. dla <math>n=4</math> do zapisania <math>C</math> 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 | <span style="color:blue;">a</span> | <span style="color:blue;">a</span> | <span style="color:blue;">c</span> | a | b | <span style="color:blue;">a</span> | <span style="color:blue;">a</span> | <span style="color:blue;">c</span> | 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 <code>aac</code> – 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 |
 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---------------------
 | <span style="color:blue;">a</span> | <span style="color:blue;">a</span> | <span style="color:blue;">c</span> | a | b | <span style="color:blue;">a</span> | <span style="color:blue;">a</span> | <span style="color:blue;">c</span> | 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 | <span style="color:blue;">a</span> | <span style="color:blue;">a</span> | <span style="color:blue;">c</span> | a | b | <span style="color:blue;">a</span> | <span style="color:blue;">a</span> | <span style="color:blue;">c</span> | 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 (<math>k</math> symboli) i bufor wyjściowy (<math>n</math> symboli).

# Wypełnij słownik pierwszym symbolem.
# Dla kolejnych danych (par i trójek) powtarzaj:
## Jeśli mamy do czynienia z trójką (0,<math>P,</math><math>C</math>) to skopiuj ze słownika na początek bufora wyjściowego symbole z zakresu <math>P \ldots P+C-1,</math> wypisz na wyjście skopiowane symbole i przesuń cały bufor o <math>C</math> pozycji w lewo.
## Jeśli mamy do czynienia z dwójką (1,<math>S</math>) to skopiuj symbol <math>S</math> 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 <math>(n=k=4),</math> a więc do zapisu liczby <math>P</math> i <math>C</math> wystarczą po 2 bity. Przyjmijmy także, że kodowane symbole to [[bajt]]y (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 <code>aabbcabbcabd</code>.

{| class="wikitable"
|-
! #
! 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 || <u>aa</u>aa/<u>aa</u>bb || (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,<code>b</code>)
| w słowniku nie ma ciągu rozpoczynającego się od <code>b</code>, zatem na wyjście wypisywana jest para, a bufor przesuwany o jedną pozycję
|-
| 4 || aaa<u>b</u>/<u>b</u>cab || (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,<code>c</code>)
| w słowniku nie ma ciągu rozpoczynającego się od <code>c</code>, zatem na wyjście wypisywana jest para, a bufor przesuwany o jedną pozycję
|-
| 6 || <u>abbc</u>/<u>abbc</u> || (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 || <u>ab</u>bc/<u>ab</u>d || (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,<code>d</code>)
| w słowniku nie ma ciągu rozpoczynającego się od <code>d</code>, zatem na wyjście wypisywana jest para, a bufor przesuwany o jedną pozycję
|}

Rozmiar danych przed kompresją: <math>12 \cdot 8 = 96</math> bitów.

Rozmiar danych po kompresji:
* symbol początkowy: 8 bitów.
* trzy pary: <math>3 \cdot 9 = 27</math> bitów,
* cztery trójki: <math>4 \cdot 5 = 20</math> bitów.
W sumie 55 bitów, co daje współczynnik kompresji ok. 42%.

== Przykład dekompresji ==
Zostaną zdekompresowane dane z poprzedniego przykładu.

{| class="wikitable"
|-
! #
! wejście dekodera
! słownik| wyjście dekodera
! słownik
! komentarz
|-
| 1 || a ||aaaa| || aaaa
| wypełnienie słownika pierwszym symbolem
|-
| 2 || (0,0,2) ||<u>aa</u>aa| 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,<code>b</code>) ||aaaa| 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) ||aaa<u>b</u>| 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,<code>c</code>) ||aabb| 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) ||<u>abbc</u>| 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) ||<u>ab</u>| ab || bcab || jw.
|-
| 8 || (1,<code>d</code>) ||bcab| 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 ==
* {{Cytuj książkę |nazwisko = Drozdek |imię = Adam |tytuł = Wprowadzenie do kompresji danych |data = 1999 |wydawca = Wydawnictwa Naukowo-Techniczne |miejsce = Warszawa |isbn = 83-204-2303-1}}

[[Kategoria:Algorytmy kompresji bezstratnej]]