How Computers Compress Data Using Dictionary Building

This 1985 patent describes a method for making computer files smaller by building a dictionary of common data patterns and replacing them with shorter codes.

What it covers

This patent details a system that shrinks data, like text or files, making them take up less space. It works by reading through the data and building a 'dictionary' of frequently occurring sequences of characters, called strings. When it finds a string in the data that's already in its dictionary, it replaces that string with a short code. If it finds a string that's not quite in the dictionary but is close, it adds a new, longer string to the dictionary. This new string is made up of the longest matching string it found and the very next character in the data. The system uses a clever 'hashing' technique to quickly search its dictionary for matches. To get the original data back, a separate 'decompressor' uses the same dictionary-building logic to reconstruct the data from the codes.

What it doesn't cover

• —Data compression that doesn't involve building a dictionary of previously seen strings.
• —Compression methods that don't use a 'longest match' strategy to find patterns.
• —Systems that don't use a hashing function to speed up dictionary lookups.
• —Decompression methods that don't reconstruct the dictionary in a similar way to the compressor.
• —Compression that doesn't extend a matched string with the next input character to create a new dictionary entry.

The clever bit

The innovation lies in dynamically building the dictionary on the fly. Instead of needing a pre-defined dictionary, the compressor learns the data's patterns as it goes, creating new dictionary entries from the longest match found plus the next character. This adaptive approach makes it highly effective for a wide variety of data.

Why it matters

This patent is a foundational piece for modern data compression techniques. The concepts it lays out, particularly dictionary-based compression using algorithms like Lempel-Ziv (which this patent is related to), are the basis for widely used compression formats like ZIP, GZIP, and PNG images. It enabled more efficient storage and faster transmission of digital information.

Real-world examples

• 1.ZIP file compression
• 2.GZIP compression
• 3.PNG image compression
• 4.Lempel-Ziv-Welch (LZW) algorithm implementations