LZW - Polski Serwis Naukowy

Ten artykuł dotyczy algorytmu kompresji bezstratnej. Zapoznaj się również z: inne znaczenia.

Lempel-Ziv-Welch (skracane zwykle do LZW) – metoda strumieniowej bezstratnej kompresji słownikowej, będąca modyfikacją metody LZ78.

Pomysłodawcą algorytmu jest Terry A. Welch. Metodę opisał w 1984 roku, w artykule A technique for high-performance data compression opublikowanym w numerze 6. Computer (str. 8-19).

Metoda LZW jest względnie łatwa do zaprogramowania, daje bardzo dobre rezultaty. Wykorzystywana jest m.in. w programach ARC, PAK i UNIX-owym compress, w formacie zapisu grafiki GIF, w formatach PDF i PostScript (filtry kodujące fragmenty dokumentu) oraz w modemach (V.42bis). LZW było przez pewien czas algorytmem objętym patentem, co było przyczyną podjęcia prac nad nowym algorytmem kompresji obrazów, które zaowocowały powstaniem formatu PNG.

LZ78 – słownikowa metoda bezstratnej kompresji danych. Została opracowana w 1978 roku przez Jacoba Ziva i Abrahama Lempela i opisana w IEEE Transactions on Information Theory, w artykule pt. "Compression of individual sequences via variable-rate encoding" (str. 530-536).
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.

Zmiany w stosunku do LZ78

W pojedynczym kroku kompresji LZ78 wyszukiwane jest w słowniku najdłuższe słowo będące prefiksem niezakodowanych jeszcze danych. Na wyjście wypisywany jest indeks tego słowa oraz pierwszy symbol z wejścia znajdujący się za dopasowaniem. Np. jeśli w słowniku pod indeksem 2 zapisane jest słowo "wiki", a kodowany jest ciąg "wikipedia", na wyjście zostanie wypisana para (2, 'p'); do zakodowania pozostanie jeszcze ciąg "edia". Jeśliby nie udało się zlokalizować niczego w słowniku, na wyjście wypisywana jest para (0, pierwsza litera) – oznacza to, że w słowniku nie ma jeszcze słowa jednoliterowego równego tej pierwszej literze.

compress - uniksowy program kompresujący wykorzystujący wariant algorytmu kompresji LZW nazywany LZC. Tworzy pliki z rozszerzeniem .Z i może być używany jako kompresor w programie tar.
GIF (ang. Graphics Interchange Format) – format pliku graficznego z kompresją bezstratną (opis niżej) stworzony w 1987 r. przez firmę CompuServe. Pliki tego typu są powszechnie używane na stronach WWW, gdyż pozwalają na tworzenie animacji dwustanową przezroczystością.

Przewaga LZW nad LZ78 to krótsze wyjście kodera – wypisywany jest wyłącznie indeks słowa. Uzyskano to dzięki pierwszemu etapowi algorytmu, tj. wstępnemu wypełnieniu słownika alfabetem (wszystkimi symbolami, jakie mogą pojawić się w danych), gwarantując w ten sposób, że zawsze uda się znaleźć dopasowanie, przynajmniej jednoliterowe.

PDF (ang. Portable Document Format, przenośny format dokumentu) – format plików służący do prezentacji, przenoszenia i drukowania treści tekstowo-graficznych, stworzony i promowany przez firmę Adobe Systems. Język opisu pliku PDF jest okrojoną wersją języka programowania PostScript wzbogaconą o elementy hipertekstowe.
Algorytm – w matematyce oraz informatyce skończony, uporządkowany ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism - przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku.

Algorytm kompresji (kodowania)

W pojedynczym kroku algorytmu wyszukiwany jest w słowniku najdłuższy prefiks niezakodowanych jeszcze danych. Na wyjście wypisywany jest wówczas kod związany z tym słowem, zaś do słownika dodawana nowa pozycja: konkatenacja słowa i pierwszej niedopasowanej litery.

Algorytm przebiega następująco:

Modem (od ang. MOdulator-DEModulator) - urządzenie elektroniczne, którego zadaniem jest zamiana danych cyfrowych na analogowe sygnały elektryczne (modulacja) i na odwrót (demodulacja) tak, aby mogły być przesyłane i odbierane poprzez linię telefoniczną (a także łącze telewizji kablowej lub fale radiowe). Jest częścią DCE (Data Communications Equipment), które w całości wykonuje opisane wyżej czynności. Nieodzowne do współpracy jest DTE (Data Terminal Equipment) i to dopiero stanowi całość łącza przesyłania danych. Dzięki modemowi można łączyć ze sobą komputery i urządzenia, które dzieli znaczna odległość.
Pixmapa, mapa pikseli – plik wykorzystujący rastrowy sposób reprezentacji komputerowej grafiki dwuwymiarowej polegający na określeniu położenia każdego piksela obrazu, oraz przypisaniu mu wartości określającej kolor w danym trybie koloru.

Wypełnij słownik alfabetem źródła informacji.
c := pierwszy symbol wejściowy
Dopóki są dane na wejściu:
Wczytaj znak s.
Jeżeli ciąg c + s znajduje się w słowniku, przedłuż ciąg c, tj. c := c + s
Jeśli ciągu c + s nie ma w słowniku, wówczas:
wypisz kod dla c (c znajduje się w słowniku)
dodaj ciąg c + s do słownika
przypisz c := s.
Na końcu wypisz na wyjście kod związany c.

O efektywności kompresji w dość dużym stopniu decyduje sposób zapisu kodów (liczb).

LZC - wariant słownikowej metody kompresji LZW, wykorzystywany w programie compress. Ogólną ideą działania metody LZW jest zapisywanie na osobnej liście (w tzw. słowniku) ciągów bajtów, które pojawiły się w kompresowanych danych - kolejne wystąpienie ciągu znajdującego się na liście powodują zapisanie wyłącznie jego numeru (indeksu), który zajmuje mniej bitów niż dany ciąg. W metodzie LZC liczba bitów potrzebna na zapisanie indeksu rośnie od 9 do 16 bitów, wraz ze zwiększaniem liczby pozycji w słowniku; liczba pozycji jest ograniczona do ok. 65 tysięcy (2). Charakterystyczne jest postępowanie w sytuacji, gdy w słowniku nie ma już miejsca na nowe ciągi. Program nie modyfikuje listy słów, lecz wykorzystuje ją do dalszej kompresji, jednocześnie monitorując współczynnik kompresji - dopiero gdy spadnie on poniżej pewnego progu, lista słów jest zerowana i budowana od początku.
Kodowanie słownikowe - kodowanie danych, w którym podciągi komunikatu występujące w słowniku (tj. zbiorze słów) są zastępowane symbolami jednoznacznie opisującym ich pozycję w słowniku, zwykle indeksami (liczbami). Takie metody dobrze kompresują dane, w których podciągi powtarzają się, np. w przypadku tekstów naturalnych (teksty książek, czasopism itp.) wiele słów a nawet całych fraz występuje wielokrotnie.

czytaj dalej: [2], [3]

w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)