LZ77

Allikas: Vikipeedia

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

LZ[muuda | redigeeri lähteteksti]

Algoritm on iseenesest väga lihtne ja lihtsustatud variant näeks välja järgmine:

  1. Loe sisendandmed.
  2. Kas seda on juba esinenud libisevas aknas.
  3. Kui pole, siis kirjuta väljundisse.
  4. Kui on, siis kirjuta kaugus ja kokkulangevuse pikkus.
  5. 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.

Näide[muuda | redigeeri lähteteksti]

Võttes libiseva akna pikkuseks 4 KB. Sellisel juhul oleks mõistlik kauguse ja pikkuse paar kodeerida järgmiselt:

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

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 see 24 bitti sisse ja 16+1 bitti väljundisse. Kui aga tulemus on väiksem, 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.

Vaata ka[muuda | redigeeri lähteteksti]

Välislingid[muuda | redigeeri lähteteksti]