LZ 78

Domů Komprese

Kompresory založené na tomto principu postupně přidávají zapisované řetězce do slovníku a pokud ve vstupním souboru najdou nějaký řetězec, který již je ve slovníku, nahradí ho odkazem do tohoto slovníku. Dále je popsán algoritmus LZW pocházející od Terry Welsche z roku 1984, původně určený k hardwarové implementaci do diskových řadičů.

Výhodou této metody je velmi dobrý kompresní poměr (zvláště při aplikaci některé statistické metody na výsledný kód), rychlá komprese i dekomprese a nevelké nároky na pamět.

Komprese

Algoritmus začíná s prázdným slovníkem a řetězcem L obsahujícím první znak zdrojového souboru. Vždy po přečtení dalšího znaku c zjistí, jestli se řetězec L+c vyskytuje ve slovníku. Pokud ano, pouze prodlouží řetězec L o znak c, jinak zapíše např. 12-ti bitový odkaz do slovníku nebo (pokud řetězec L obsahuje jediný znak) pouze znak, ale opět 12-ti bitově. V tomto případě tedy čísla 0-255 jsou jednotlivé znaky a čísla 256-4095 indexy do slovníku. Pokud se slovník zaplní dříve než je přečten celý soubor, je celý slovník smazán a začíná se plnit znovu. Někdy se pro zlepšení účinnosti místo smazání slovníku používá algoritmus LRU (last-recently-used) pro odstranění nepoužívaných řetězců ze slovníku. Vzhledem k tomu, že slovník se plní od nejnižších pozic, je pro zlepšení kompresního poměru výhodné začít kódy ukládat pouze 9-ti bitově a teprve když se slovník více zaplní, postupně je rozšiřovat až na těch např. 12 bitů. Slovník dekompresoru se totiž plní stejně a tak dekompresor snadno pozná, kdy začít kódy číst 10-ti bitově.

1
2
3
4
5
6
7
8
9
10
11
L = readChar
while (!eof(input)) {
  c = readChar
  if (Lc ve slovníku)
    L = Lc
  else {
    zapsat kód pro řetězec L
    přidat Lc do slovníku
    L = c
  }
}

Příklad:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Vstup: WEB-WEB-WEB!

Řetězec L    Přečtený znak    Výstup    Nová položka ve slovníku
                 W
   W             E              W       (256) = WE
   E             B              E       (257) = EB
   B             -              B       (258) = B-
   -             W              -       (259) = -W
   W             E            Řetězec WE již je ve slovníku
   WE            B            (256)     (260) = WEB
   B             -
   B-            W            (258)     (261) = B-W
   W             E
   WE            B
   WEB           !            (260)     (262) = WEB!
   !           (eof)            !

Demonstrační Java Applet

Při kompresi je tedy velmi často nutné zjistit, jestli nějaký řetězec již ve slovníku je, případně jeho kód. K tomuto účelu by se hodil strom nebo hash-table: např. z kódu řetězce a přidávaného znaku spočteme index do tabulky obsahující kód řetězce, přidávaný znak a kód nového řetězce. Pokud první dvě položky souhlasí, máme kód celého řetězce, jinak jsme na špatné adrese a hledáme někde jinde (např. o několik řádků dál), nebo je tento řádek tabulky prázdný (zjistíme podle speciální hodnoty), celý řetězec tedy není ve slovníku a navíc máme místo, kam ho uložit.

Dekomprese

Dekompresor postupně čte kódy, zapisuje jim příslušející řetězce a přidává nové řetězce do slovníku. Do slovníku je vždy přidán řetězec reprezentovaný předcházejícím kódem a první znak z řetězce s aktuálním kódem. V případě, že byl přečten kód, kterému ještě nebyl přiřazen řetězec (to se stane např. pokud původní text obsahoval několik stejných znaků za sebou), je do slovníku přidán řetězec skládající se z předcházejícího řetězce a jeho posledního znaku. V průběhu dekomprese má dekompresor stejný slovník jako kompresor.

1
2
3
4
5
6
7
8
read last
write last
while (!eof(input)) {
  read code
  write řetězec table[code] (nebo znak code)
  přidání řetězce table[last]+prvni znak table[code] do slovníku
  last = code
}

Tabulku řetězců lze přímo indexovat přečteným kódem (pokud je větší než 0xFF, jinak jde o jediný znak a ten stačí zapsat na výstup). Stačí, když tabulka bude obsahovat kód prefixu a nově přidaný znak. Postupným procházením tabulky podle kódu prefixu tak dostaneme odzadu celý řetězec reprezentovaný přečteným kódem.

Problém nastane, pokud byl přečten kód řetězce, který ještě není v tabulce. To se opravdu stát může: při kompresi zjistíme, že řetězec (cL)c ještě není ve slovníku, proto ho přidáme a jako začátek nového řetězce vezmeme c, pokud na vstupu následuje Lcx, zapíšeme kód pro cLc a přidáme (cLc)x do slovníku. Při dekompresi přečteme kód pro cLc (který ještě není v tabulce) a … Teď již je vidět, že stačí, když do tabulky přidáme frázi skládající se z předcházejícího řetězce (last) a jeho prvního znaku, celou tuto frázi zapíšeme na výstup a jako nový řetězec last vezmeme jeho první znak.

Demonstrační program v C