LZMW
LZMW – algorytm 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)
- Wyzeruj słownik
- i := 0 - bieżąca pozycja
- T := kodowany tekst
- P := "" - poprzednie słowo, inicjowane na puste
- 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
Algorytm dekompresji jest identyczny jak w metodzie LZW.
Przykład kompresji
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%.