Lempel-Ziv-Welch

October 30, 2018

LZW is a compression algorithm that the file "ZIP" is based upon. It is a lossless data algorithm, means it loses no data, created by Abraham Lempel, Jacob Ziv, and Terry Welch. It is also used in the GIF image format.

The algorithm follows five steps:

1. Initialize the dictionary to contain all strings of length one.

2. Find the longest string W in the dictionary that matches the current input.

3. Emit the dictionary index for W to output and remove W from the input.

4. Add W followed by the next symbol in the input to the dictionary.

5. Go to Step 2.

It scans through the input string for successively longer substrings until it finds one that is not already in the dictionary. This process repeats itself over and over. This algorithm works best on repeated patterns, therefore larger file sizes. Therefore, as the message grows, the compression ratio maximizes. Decoding the algorithm is easy, as the dictionary is referred to to decode any information in the compressed version of the file. Therefore, the decoder and the encoder have identical dictionaries, but they're reversed, so just an initial dictionary is required.