LZW dekomprese
Základní informace
- slovníková kompresní metoda
- jednoprůchodová kompresní metoda
- adaptivní kompresní metoda
- symetrická kompresní metoda
- rozšíření metody LZ-78 - výstupem pouze indexy do slovníku
- rychle rostoucí počet frází ve slovníku
- použití v compress, GIF, TIFF, V.42bis, PDF, PS, ZIP
Historie
LZW (Lempel-Ziv-Welch) je univerzální bezeztrátový algoritmus. Byl navržen Abrahamem Lempelem, Jacobem Zivem a Terryem Welchem. Publikován Welchem v roce 1984 jako vylepšení implementace algoritmu LZ78 od Lempela a Ziva z roku 1978. Algoritmus je navržen pro rychlou implementaci, která nemusí být optimální.
Popis
Kompresní algoritmus vytváří překladovou tabulku z právě komprimovaného textu. Překladová tabulka mapuje kód pevné délky (obvykle 12 bitů) na řetězec znaků. Tabulka je inicializována všemi jednotlivými znaky (definovanými abecedou). Kompresní algoritmus postupně prochází text a ukládá každý unikátní dvouznakový řetězec jako kód/znak zřetězený s kódem odpovídajícím příslušnému prvnímu znaku. Jakmile je každý dvouznakový řetězec uložen, první znak je vypsán na výstup. Vždy, když je načten ze vstupu již přidaný řetězec maximální délky, je tento řetězec rozšířen následujícím znakem a uložen do tabulky. Kód tohoto řetězce maximální délky je vypsán na výstup.
Dekompresnímu algoritmu stačí pouze zkomprimovaný řetězec, protože je schopen si z něj překladovou tabulku sestavit behem dekomprese. Nicméně může nastat případ, kdy řetězec na vstupu má podobu znak/řetězec/znak/řetězec/znak (kde znak je nějaký stejný znak a řetězec je nějaký stejný řetězec) a v překladové tabulce již máme uložen řetězec znak/řetězec. Jakmile dekompresní algoritmus načte znak/řetězec/znak, nemůže tento řetězec najít v tabulce. Nicméně tento stav je řešitelný, protože nově načtený znak je shodný s minule načteným znakem.
Pseudokód
1: begin
2: tmp = ""
3: inicializace slovníku
4: while ((kód = načti kód) != EOF) do
5: begin
6: if ( existuje fráze ve slovníku s kódem (kód) ) then
7: begin
8: fráze := slovník[kód]
9: output(fráze)
10: přidej do slovníku (tmp + první znak z fráze)
11: end
12: else
13: begin
14: if ( kód > maximální index slovníku + 1 )
15: exit
16: fráze := tmp + první znak z tmp
17: output(fráze)
18: přidej do slovníku (fráze)
19: end
20: tmp := fráze
21: end
22: end
Odkazy
- M. Kopka: Slovníková komprese (LZW). 1996.
- Miroslav Beneš:Komprese dat. 2005.
- LZW. Wikipedia, the free encyclopedia.
- Terry Welch: A Technique for High-Performance Data Compression. Computer, June 1984.
- Mark Nelson: LZW Data Compression. Dr. Dobb's Journal, October 1989.
- Stuart Caie: Sad day... GIF patent dead at 20.6.2003.
- Nathan Willis: Bringing back LZW compression. 2005.
- M. C. Battilana: The GIF Controversy: A Software Developer's Perspective. 2004.
- Interaktivní LZW komprese.