How to use the lzw compression stepper
- Choose Encode text to compress, or Decode codes to expand a list of numbers.
- To encode, enter the text. It is read as UTF-8 bytes and up to 2,000 bytes are accepted.
- To decode, enter numbers from 0 to 4095 separated by spaces or commas.
- Read the codes sent, the size comparison and the step table showing the prefix, the next byte, the code sent and the new dictionary entry.
Formula
start with entries 0 to 255, one for each byte
keep the longest known prefix w; read byte c
if w + c is known, w = w + c; otherwise send the code of w, add w + c as the next entry and set w = c
The decoder rebuilds the same dictionary from the codes. A code may name the entry the encoder added just before sending it; that entry is the previous text plus its own first byte.
TOBEORNOTTOBEORTOBEORNOT
The 24 bytes become 16 codes: 84 79 66 69 79 82 78 79 84 256 258 260 265 259 261 263. The first nine codes are single letters, and the later ones name phrases built earlier, such as TO (256), BE (258), OR (260) and BEO (265).
At 12 bits per code the output needs 192 bits, exactly the same as the 24 bytes x 8 = 192 bits of the input, so this short text does not shrink at all. Longer text with repeats is where the method pays off. The input aaaaaaa gives 97 256 257 97.
Where LZW is used
Lempel-Ziv-Welch coding appears in the GIF and TIFF image formats and in older compression tools. It needs no table sent along with the data, because the decoder builds the same table. That is its main advantage over the code tables of the Huffman Coding Calculator.
Real formats vary the code width as the dictionary grows, and have special codes to clear the table. This page uses a fixed 12 bit width as an example and stops adding entries when the dictionary reaches 4,096. For other ways of writing binary data as text, see the Base64 Encoder and Decoder.
The repeated string case
For aaaaaaa the encoder sends 97, then 256 for aa, then 257 for aaa. When the decoder reads 256 it has not yet built entry 256, but it knows the entry must be a followed by the first letter of itself, which is aa. The decoding test, 97 256 257 258 giving ten a letters, covers exactly this case.
Assumptions and limits
- Input text is converted to UTF-8 bytes, so accented letters and emoji take more than one byte.
- A space is drawn as a visible symbol in the table, and unreadable bytes as \x and two hex digits.
- The size comparison assumes 12 bits for every code, an example width.
- Only the first 60 steps are shown; the codes list is complete.
- Decoding stops with a message if a code is not in the dictionary yet or the first code is not a single byte.
Frequently asked questions
Why did my short text not get smaller?
Each code takes 12 bits in the comparison, more than the 8 bits of a plain byte. A text has to repeat enough for the longer phrases to repay that.
Why does decoding sometimes use a code I have not seen?
The encoder adds an entry and may use it at once. The decoder builds it one step later, so it works the entry out from the previous text.
Is LZW the same as ZIP?
No. ZIP files usually use a different method, called Deflate. LZW is an older relative from the same family.
Can I decode codes from a GIF file?
Not directly. GIF packs variable width codes and clear codes into blocks, which this page does not read.