Tekst źródłowy strony LZMW

'''LZMW''' – [[algorytm]] [[Kodowanie słownikowe|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 <math>(T[i, \ldots]),</math> 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 <math>P + S,</math> jeśli jeszcze nie istnieje
#* '''i''' := '''i''' + '''n'''
#* '''P''' := '''S'''

== Algorytm dekompresji ==
Algorytm dekompresji jest identyczny jak w metodzie [[LZW#Algorytm dekompresji|LZW]].

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

{| class="wikitable" width="100%"
|-
! poprzedni ciąg (P)
! bieżący symbol (S)
! P + S
! indeks (k)
! słownik
! komentarz
|-
| || || || || 1. a<br />2. b<br />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ż ==
* [[LZ77]]
* [[LZ78]]

[[Kategoria:Algorytmy kompresji bezstratnej]]