How Computers Shrink Data by Finding Repeated Patterns

The patent details a system for compressing "data character signals" (Claim 1). First, it builds a "string table" (Claim 1) that stores sequences of characters it has seen before. When processing new data, it searches for the "longest match" (Claim 1) between the incoming data and the strings already in its table. Once the longest match is determined, the system sends a short "code signal" (Claim 1) representing that matched string instead of the actual characters. It then adds a new, slightly longer string to its table, formed by taking the "longest match" and adding the very next character from the input data (Claim 1). For example, if the input is "banana" and "ban" is the longest match, it sends the code for "ban" and then adds "bana" to its table. Decompression works by receiving these codes and rebuilding a similar string table to translate the codes back into the original character sequences.

The clever bit

The core innovation is the dynamic creation of a dictionary (the "string table") on the fly, where frequently occurring sequences of characters are identified and replaced with shorter codes. This adaptive approach, combined with efficiently searching and updating the dictionary using a "limited search hashing procedure" (Abstract, Claim 5), allows for effective compression without needing a pre-defined dictionary.

What it does not cover

• ×Compression methods that do not use a "string table" to store encountered data character signals (Claim 1).
• ×Compression methods that do not search for the "longest match" between input data and stored strings (Claim 1).
• ×Compression methods that do not assign a unique "code signal" to each stored string for transmission (Claim 1).
• ×Compression methods that do not build an "extended string" by adding the next character to the longest match (Claim 1).
• ×Compression methods that do not involve "data character signals" (Claim 1), implying it's not for raw binary data without character interpretation.