LZW

Lempel–Ziv–Welch (LZW) is a universal lossless data compression algorithm created by Abraham Lempel, Jacob Ziv, and Terry Welch.

Overview

It was published by Welch in 1984 as an improved implementation of the LZ78 (LZH) algorithm published by Lempel and Ziv in 1978. Its most important use is the popular GIF format and may also be used in the TIF format.

How it works

A dictionary of previous values are used for repeated data instead of reentering the data. A high level view of the encoding algorithm is shown here:

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.

For more information

• https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch
• Compression formats