LZW84

Z Wikipedie, otevřené encyklopedie

LZW84 (Lempel-Ziv-Welch 84) je bezeztrátový kompresní algoritmus vyvinutý Abrahamem Lempelem, Jacobem Zivem a Terry Welchem. Byl publikován v roce 1984 jako vylepšení algoritmů LZ77 a LZ78 publikovaných 1977 a 1978. Je relativně jednoduchý a rychlý, ale nedosahuje zdaleka tak dobré komprese jako náročnější algoritmy jako LZMA, je většinou horší než Deflate a neprovádí analýzu dat. Data prošlá algoritmem LZW84 jsou inkompresibilní, toto je rozdíl oproti algoritmu LZ77, po kterém lze data dále kompresovat pomocí algoritmu Huffman nebo podobných. Algoritmus byl až do roku 2004 postižený patentem, dnes je patent prošlý, ale algoritmus mezitím překonaný. Byl využíván (a je částečně dodnes) v archivech ARC, starých verzích ZIP (PKZIP 0.x a 1.x), kompresoru „Z“, obrazů GIF, a dokumentech PDF.

[editovat] Popis algoritmu

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 (něco jako 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 (tj. 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á.