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

It is the algorithm of the widely used Unix file compression utility compress and is used in the GIF image format.

Algorithm

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.

Example

TOBEORNOTTOBEORTOBEORNOT#

Dict

Encoding

Dict

Decoding

Dict