LZ77 deflate

Algoritmus LZ77 (pomenovaný podľa svojich objaviteľov A.Lempela a J.Ziva a roku vzniku algoritmu 1977) je založený na princípe nahradzovania duplicitných reťazcov znakov špeciálnymi kódmi. To znamená, že pokiaľ kompresor nájde reťazec znakov, ktorý už bol raz v kódovaných dátach obsiahnutý, nahradí ho jedným, alebo viac špeciálnymi kódmi, ktoré obsahujú odkaz na jeho pôvodný výskyt. Zjednodušene si to môžeme ukázať na príklade (zápis chápte len symbolicky,nieje použitý špeciálny znak): 

                                    < 4>
leze po železe  <<- zakódujeme ->>  leze po že[10,4]    [pozícia,dĺžka]
                                    |<--10---|

Kompresor si vyhradí špeciálny znak (ktorého pravdepodobnosť výskytu je najmenšia) a tento využíva k identifikácii kompresie. Pokiaľ kompresor nájde duplicitný reťazec, vyšle špeciálny znak a po ňom pozíciu a dĺžku duplicity. V prípade, že sa v kódovaných dátach objaví špeciálny znak, je poslaný na výstup tento špeciálny znak a za ním napr. znak #255. Je to značka podľa ktorej dekompresor spozná, že sa v zdrojových dátach objavil špeciálny znak.

V praxi sa algoritmus LZ 77 používa v metóde deflate. Metódu LZ77 deflate používajú komprimačné programy zip, gzip, pkzip a iné.
Metóda deflate využíva dva kompresné algoritmy: Huffmanove kódovanie a kompresiu LZ77.

Teraz sa zameriame na spôsob akým je kompresná schéma LZ77 implementovaná v metóde deflate. Pokiaľ teda kompresor našiel v predchádzajúcich dátach duplicitu s reťazcom začínajúcim na aktuálne komprimovanej pozícii, vyšle špeciálny kód, nasledovaný dvojicou kódov dĺžka-pozícia.
 špeciálny znak   dĺžka duplicitného reťazca   pozícia duplicity vzhľadom k predchádzajúcim dátam 
Dĺžka vyjadruje počet bytov ktoré boli nájdené ako duplicitné a pozícia relatívnu pozíciu k pozícii aktuálnej (v spätnom smere). Duplicitné reťazce sú vyhľadávané v predchádzajúcich dátach v tzv. posuvnom okne (sliding window). Jeho dĺžka (veľkosť) záleží od konkrétnej implementácie, ale v praxi sa používa 32 768 bytov veľké okno. Jednoducho povedané-za účelov vyhľadania duplicitného reťazca, nie sú prehľadávané všetky predchádzajúce dáta, ale iba dáta v rozsahu 32 768 bytov spätne. Prirodzene, že kompresor (dekompresor) musí disponovať záznamom (má ho v pamäti) o posledných 32 768 bytoch (znakoch). Ďalej je potrebné aby kompresor maximálne efektívne zapísal hodnoty dĺžok a pozícií. K tomuto účelu sa používajú nasledujúce tabuľky:

Tabuľka 1. sa vzťahuje k dĺžke duplicitného reťazca. V stĺpci označenom Code sú kódy reprezentujúce dĺžku reťazca. Začínajú hodnotou 257 pretože hodnoty 0...255 sú vyhradené pre Huffanove kódovanie a 256 znamená EOF (koniec súboru). Hodnoty 257 majú deväťbitové vyjadrenie najvyšší bit je rovný 1, čo je vlastne ten špeciálny znak. V stĺpci Extra Bits je doplnková dĺžka a v stĺpci Lenghts je dĺžka alebo interval dĺžky duplicity. Mechanizmus tvorby kódu je nasledovný. Kompresor pozná skutočnú dĺžku duplicity a hľadá najprv v stĺpci Lenghts taký interval prípadne hodnotu, do ktorého táto skutočná dĺžka patrí. V prípade, že ide o interval, zistí sa počet bitov doplnkovej dĺžky a do týchto bitov sa vyplní diferencia skutočnej dĺžky od dolného okraja intervalu. Takto vytvorený kód alebo dvojivca kódov sa vyšle na výstup. Pozri príklad.

Tabuľka 1.
Code Extra Bits Lengths Code Extra Bits Lengths Code Extra Bits Lengths
257 0 3 267 1 15,16 277 4 67-82
258 0 4 268 1 17,18 278 4 83-98
259 0 5 269 2 19-22 279 4 99-114
260 0 6 270 2 23-26 280 4 115-130
261 0 7 271 2 27-30 281 5 131-162
262 0 8 272 2 31-34 282 5 163-194
263 0 9 273 3 35-42 283 5 195-226
264 0 10 274 3 43-50 284 5 227-257
265 1 11,12 275 3 51-58 285 0 258
266 1 13,14 276 3 59-66      

