LZW

         LZW jak i jego zaimplementowane rozszerzenia jest strumieniowym bezstratnym algorytmem i korzysta ze słowników dynamicznych. Jest on modyfikacją algorytmu LZ78 zaproponowaną przez Terry’ego Welcha w 1984 roku. W przypadku LZ78 dane wejściowe kodowane są za pomocą par liczb <i, c> gdzie i jest indeksem odpowiadającym elementowi słownika, który daje najdłuższe dopasowanie kodowanego ciągu, a c jest kodem znaku w danych wejściowych znajdującego się bezpośrednio za dopasowanym fragmentem. Po każdym dopasowaniu dodajemy do słownika konkatenację dopasowanego elementu słownika i występującego za nim w danych znaku c. Tak więc każdy nowy element słownika powstaje przez skonkatenowanie jednego symbolu z istniejącym wcześniej elementem słownika.

Gdy w przypadku LZ78 występuje konieczność kodowania drugiego elementu pary <i, c>, w LZW istnieje sposób na usunięcie tej konieczności. Aby było to możliwe, trzeba na początku kodowania umieścić w słowniku wszystkie litery alfabetu wejściowego. Koder gromadzi kolejne symbole z ciągu danych wejściowych, tworząc z nich wzorzec p tak długo, jak długo p jest elementem słownika. Jeśli dodanie kolejnej litery a do wzorca daje wzorzec p * a (* oznacza konkatenację), którego nie ma jeszcze w słowniku, to do odbiorcy przesyłany jest indeks wzorca p i do słownika zostaje dodany wzorzec p * a. Następnie zaczynamy odczytywanie kolejnego wzorca, począwszy od litery a

Przykład – kodowanie LZW.

Tekst do zakodowania:

TO,JA,TO,JA,TO,JA,OSTOJA,OSTOJA

Słownik: (elementy czerwone to elementy początkowe w słowniku)

        1               A

        2               J

        3               O

        4               T

        5               ,

        6                TO

        7                O,

        8                ,J

        9               JA

        10             A,

        11             ,T

        12             TO,

        13             ,JA

        14             A,T

        15             TO,J

Zakodowana postać tekstu:

4 3 5 2 1 5 6 8 10 12 9

Dekodowanie przy pomocy algorytmu LZW wykonywane jest z użyciem takiego samego słownika początkowego, jak w przypadku kodowania. Cały stworzony dynamicznie słownik podczas procesu kodowania, jest automatycznie odtwarzany po stronie dekodera. Algorytm wygląda tak:

1.   Umieszczamy w słowniku wszystkie możliwe ciągi jednoliterowe (czyli litery alfabetu).

2.   Tekst odkodowany jest na początku pusty.

3.   Dla i=1,2,...,n, gdzie p₁,..,p_n to ciąg elementów do odkodowania:

a.           Jeśli w poprzednim kroku do słownika dodany był element p?, to zamień go na p p_i[1], gdzie p_i[1] to pierwszy symbol elementu słownika na pozycji p_i

b.          Do tekstu odkodowanego dołącz na koniec element z pozycji p_i słownika.

c.          Jeśli i > 1 i słownik nie jest pełny: do słownika dodaj element p_i?

            Zastosowania LZW

1.     Polecenie compress w Unixie

2.     Kompresja obrazów GIF - Graphics Interchange Format (kompresja niewielka)

3.     Kompresja danych przesyłanych przez modem – V.42 bis