HetLZW- ofLemple-Ziv-Welch-algoritme is een exact omkeerbaarcompressie-algoritme dat doorAbraham Lempel,Jacob Ziv enTerry 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 eencode.
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-vrijebestandsindelingen zoalsGIF, omdat het algoritmegepatenteerd was. Het Amerikaanse patent liep echter af op 20 juni 2003, en in de loop van 2004 verliepen deCanadese,Europese enJapanse patenten. Tegenwoordig wordt LZW vaak gebruikt voor het comprimeren van digitaletopografische kaarten inGeoTIFF-bestanden.
Het LZW-algoritme gebruikt een zogenaamd 'woordenboek' om het bestand tecomprimeren. In plaats van zoals bijHuffman-compressie de tekens afzonderlijk te hercoderen, houdt dit algoritme een lijst bij (het 'woordenboek') van bepaaldetekenreeksen (strings). Hetalgoritme begint met een 'woordenboek' van 256 tekens, deASCII-tabel. Tijdens het comprimeren zal deze tabel aangroeien met allestrings 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 alleindices die een macht van 2 zijn (2n).
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.
Eenopensource-opvolger van LZW isLZMA wat staat voorLempel-Ziv-Markov chain-Algorithm. Een van de programma's die daarop zijn gebaseerd is7-Zip. Het heeft een hogere compressiefactor dan bijvoorbeeldWinZip.