Wikiversity
Lempel–Ziv (LZ) algoritmit ovat yksi tunnetuimmista ja suosituimmista menetelmistä tiedon häviöttömälle pakkaukselle.
Menetelmä
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
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
Lähteet
- ↑ 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
- A Technique for High-Performance Data Compression (englanniksi)
- Lecture 7: Supplemental notes on LZ77 (PDF) (englanniksi)
| ||||||||||||||||||
