Projekty a zdrojové kódy - Jihočeská univerzita
LZW kompresni metoda
LZW je slovníková kompresní metoda. Vymysleli ji pánové Lempel, Ziv a Welch v roce 1978. Je to asi nejznámější implementace metody LZ78.
Algoritmus této metody je takový, že se nahrazují již vyskytnuté řetězce znaků ze souboru určitými kódy.
Kompresní poměr této metody není nejlepší, asi o 30% horší než u nejlepších komprimačních programů. V nejhorším případě je vystupní soubor o 25% vetší než vstupní, ale jeho obrovskou výhodou je to, že její implementace je velmi rychlá a snadno rešitelná!
Tímto je tato metoda určena hlavně pro kompresi a dekompresi v realném čase. Proto její největší využití je u formátu přenosu dat v sítích, ale je použitá též v obrazových formátech GIF a TIFF nebo u postscriptu a PDF dokumenů.
Algoritmus LZW kompresní metody
Kódovací algoritmus si postupně vytváří kódovací tabulku ze slov použitých v již zakódovaném textu. Tato tabulka mapuje vstup na slova/stringy s pevně stanovenou délkou.
Na počátku je tabulka inicializována pomocí všech jednoznakových slov použité abecedy. A dále algoritmus sériově prohledává text, ukládá si do tabulky každé unikátní dvouznakové slovo jako zřetězení vzoru a kódu - tvoří se slovník.
A jakmile má uloženy všechna dvouznaková slova pošle na výstup kód prvního na vstupu. Algoritmus pokračuje v kódování, jakmile je na vstupu nalezeno již známé slovo (je již v tabulce) na výstup se pošle odpovídající kódový znak plus před ním první znak kódovaného slova.
Dekompresnímu algoritmu stačí jen zkomprimovaný text, je schopen si slovník sám zpětně vytvořit.
Ovšem při tomto postupu se může dojít k chybné dekompresi. Při situaci znak-slovo-znak-slovo-znak, kde znak a slovo jsou stejná a dekompresor má již ve svém slovníku uloženo znak-slovo, pak pokud dále načte znak-slovo-znak, není pak schopen toto dekódovat, neboť to nezná.
Pro lepší pochopení ...
Nejste z předchozího textu moudří? Násedující JAVA APPLET snad lépe napoví jak LZW kompresní metoda funguje .)