STISKANJE DATOTEK

Opis algoritma za zip stiskanje


  1. Zip stiskalni program temelji na LZ77 (Lempel - Ziv 1977) algoritmu. Najde ve~kratne nize v vhodnih podatkih. Drugi pojavitveni niz se nadomesti s kazalcem na prej{nji niz v obliki para (oddaljenost, dol`ina) . Oddaljenost je omejena z 32K byti, dol`ina pa z 258 byti. ^e se niz ne pojavi nikjer v 32K bytih, se ta niz prepi{e kot zaporedje enakih bytov. (V tem opisu se mora niz jemati kot neomejeno zaporedje bytov in ne kot omejen tiskan znak).

  2. Enaki nizi ali dol`ine ujemalnih nizov so stisnjeni s prvim Huffmanovim drevesom, oddaljenosti do ujemalnih nizov pa z drugim drevesom. Drevesi sta shranjeni v kompaktni obliki na za~etku vsakega bloka. Bloki imajo lahko poljubno velikost (razen tega morajo stisnjeni podatki enega bloka ustrezati razpolo`ljivi velikosti pomnilnika). Velikost bloka je dolo~ena ko zip z algoritmom odlo~i, kdaj bi bilo koristno za~eti nov blok z sve`ima drevesoma (to bi bilo v grobem opis stiskanja).

  3. Ponovitvene nize najdemo z uporabo "hash" tabel. Vsi vhodni nizi dol`ine 3 se vnesejo v "hash" tabelo. "Hash" indeks je izra~unan za naslednje 3 byte. ^e vrsta "hash" ni prazna za naslednji indeks, se vsi nizi v vrsti primerjajo s trenutnim vhodnim nizom in ozna~i se najdalj{i niz.

  4. "Hash" vrsta za~ne iskanje pri najnovej{em nizu z najkraj{o razdaljo, in tako izkoristi prednost pri Huffmanovem kodiranju. Vrsta je enojno povezana in v njej ni brisanja. Algoritem preprosto opusti stare ujemalne nize.

  5. Da prepre~imo najslab{o mo`no situacijo, so zelo dolge vrste samodejno skraj{ane (na za~etku ali koncu) na dolo~eno dol`ino. To lahko dolo~imo v izbiri, ki jih program zip vsebuje (zip -1 do -9). Tako zip ne najde vedno najdalj{i mo`en ujemalni niz, vendar poi{~e dovolj dolgega.

  6. Zip v vrsti odlo`i tudi ujemalne nize s po~asnej{im ra~unskim mehanizmom. Potem ko je algoritem na{el ujemalni niz dol`ine N, zip i{~e dalj{i ujemalni niz na naslednjem vhodnem bytu. ^e ga najde, se prej{nji ujemalni niz skraj{a v niz dol`ine ena ( to povzro~i nastank enega enojnega byte). To nam omogo~i, da kasneje v algoritmu poi{~emo dalj{i ujemalni niz. Druga~e zadr`imo originalni ujemalni niz in naslednji mo`en je le N korakov pozneje.

  7. Ujemalni nizi z po~asej{im ra~unskim mehanizmom so tudi izbira ki jo program zip vsebuje. ^e je trenutni ujemalni niz dovolj dolg, zip preneha z iskanjem dalj{ega, kar pospe{i celoten proces stiskanja. ^e je stiskalno razmerje pomembnej{e od hitrosti stiskanja, zip posku{a najti dalj{i ujemalni nizi, ~eprav je prvotni `e dovolj dolg.

  8. Ujemalni nizi s po~asnej{im ra~unskim mehanizmom niso uporabni za hitro stiskanje(izbira hitrosti -1 do -3). Pri tem hitrem stikanju, kadar ne najdemo ustreznega ujemalnega niza ali ta ni dovolj dolg, se v "hash" tabelo vrinejo novi nizi. To zmanj{a stiskalno razmerje, vendar se prihrani ~as, saj se zmanj{a iskanje in vrivanje ujemalnega niza.

Ujemalni niz je ve~ji ali enak niz (po dol`ini), ki se ujema z nekim predhodnim nizom.
NAPREJ NAZAJ STISKALNI PROGRAMI NA ZACETEK