LZW is the most commonly used dictionary scheme, and is patented by Welch at Unisys. |
It is adaptive and constructs the table while it is compressing (unlike the Huffman schemes, which compute the code table on one scan and compress on the next). |
An LZW compressor starts with a dictionary that has one entry for each single pixel value. For example, if the pixels are 8 bits, the original dictionary has 256 entries. Each time it sees a new sequence of inputs, it adds a new entry to the dictionary. If it sees a pattern that has been seen before, it uses a previous entry. |