LZ77
| Vajab toimetamist |
LZ77 ja LZ78 on andmete kadudeta pakkimise algoritmid. Algoritmid avaldasid Abraham Lempel ja Jacob Ziv aastatel 1977 ja 1978. Tänapäeval enamus pakkimisalgoritme põhinevad LZ variatsioonil. Tuntumad neist on LZW, LZSS ja LZMA. LZ77 algoritm kasutab libiseva akna tehnikat.
[redigeeri] LZ
Algoritm on iseenesest vaga lihtne ja lihtsustatud variant näeks välja järgmine:
- Loe sisendandmed.
- Kas seda on juba esinenud libisevas aknas.
- Kui pole, siis kirjuta väljundisse.
- Kui on, siis kirjuta kaugus ja kokkulangevuse pikkus.
- Alusta uuesti niikaua kuni andmed otsas.
Libisev aken on siis kas 4 KB, 32 KB või selline, mida algoritm suudab hallata. Ehk siis näitab see, kui pikk mälu pakkijal on andmete meeles pidamiseks. 2 punktis ongi see koht, kus kontrollitakse, kas sisendandmetega on kattuvus juba eelnevalt nähtuga.
[redigeeri] Näide
Võttes libiseva akna pikkuseks 4 KB. Sellisel juhul oleks mõistlik kauguse ja pikkuse paar kodeerida järgmiselt:
Kokkuvõttes annab see 12+4=16 bitti ehk 2 baiti. Lisaks tuleb kasutada ära veel 8 bitti ehk 1 bait ära selleks, et märkida kas meil on tegemist kaugus-pikkus paariga või mitte. Kokku teeb see 3 baiti. Seega miinimum kattuvuse pikkus peaks olema 3 baiti. Kokkuvõttes annab 24 bitti sisse ja 16+1 bitti väljundisse. Kui aga väiksem on, siis väljundis on andmed lõppkokkuvõttes suuremad. Näiteks 2 baidi puhul tuleb ära kasutada 16 bitti kaugus-pikkus paarile ja 1 bitt märkimaks, kas tegu on kaugus-pikkus paariga. Kokku siis 17 bitti, mis on suurem kui 16 bitti (2 baiti). Samuti lähtudes sellest võiks kattuvuse pikkus olla 3 võrra pikem 1-15 ehk 4-18.