Tabuľka 2. obsahuje kódy prislúchajúce relatívnej pozícii duplicity vzhľadom k predchádzajúcim dátam. V stĺpci Distance je relatívna pozícia, jej kód je v stĺpci Code a počet bitov doplnkovej dĺžky je v stĺpci Extra Bits. Kompresor pri tvorbe kódu postupuje podobne ako v predchádzajúcom prípade. Teda najprv zistí, do ktorého intervalu skutočná pozícia patrí. Potom zistí počet doplnkových bitov pre tento interval a do nich zapíše odchylku skutočnej pozície od dolného intervalu. Takto vytvorený kód sa vyšle na výstup. Pozri príklad.

Tabuľka 2.
Code Extra Bits Distance Code Extra Bits Distance Code Extra Bits Distance
0 0 1 10 4 33-48 20 9 1025-1536
1 0 2 11 4 49-64 21 9 1537-2048
2 0 3 12 5 65-96 22 10 2049-3072
3 0 4 13 5 97-128 23 10 3073-4096
4 1 5,6 14 6 129-192 24 11 4097-6144
5 1 7,8 15 6 193-256 25 11 6145-8192
6 2 9-12 16 7 257-384 26 12 8193-12288
7 2 13-16 17 7 385-512 27 12 12289-16384
8 3 17-24 18 8 513-768 28 13 16385-24576
9 3 25-32 19 8 769-1024 29 13 24577-32768

Príklad: Nech je dĺžka duplicity 100 a jej pozícia 350 znakov spätne od komprimovaného znaku.

Lenghts=100   (dĺžka)
Distance=350  (pozícia)

1.Kompresor najprv spacúva dĺžku a teda hľadá interval, ktorému hodnota 100 prináleží.
  V Tabuľke 1. nájde interval 99-114 ktorému odpovedá kód 279 a 4 doplnkové bity.
  -->> vyšle teda kód 279 na výstup (čím zároveň označí, že dáta sú LZ77 komprimované)
  -->> do 4 bitov vloží hodnotu 1 (100-99=1=0001b) a vyšle ju bezprostredne za kódom 279

2.Teraz kompresor spracuje relatívnu pozíciu duplicity pre hodnotu 350.
  V Tabuľke 2. nájde interval 257-384 ktorému odpovedá kód 16 a 7 doplnkových bitov.
  -->> vyšle teda kód 16 na výstup
  -->> do 7 bitov vloží hodnotu 93 (350-257=93=1011101b) a vyšle ju taktiež na výstup

Komprimované dáta sú organizované v blokoch s rôznou veľkosťou. Každý blok komprimovaných dát začína 3 bitovou hlavičkou, ktorá obsahuje nasledovné dáta:

prvý bit            BFINAL
nasledujúce 2 bity  BTYPE
BFINAL nastaví sa iba v prípade, že sa jedná o posledný blok komprimovaných dát

BTYPE špecifikuje ako sú dáta v bloku komprimované
00 - nekomprimované. Vhodné pre dáta, ktoré už boli predtým nejakým spôsobom komprimované.Na začiatku sa potom uvedie iba hodnota označujúca počet bytov dát a potom nasledujú dáta v podobe jednotlivých bytov.
01 - komprimované LZ77 a fixným Huffmanovým kódom. Použitú tabuľku Huffmanových kódov špecifikuje Deflate specification a preto ju nieje potrebné vkladať do bloku komprimovaných dát pre potreby dekompresie.
10 - komprimované LZ77 a dynamickým Huffmanovým kódom. Tabuľky Huffmanových kódov vytvára kompresor a ukladá ich do bloku spolu s komprimovanými dátami.
11 - rezervované (chyba)

Organizácia dát v blokoch má aj určité nevýhody. Na rozdiel od algoritmu LZW kde komprimované dáta môžu byť vysielané (napr. modemom) kontinuálne, je potrebné v algoritme LZ77 počkať na kompresiu celého bloku a až následne môžu byť dáta vyslané.

Pozn.: Kompresor aj dekompresor využívajú dve rôzne tabuľky Huffmanových kódov. Jednu pre dĺžku a druhú pre pozíciu.

Informačné zdroje:

[1] MACEK David, "Komprese je věda", CHIP č.6/96
[2] FELDSPAR Antaeus, "An Explanation of the Deflate Algorithm"
      http://www.info-zip.org/pub/infozip/zlib/feldspar.html
[3] DEUTCH Peter, RANDERS-PEHRSON Glenn, "Zlib Specifications"
      http://www.info-zip.org/pub/infozip/zlib/zlib_docs.html
[4] Jean-loup's home page - stránka autora programu gzip, http://gailly.net
[5] Compression FAQ, http://www.faqs.org/faqs/compression-faq/part2/preamble.html
[6] ftp://ftp.uu.net/archiving/zip, ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html

[hlavná strana]

Dušan SOVIČ