Lempel Ziv Welch
Het LZW of Lemple-Zif-Welch algoritme is een exact omkeerbaar compressie-algoritme dat door de heren Abraham Lemple, Jacob Zif 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'. 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 is. Het Amerikaanse patent is echter afgelopen op 20 juni 2003, in de loop van 2004 verliepen de Canadese, Europese en Japanse patenten.
[bewerk] Details LZW algoritme
Het LZW-algoritme gebruikt een z.g. 'woordenboek' om het bestand te comprimeren. In plaats van zoals bij Huffman-compressie de tekens afzonderlijk te gaan hercoderen, gaat dit algoritme een lijst bijhouden (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.
[bewerk] Opvolgers
Een open source 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.
