LZ77

LZ77 ja LZ78 on andmete kadudeta pakkimise algoritmid. Algoritmid avaldasid Abraham Lempel ja Jacob Ziv aastatel 1977 ja 1978. Tänapäeval põhineb enamik pakkimisalgoritme LZ variatsioonil. Tuntumad neist on LZW, LZSS ja LZMA. LZ77 algoritm kasutab libiseva akna tehnikat.

LZ

Algoritm on lihtne, selle lihtsustatud variant näeb välja järgmine:

1. Loe sisendandmed;
2. Kontrolli, kas sisseloetu on juba esinenud libisevas aknas;
3. Kui pole, siis kirjuta väljundisse;
4. Kui on, siis kirjuta väljundisse kaugus ja kokkulangevuse pikkus;
5. Alusta uuesti kuni andmete lõppemiseni.

Libiseva akna suurus on kas 4 kB, 32 kB või selline, mida algoritm suudab hallata. See väljendab pakkijal andmete meelespidamiseks kasutatava mäluakna suurust. Algoritmi teises punktis kontrollitakse sisendandmete kattumist varem sisse loetud andmetega.

Näide

Libiseva akna pikkuseks võetakse 4 kB. Sel juhul on mõistlik kauguse ja pikkuse paar kodeerida järgmiselt:

1. 4 bitti pikkusele (15 baidi jagu).
2. 12 bitti kaugusele (4095 baidi ulatuses).

See on kokku 12+4=16 bitti ehk 2 baiti.

Lisaks tuleb kasutada veel 8 bitti ehk 1 bait selleks, et märkida, kas tegemist on kaugus-pikkuspaariga või mitte. Kokku teeb see 3 baiti. Seega vähima kattuvuse pikkus peab olema 3 baiti. Kokkuvõttes annab see 24 bitti sisse ja 16+1 bitti väljundisse. Väiksema tulemuse korral on väljundis andmed lõppkokkuvõttes suuremad. Näiteks 2 baidi puhul tuleb kasutada 16 bitti kaugus-pikkuspaarile ja 1 bitt märkimaks, kas tegu on kaugus-pikkuspaariga. Kokku 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.

Vaata ka

• Andmete pakkimine
• Huffmani kodeerimine
• ASCII

Välislingid

• Nimekiri LZ77 variatsioonidest