LZP

LZP (P od predykacja) - metoda kompresji opracowana w 1996 roku przez Charlesa Blooma, będąca modyfikacją algorytmu LZ77, wykorzystująca kontekstowość danych - pewne ciągi występują z większym prawdopodobieństwem w sąsiedztwie innych. Mówiąc obrazowo, jeśli wcześniej po ciągu abc wystąpił ciąg def, i znów pojawił się ciąg abc, to jest szansa, że następnym ciągiem będzie def.

Metoda LZP nie została opatentowana.

Różnica w stosunku do LZ77 przedstawia się następująco:

• w LZ77 w słowniku wyszukiwany jest najdłuższy prefiks niezakodowanych jeszcze danych, koder wypisuje parę (pozycja prefiksu, jego długość);
• w LZP również wyszukiwany jest najdłuższy prefiks, ale wyłącznie od pozycji ostatniego wystąpienia kontekstu, koder wypisuje jedynie długość prefiksu.

Kontekst to ciąg określonej długości poprzedzający dane mające zostać zakodowane; Bloom proponuje stosować konteksty kilkuznakowe, w przykładowych implementacjach wykorzystywał 3 do 5 znaków. Do zapamiętywania ostatniego wystąpienia kontekstu używana jest tablica mieszająca, w której problem kolizji nie jest rozwiązywany - jest to podyktowane względami wydajnościowymi.

Algorytm kompresji

Tak samo jak w LZ77 jest bufor (albo okno), podzielone na słownik, tj. już zakodowane dane, oraz bufor kodowania, tj. dane mające właśnie zostać zakodowane. Kontekst poprzedza bufor kodowania, jest sufiksem słownika.

Koder wypisuje dwa rodzaje kodów:

1. litera - niezakodowana litera (np. znak ASCII)
2. liczba - długość prefiksu

Algorytm przebiega następująco:

1. Inicjalizacja:
   • N := długość kontekstu
   • s := kodowany tekst
   • i := 0 - bieżąca pozycja
   • Wyzeruj tablicę L przechowującą ostatnie wystąpienia kontekstu
2. Wypisz N pierwszych liter
3. i := N - przesuń okno o N pozycji w lewo
4. Dopóki są dane (i < długość(s)) powtarzaj:
   • P := L[kontekst] - pobierz pozycję ostatniego wystąpienia kontekstu
   • L[kontekst] := i - zapamiętaj bieżącą pozycję
   • Jeśli P nie istnieje (nie było jeszcze takiego kontekstu) wypisz na wyjście pierwszy niezakodowany znak i przesuń okno w lewo o jedną pozycję; i := i + 1.
   • Jeśli P istnieje znajdź najdłuższy podciąg, tzn. s[P, P + k] = s[i, i + k], gdzie k to długość dopasowania:
     1. Jeśli k = 0 (brak dopasowania), wypisz literę s[i], przesuń okno w lewo o jedną pozycję; i := i + 1;
     2. Jeśli k > 0 (dopasowanie istnieje), wypisz liczbę k, przesuń okno o tyle pozycji w lewo; i := i + k;

Przykładowy krok kompresji - przypadek znalezienie prefiksu

Długość kontekstu N = 3.

 |                 słownik                         | bufor kodowania   | dane niezakodowane
 +---+---+---+---+---+---+---+---+-----+---+---+---+---+---+---+---+---+---------------------
 | a | b | <font color="blue">c</font> | <font color="blue">a</font> | <font color="blue">b</font> | <font color="red">b</font> | <font color="red">a</font> | c | ... | <font color="blue">c</font> | <font color="blue">a</font> | <font color="blue">b</font> | <font color="red">b</font> | <font color="red">a</font> | a | a | b |         ... 
 +---+---+---+---+---+---+---+---+-----+---+---+---+---+---+---+---+---+---------------------
         | poprzedni |                 | kontekst  |
           kontekst       <-- '''P''' --       bieżący

Koder wypisze na wyjście liczbę 2, długość ciągu ba.

Przykładowy krok kompresji - niepowodzenie

Długość kontekstu N = 3.

 |                 słownik                         | bufor kodowania   | dane niezakodowane
 +---+---+---+---+---+---+---+---+-----+---+---+---+---+---+---+---+---+---------------------
 | a | b | <font color="blue">c</font> | <font color="blue">a</font> | <font color="blue">b</font> | c | c | c | ... | <font color="blue">c</font> | <font color="blue">a</font> | <font color="blue">b</font> | <font color="red">b</font> | a | a | a | b |         ... 
 +---+---+---+---+---+---+---+---+-----+---+---+---+---+---+---+---+---+---------------------
         | poprzedni |                 | kontekst  |
           kontekst       <-- '''P''' --       bieżący

Po poprzednim wystąpieniu kontekstu nie występuje prefiks bufora kodowania - na wyjście wypisywana jest pierwsza litera z bufora kodowania, b.

Algorytm dekompresji

Parametry są dokładnie takie same jak przy kompresji.

Algorytm:

1. N := długość kontekstu
2. i := 0 - bieżąca pozycja
3. Wczytaj N pierwszy liter, pierwszy kontekst
4. Dopóki są dane:
   • Wczytaj daną
   • Jeśli to litera, wypisz ją na wyjście i dopisz na koniec bufora
   • Jeśli to liczba (k), pobierz pozycję ostatniego wystąpienia kontekstu P, skopiuj na wyjście podciąg bufor[P, P+k], i ten sam ciąg dopisz na koniec bufora, zaktualizuj tablicę L

Linki zewnętrzne

• (ang.) Strona z publikacjami Charlesa Blooma nt LZP (ostatni dostęp 2.09.2008)

Zobacz też

• PPM