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 (typicky 256 znaků ASCII). 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). Jakmile má uložena 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, slovník si vytváří stejně jako u komprimace „za chodu“.
[editovat] Související články
[editovat] Zdroje
- SOBOTA, Branislav, MILIÁN, Ján: Grafické formáty, nakl. Kopp, ISBN 80-85828-58-8, zejm. str. 37 a 75.
