Lempel-Ziv

Lempel–Ziv (LZ) algoritmit ovat yksi tunnetuimmista ja suosituimmista menetelmistä tiedon häviöttömälle pakkaukselle.

Algoritmin ovat kehittäneet Abraham Lempel ja Jacob Ziv. Algoritmin ensimmäiset versiot tunnetaan LZ77 ja LZ78 julkaisuvuosien 1977 ja 1978 perusteella (myös LZ1 ja LZ2).[1]

Lempel-Ziv algoritmi käyttää sanastoon perustuvaa pakkausta, jossa toistuvat jaksot korvataan viittauksilla sanastoon.[2] Jotta pakattu tieto voidaan palauttaa on sanasto tunnettava. Sanasto voi olla ennalta määritelty tai se voi seurata tiedon mukana. LZW-muunnos lisää sanaston dynaamisen luomisen pakattavasta tiedosta.

Pakkaustehoon vaikuttavia tekijöitä ovat mm. sanaston laajuus ja jaksojen pituus.

Menetelmän eri versioita ja muunnoksia:

  • Deflate
  • Lempel-Ziv-Welch (LZW)
  • Lempel-Ziv-Oberhumer (LZO)
  • Lempel-Ziv-Ross-Williams (LZRW)
  • Lempel-Ziv-Stac (LZS), myös Stac-pakkaus
  • Lempel-Ziv-Storer-Szymanski (LZSS)
  • Lempel-Ziv-Markov chain algorithm (LZMA)
  • Statistical Lempel–Ziv

Algoritmia käytetään yleisessä tiedostojen pakkauksessa sekä kuvadatan pakkauksessa kuten GIF ja PNG tiedostomuodot.[1]

Lempel-Ziv algoritmi on nimetty IEEE:n merkkipaalujen (engl. milestone) listalla.[3]

Katso myös

Lähteet
  1. Lempel-Ziv Compression Algorithm ethw.org. Viitattu 25.2.2017.
  2. Lempel-Ziv (PDF) math.mit.edu. Arkistoitu 28.5.2021. Viitattu 6.10.2020. (englanniksi) 
  3. Milestones:Lempel-Ziv Data Compression Algorithm, 1977 ethw.org. Viitattu 25.2.2017.
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.