Lempel Ziv Welch

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Het LZW of Lemple-Ziv-Welch-algoritme is een exact omkeerbaar compressie-algoritme dat door Abraham Lempel, Jacob Ziv en Terry Welch is uitgevonden. Lempel en Ziv hadden in 1977 een eerdere variant (LZ77) ontwikkeld en samen met Welch werd in 1984 een verbeterde versie gemaakt die nu bekendstaat als 'LZW' of 'LZ78'. Het algoritme werkt volgens het principe dat veelvoorkomende tekenreeksen worden vervangen door een code.

Het LZW-algoritme was ten tijde van de uitvinding het meest effectieve compressie-algoritme dat er bestond. Het wordt tegenwoordig vrijwel alleen nog in een aantal niet-vrije bestandsindelingen zoals GIF gebruikt omdat het algoritme gepatenteerd was. Het Amerikaanse patent is echter afgelopen op 20 juni 2003, in de loop van 2004 verliepen de Canadese, Europese en Japanse patenten. LZW wordt vaak gebruikt voor het comprimeren van digitale topografische kaarten in GeoTiff-bestanden.

Details[bewerken]

Het LZW-algoritme gebruikt een zogenaamd 'woordenboek' om het bestand te comprimeren. In plaats van zoals bij Huffman-compressie de tekens afzonderlijk te hercoderen, houdt dit algoritme een lijst bij (het 'woordenboek') van bepaalde reeksen van tekens (strings). Het algoritme begint met een 'woordenboek' van 256 tekens, de ASCII-tabel. Tijdens het comprimeren zal deze tabel aangroeien met alle strings die frequent in het bestand voorkomen. Zo ontstaat er echter een probleem: als er meer dan 256 tekens zijn, hoe kunnen wij deze dan allemaal coderen in 8 bits? Dit probleem wordt gemakkelijk opgelost door vanaf index 256 een code met 9 bits te gebruiken, vanaf 512 10 bits, vanaf 1024 11 bits en zo verder met alle indices die een macht van 2 zijn (2n).

Bij het LZW-algoritme is het NIET nodig een woordenboek toe te voegen aan het gecomprimeerde bestand. In elk systeem zit een ASCII-tabel verwerkt en dit is het enige dat nodig is om het gegeven bestand te kunnen decomprimeren. Het algoritme om te comprimeren wordt eigenlijk omgekeerd uitgevoerd. Er worden eerst 2 bytes codes ingelezen. De eerste code komt uit de ASCII-tabel en kunnen we onmiddellijk decoderen.

Opvolgers[bewerken]

Een opensource-opvolger van LZW is LZMA wat staat voor Lempel-Ziv-Markov chain-Algorithm. Eén van de programma's die daarop zijn gebaseerd is 7-Zip. Het heeft een hogere compressiefactor dan bijvoorbeeld WinZip.