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

LZ-78

Základní informace

Jde o paměťově náročnou metodu, neb pro objemné vstupy může slovník zabrat celou volnou paměť. Existuje několik technik, jak tomuto předejít. Při nedostatku nové paměti se může slovník zmrazit, smazat a začít vytvářet nový, případně použít i jiné metody. V kompresní utilitě compress se tento problém řeší zmražením slovníku a následnou kontrolou kompresního poměru. Pokud tento překročí povolenou mez, slovník se smaže a začne se tvořit nový.

Historie

Kompresní metodu LZ78 vymysleli v roce 1978 Abraham Lempel a Jacob Ziv. Z počátku se jednalo o populární kompresní metodu, nadšení ovšem opadlo poté, co byly části algoritmu LZ78 patentovány. Nejznámější modifikace algoritmu je LZW Terry Welche.

Popis

Metoda LZ78 je založena na principu ukládání frází vstupního textu do slovníku. Pokud se uložená fráze v textu objeví znova, na výstup je poslán jen index fráze ve slovníku.

Každý krok LZ78 pošle na výstup dvojici (i,a), kde i je index fráze do slovníku a a je znak následující bezprostředně za nalezenou frází. Slovník je reprezentován jako strom s očíslovanými uzly. Jdeme-li z kořene stromu do daného uzlu, dostaneme frázi ze vstupního textu.

V jednotlivých krocích se hledá nejdelší fráze ve slovníku, která by odpovídala dosud nezpracované časti vstupního textu. Index této fráze spolu s písmenem, které následuje v textu za nalezenou částí, je potom dán na výstup. Do slovníku je pak vložena stárá fráze rošířená o nové písmeno. Tato fráze je označena nejmenším možným číslem.

Kódování začíná se stromem čítajícím jediný uzel, reprezentujícím prázdný řetězec.

Pseudokód


 1:  begin
 2:     inicializace slovníku
 3:     buffer := ""
 4:     while (!konecVstupu()) do
 5:      begin
 6:        symbol := další nezpracovaný znak ze vstupu
 7:        if ( ( buffer.symbol ) je ve slovníku ) then
 8:           buffer := buffer.symbol;
 9:        else
10:         begin
11:           output(indexDoSlovníku(buffer),symbol)
12:           přidej do slovníku ( buffer.symbol )
13:           buffer := ""
14:         end
15:      end
16:     if ( !prázdný(buffer) ) then
17:        output(indexDoSlovníku(buffer));
18:  end

Odkazy

  1. LZ78. Wikipedia, the free encyclopedia.
  2. Arkadi Kagan: Lempel-Ziv Compressions - LZ78 nahlíženo z programátorského hlediska.
  3. Jacob Ziv a Abraham Lempel: Compression of Individual Sequences Via Variable-Rate Coding. IEEE Transactions on Information Theory, September 1978.
  4. LZ77/LZSS and derivatives area - seznam odkazů na rodinu LZ77 algoritmů a další zdroje. Compression Links Info.

Ukázka