LZW

Algoritmus LZW patrí do skupiny LZ algoritmov. Je pomenovaný podľa autora jeho modifikácie, Welch (1984). Redukuje druhú zložku (symbol, ktorý nasledoval za nájdenou najdlhšou postupnosťou) algoritmu LZ78, čím ešte viac zvyšuje jeho efektívnosť. Inak povedané, dekóderu sa posielajú iba indexy do slovníka. Vďaka tomu sa zmenil aj počiatočný slovník, ktorý na začiatku obsahuje všetky jednoznakové postupnosti zo zdrojovej postupnosti.

Kompresia a dekompresia

Pri kompresii, ako pri LZ78, sa hľadá najdlhšia zhoda v slovníku. Index, na ktorom v slovníku nastala zhoda je výstupom algoritmu a zväčšený reťazec (nájdená zhoda nasledujúca ďalším znakom) je pridaný ako nová položka do slovníka.

Ako vidíme, kompresia je pomerne jednoduchá, čo pri dekompresii neplatí. Tak, ako to bolo v predchádzajúcich prípadoch, aj tu použijeme na vysvetlenie príklad.

Tabuľka 3.4: Príklad: LZW dekompresia

Index	Položka	Vstup	Index otca
		initial dictionary
		initial dictionary
		initial dictionary
		initial dictionary
		a	1
		c	3
		c	3
		b	2
		a	1
		d	4
		a,c	5
		c,b	7
		a,c,c	11
		b,a	8
		c,c,...

Obrázok 3.11: LZW graf

Majme na vstupe reťazec . Vidíme, že zdrojová abeceda, , pozostáva zo štyroch symbolov, ktoré sú na prvých miestach v našom slovníku (tabuľka 3.4, obrázok 3.11. Prvá nájdená najdlhšia postupnosť je , preto je ďalší symbol pridaný k tomuto reťazcu, do slovníka je pridaná položka na piatu pozíciu a na výstup poslaný znak (pozícia v slovníku, kde bola nájdená najdlhšia zhoda). Takto by dekóder pokračoval ďalej. Pozrime sa ešte na pozíciu 11 v našom slovníku. Vstupný symbol na tomto mieste je . Keďže je nájdená zhoda, zoberieme ďalší znak . Tu je nájdená zhoda s reťazcom na piatom mieste v slovníku, takže je pridaný nasledujúci znak . Tu už nie je nájdená žiadna zhoda, tento zväčšený reťazec je pridaný do slovníka a ako výstupný reťazec je znak . Konečná sekvencia zakódovaných indexov je . Tak, ako u LZ78, aj tu sa položky (indexy) stávajú čoraz väčšími a tým pádom potrebujeme na ich binárne zakódovanie viac a viac bitov. Tiež tu platí horné ohraničenie veľkosti slovníka, prípadne jeho reinicializácia počas behu.

Pri dekódovaní sa slovník vytvára, dá sa povedať, o jeden krok dozadu. Po dekódovaní posledného kódového slova bude, z tohto dôvodu, v slovníku o jeden záznam menej, čo vôbec nevadí, pretože tento záznam bol do slovníka pridaný ako posledný, a tým pádom nebol nikdy použitý. Na začiatku má dekóder v slovníku iba prvé 4 znaky. Keď dostane prvý symbol , dekóduje (prvý krok sa mierne líši od ostatných). Druhý symbol hovorí, že bol zakódovaný znak a do slovníka pridá reťazec . A ako vie, čo má pridať? Je to celý reťazec, ktorý bol výstupom v minulom kroku algoritmu (v našom prípade ) a prvý znak z reťazca dekódovaného v tomto kroku (v našom prípade ).

Záverečné poznámky

Ako vidíme, efektivita sa zväčšila vďaka odstránenému druhému symbolu v kódovom slove, takže jeho veľkosť závisí naozaj už len od veľkosti samotného slovníka.

Pri kompresii obrázkov našiel algoritmus LZW svoje uplatnenie. Je používaný vo formáte GIF (graphic interchange format).