LZP: Różnice pomiędzy wersjami

Dodane 6 bajtów ,  13 lat temu
WP:SK, drobne redakcyjne
(WP:SK, drobne redakcyjne)
'''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.
 
#*# 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.
 
+---+---+---+---+---+---+---+---+-----+---+---+---+---+---+---+---+---+---------------------
| poprzedni | | kontekst |
kontekst <-- <b>'''P</b>''' -- bieżący
 
Koder wypisze na wyjście liczbę 2, długość ciągu <font color="red">ba</font>.
 
=== Przykładowy krok kompresji - niepowodzenie ===
 
Długość kontekstu '''N''' = 3.
 
+---+---+---+---+---+---+---+---+-----+---+---+---+---+---+---+---+---+---------------------
| poprzedni | | kontekst |
kontekst <-- <b>'''P</b>''' -- bieżący
 
Po poprzednim wystąpieniu kontekstu nie występuje prefiks bufora kodowania - na wyjście wypisywana jest pierwsza litera z bufora kodowania, <font color="red">b</font>.
 
== Algorytm dekompresji ==
 
Parametry są dokładnie takie same jak przy kompresji.
 
#* 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 ==
* {{lang|en}} [http://www.cbloom.com/papers/lzp.html Strona z publikacjami Charlesa Blooma nt LZP] (ostatni dostęp 2.09.2008)
 
== Zobacz też ==
* [[PPM (kompresja)|PPM]]