LZMW

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

LZMWalgorytm kompresji słownikowej będący modyfikacją algorytmu LZW, zaproponowany w 1985 roku przez V. Millera i M. Wegmana w artykule Variations on a theme by Ziv and Lempel.

Zmianie podlega jedynie koder, dekoder jest taki sam jak w metodzie LZW.

W LZW po wyszukaniu w słowniku najdłuższego prefiksu niezakodowanych danych, do słownika dodawane jest nowe słowo będące konkatenacją tego prefiksu i następującego po nim znaku. Innymi słowy do słownika trafia słowo o jeden znak dłuższe niż prefiks. Z kolei w metodzie LZMW pamięta się słowo dopasowane w poprzednim kroku i po dopasowaniu kolejnego, do słownika trafia konkatenacja obu słów. W ten sposób słowa są pojawiające się w słowniku szybko stają się coraz dłuższe.

Modyfikacją LZMW jest z kolei LZAP (James Storer, 1988), która dodaje do słownika konkatenację poprzedniego słowa z wszystkimi prefiksami bieżącego – to powoduje znaczący rozrost słownika, jednak pozwala ominąć niedogodności LZMW.

Algorytm kompresji (kodowania)[edytuj | edytuj kod]

  1. Wyzeruj słownik
  2. i := 0 - bieżąca pozycja
  3. T := kodowany tekst
  4. P := "" - poprzednie słowo, inicjowane na puste
  5. Dopóki i < długość(T), wykonuj:
    • Znajdź najdłuższy prefiks niezakodowanych danych który znajduje się w słowniku - wynikiem jest bieżące słowo S o kodzie k i długości n znaków
    • Na wyjście wypisz kod k
    • Do słownika dodaj słowo jeśli jeszcze nie istnieje
    • i := i + n
    • P := S

Algorytm dekompresji[edytuj | edytuj kod]

Algorytm dekompresji jest identyczny jak w metodzie LZW.

Przykład kompresji[edytuj | edytuj kod]

Zostanie zakodowany ciąg składający się z 12 znaków: "aaaaabbbaaaa".

poprzedni ciąg (P) bieżący symbol (S) P + S indeks (k) słownik komentarz
1. a
2. b
3. c
inicjalizacja słownika alfabetem
a a 1 - indeks 'a' nic nie jest dodawane do słownika, P := 'a'
a a aa 1 - indeks 'a' 4. aa do słownika jest dodawany ciąg 'aa', P := 'a'
a aa aaa 4 - indeks 'aa' 5. aaa do słownika jest dodawany ciąg 'aaa', P := 'aa'
aa a aaa 1 - indeks 'a' nic nie jest dodawane do słownika, P := 'a'
a b ab 2 - indeks 'b' 6. ab do słownika jest dodawany ciąg 'ab', P := 'b'
b b bb 2 - indeks 'b' 7. bb do słownika jest dodawany ciąg 'bb', P := 'b'
b b bb 2 - indeks 'b' nic nie jest dodawane do słownika, P := 'b'
b aaa baaa 5 - indeks 'aaa' 8. baaa do słownika jest dodawany ciąg 'baaa', P := 'aaa'
aaa a aaaa 1 - indeks 'a' 9. aaaa do słownika jest dodawany ciąg 'aaaa', P := 'a'

Zakodowane dane składają się z 9 indeksów: 1, 1, 4, 1, 2, 2, 2, 5, 1.

Jeśli przyjąć, że indeksy oraz symbole są zapisane na tej samej liczbie bitów, to współczynnik kompresji wyniesie ok. 25%.

Zobacz też[edytuj | edytuj kod]