Lempel Ziv Welch

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 bekend staat als 'LZW' of 'LZ78'. Het algoritme werkt volgens het principe dat veel voorkomende tekenreeksen worden vervangen door een code.

Het LZW-algoritme was ten tijde van de uitvinding het effectiefste compressie-algoritme dat er bestond. Voor enkele tientallen jaren bleef het gebruik beperkt tot een aantal niet-vrije bestandsindelingen zoals GIF, omdat het algoritme gepatenteerd was. Het Amerikaanse patent liep echter af op 20 juni 2003, en in de loop van 2004 verliepen de Canadese, Europese en Japanse patenten. Tegenwoordig wordt LZW vaak gebruikt voor het comprimeren van digitale topografische kaarten in GeoTIFF-bestanden.

Details

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 tekenreeksen (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 (2ⁿ).

Bij het LZW-algoritme is het niet nodig een woordenboek toe te voegen aan het gecomprimeerde bestand. Het impliciete woordenboek van de ASCII-tabel 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 twee bytes codes ingelezen. De eerste code komt uit de ASCII-tabel en kunnen we onmiddellijk decoderen.

Opvolgers

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