Lempel-Ziv
Lempel–Ziv (LZ) algoritmit ovat yksi tunnetuimmista ja suosituimmista menetelmistä tiedon häviöttömälle pakkaukselle.
Menetelmä
[muokkaa | muokkaa wikitekstiä]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, jolloin sitä ei tarvitse erikseen määritellä, ja sanasto päätellään purkamisen yhteydessä.[3] Lempel-Ziv-Welch (LZW) on Terry Welchin vuonna 1984 kehittämä muunnos LZ78-pakkauksesta. LZW on kuvattu artikkelissa A technique for high performance data compression IEEE Computer -lehdessä.[4] Welch ehdotti muutoksia sanaston käsittelyyn ja sanaston indekseinä käytettäviin koodisanoihin.[5]
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]
Vaikutus
[muokkaa | muokkaa wikitekstiä]Lempel-Ziv algoritmi on nimetty IEEE:n merkkipaalujen (engl. milestone) listalla.[6] Lempel-Ziv-Welch (LZW) -muunnelma on pahamaineinen Unisysin vuonna 1994 hakeman patentin johdosta. Unisys haki patenttia, kun LZW:tä käyttävä GIF oli jo laajalti käytössä internetissä esitetyssä sisällössä. Viimeinen LZW:tä koskeva patentti vanheni vuonna 2004.[7]
Katso myös
[muokkaa | muokkaa wikitekstiä]Lähteet
[muokkaa | muokkaa wikitekstiä]- ↑ a b Lempel-Ziv Compression Algorithm ethw.org. Viitattu 25.2.2017.
- ↑ Lempel-Ziv (PDF) math.mit.edu. Arkistoitu 28.5.2021. Viitattu 6.10.2020. (englanniksi)
- ↑ Brad Karp: Lempel-Ziv-Welch Compression .cs.ucl.ac.uk. 5.2.2019. Viitattu 3.4.2024. (englanniksi)
- ↑ Details for: Graphics Interchange Format 87a nationalarchives.gov.uk. Viitattu 3.4.2024. (englanniksi)
- ↑ Debra A. Lelewer & Daniel S. Hirschberg: 5.1 Lempel-Ziv Codes ics.uci.edu. Viitattu 3.4.2024. (englanniksi)
- ↑ Milestones:Lempel-Ziv Data Compression Algorithm, 1977 ethw.org. Viitattu 25.2.2017.
- ↑ LZW Compression Encoding loc.gov. Viitattu 3.4.2024. (englanniksi)
Aiheesta muualla
[muokkaa | muokkaa wikitekstiä]- A Technique for High-Performance Data Compression (englanniksi)
- Lecture 7: Supplemental notes on LZ77 (PDF) (englanniksi)