LZW84
Z Multimediaexpo.cz
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 v letech 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 dále nekomprimovatelná, toto je rozdíl oproti algoritmu LZ77, po kterém lze data dále komprimovat pomocí algoritmu Huffman nebo podobného. Algoritmus byl až do roku 2004 zatížený patentem, dnes je patent prošlý, ale algoritmus byl mezitím překonán. Byl využíván (a je částečně dodnes) v archívech ARC, starých verzích ZIPu (PKZIP 0.x a 1.x), unixovém komprimačním programu compress (soubory s příponou „Z“), grafickém formátu GIF a dokumentech PDF.
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“.
Vysokoúrovňový popis algoritmu v krocích:
- Inicializuj slovník na všechny řetězce dlouhé jeden znak.
- Najdi nejdelší možný řetězec Ř ve slovníku, který odpovídá aktuálnímu vstupu.
- Na výstup pošli index Ř a odstraň řetězec Ř ze vstupu.
- Přidej řetězec Ř + následující znak ze vstupu do slovníku.
- Běž na krok 2.
Pozn.: tedy jak vidíte, nově zakódované podřetězce se mohou na výstup dostat až na druhý výskyt, protože při prvním výskytu ještě nejsou ve slovníku. Fakticky tento první výskyt slouží k uložení informace o jejich složení do výstupních dat.
Související články
Literatura
- SOBOTA, Branislav, MILIÁN, Ján: Grafické formáty, nakl. Kopp, ISBN 80-85828-58-8, zejm. str. 37 a 75.
| Náklady na energie a provoz naší encyklopedie prudce vzrostly. Potřebujeme vaši podporu... Kolik ?? To je na Vás. Náš FIO účet — 2500575897 / 2010 |
|---|
| Informace o článku.
Článek je převzat z Wikipedie, otevřené encyklopedie, do které přispívají dobrovolníci z celého světa. |