English
předchozí hlavní stránka obsah další

LZW komprese

Základní informace

Historie

LZW (Lempel-Ziv-Welch) je univerzální bezztrátový kompresní algoritmus vytvořený Abrahamem Lempelem, Jacobem Zivem a Terrym Welchem. Publikován byl Welchem v roce 1984 jako vylepšená implementace algoritmu LZ78. Algoritmus je navržen tak, aby byl rychlý na implementaci, ale ne nutně optimální, protože neprovádí žádnou analýzu komprimovaných dat. Běžný anglický text dokáže zakomprimovat typicky zhruba na polovinu původní délky.

Použití

Metoda se stala široce používanou v programu compress, který se stal více-méně standardním komprimačním nástrojem v Unixových systémech kolem roku 1986. Opravdu masové využití zažila ale později, po roce 1987, kdy byla nasazena jako součást grafického formátu GIF. Může být také (nepovinně) použita v obrázcích formátu TIFF. Používá ji i modemová komprese u V.42bis. Metoda LZW nabízela ve své době ve většině aplikací lepší kompresní poměr než ostatní do té doby dobře známé algoritmy. Stala se první široce používanou univerzální kompresní metodou na počítačích.

Popis

Slovníková LZW metoda je založena na následující velmi jednoduché strategii. Algoritmus postupně rozpoznává a ukládá do tabulky řetězce znaků a tyto řetězce nahrazuje ve výstupním textu přirozenými čísly z předem definovaného intervalu. Tento interval určuje výslednou abecedu a platí pro něj, že například při kódování řetězce znaků zobrazených v osmibitovém zobrazení je prvních 255 čísel vyhrazeno pro zobrazení samostatných znaků z původní abecedy. Čísla nad 255 se pak přidělují jednotlivým nalezeným řetězcům. Přitom se vytváří tabulka (slovník) již rozeznaných řetězců.

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:     while (not EOF(vstupní_soubor)) do
 3:      begin
 4:        readSymbol(znak)
 5:        if ((řetězec+znak) in tabulka_řetězců) then 
 6:           řetězec += znak
 7:        else 
 8:         begin
 9:           output(číslo(řetězec, tabulka_řetězců))
10:           ADD(řetězec, tabulka_řetězců)
11:           řetězec := znak
12:         end  
13:      end
14:  end

Odkazy

  1. LZW. Wikipedia, the free encyclopedia.
  2. Mark Nelson: LZW Data Compression.
  3. Interaktivní LZW komprese
  4. Martin Kopka: Slovníková komprese (LZW).
  5. Terry Welch: A Technique for High-Performance Data Compression. Computer, June 1984.
  6. Michael Dipperstein: Lempel-Ziv-Welch (LZW) Encoding Discussion and Implementation.

Ukázka