Dictionary Compression

Dictionary compression is a lossless compression method. It searches the data for patterns that repeat, stores each pattern once in a dictionary, and replaces every occurrence with a short code. A pattern can be any length, from a few characters to a whole word. The dictionary is stored with the compressed data, so a decompressor can swap each code back for its pattern and rebuild the original exactly, with nothing lost.

Worked example

A text file contains the repeated pattern:

abcabcabcabc

The pattern abc appears four times. The compressor stores abc once in the dictionary as code 1, and the data becomes 1 1 1 1. The original is 12 characters, so 12 bytes with one byte per character. The compressed version needs 3 characters for the dictionary entry plus 1 byte for each of the four codes, which is 7 bytes, so the file is smaller. To decompress, each code 1 is swapped back for abc, giving the original string.

When it helps

Dictionary compression works best when the data contains lots of repeated patterns, because one dictionary entry can then serve many codes. If there is very little repetition, the dictionary and codes can take up as much space as the original, so the file may not get smaller at all. Dictionary compression is lossless, but it does not always reduce file size.