Lempel–Ziv–Welch (LZW) is a universal lossless data compression algorithm created by Abraham Lempel, Jacob Ziv, and Terry Welch. It was published by Welch in 1984 as an improved implementation of the LZ78 algorithm published by Lempel and Ziv in 1978. The algorithm is designed to be fast to implement but is not usually optimal because it performs only limited analysis of the data.

The algorithm takes a string as input. It processes the string using a Dictionary.The string is encoded (and the dictionary grows) as the string is being processed. Initially, the dictionary contains all the possible characters (the alphabet) with their corresponding encoding.

The algorithm takes the longest word w (from the dictionary) that can replace the next characters in the string. It encodes this part of the string with the encoding of w. Now it takes the character c that followed w in the string, and adds wc to the dictionary.

This repeats until the string is consumed. The idea is that, as the string is being processed, we populate the dictionary with longer strings, allowing encoding of bigger chunks of the string at each replacement. The compressor algorithm builds a string translation table from the text being compressed.

The string translation table maps fixed-length codes (usually 12-bit) to strings. The string table is initialized with all single-character strings (256 entries in the case of 8-bit characters). As the compressor character-serially examines the text, it stores every unique two-character string into the table as a code/character concatenation, with the code mapping to the corresponding first character.

As each two-character string is stored, the first character is sent to the output. Whenever a previously-encountered string is read from the input, the longest such previously-encountered string is determined, and then the code for this string concatenated with the extension character (the next character in the input) is stored in the table. The code for this longest previously-encountered string is output and the extension character is used as the beginning of the next word.

Similar to 0 things you like: