LZW (for Lempel-Ziv-Welch ) is a algorithm of Data compression without loss. It is about an improvement of the algorithms LZ77 (1977) and LZ78 (1978), all the two writings by Abraham Lempel and Jacob Ziv. LZW was created in 1984 by Terry Welch, from where its name.

Algorithm LZW had been Brevet E by the company Unisys. It was used in the Modem S (standard V42 (a)) and is still used in the format of Digital image GIF and the files audio MOD.

Principle

• Initialization: a preset dictionary of words is filled.
• Reading:
• the entry is added to the plug a character at the same time As long as the plug contains words of the dictionary
• To the first character added to the plug such as the plug does not correspond to any word of the dictionary, one adds a word to the dictionary of the form has + B where has is a word of the dictionary and B a character, has left the plug and returned.
• Fine of the entry: the plug is returned if it is not empty (it corresponds to a word of the dictionary).

Let us note that the binary codes first of all are generally emitted on 8 bits, until these 8 bits are not enough any more to code the index which one wishes (for example the index 256, qu ' it is necessary to code on 9 bits). One emits index 0 then to mean that one increases the number of emitted bits by 1.

Let us take an example. Let us suppose that the sentence to be coded is “repetition”. With each letter is associated its code ASCII. The dictionary is initialized and associates index 1 with the code “0”, index 2 with the code “1” ..... etc until the index 256 which corresponds to the code “255”.

• At the beginning of compression, the binary codes will be emitted on 8 bits.

• At stage 1, one charges in the plug the first 2 characters. This continuation is not present in the dictionary, therefore it is added. One then emits on 8 bits the code “115” (because the code “114”, R in ASCII, have as an index “115” in the dictionary) and one removes plug the emitted characters.
• At stage 7, the chain “116 ' + ' 105” being already present in the dictionary (index 261), one emits the code “0” because 261 cannot be coded on 8 bits, it requires a minimum of 9 bits. The emitted codes from now on will thus be emitted on 9 bits.
• At stage 8, one charges a new character in the plug. The chain is not present in the dictionary, therefore it is added. One emits then the index of the chain “116 ' + ' 105” (261) and one removes it dictionary.
• the following stages follow logically.

Associated programs

• "lha.exe" under DOS.
• 7-zip .

External bond

• Comparative of the performances of various methods of compression of files

References