# 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. - **Patent:** US 4558302 - **Original title:** High speed data compression and decompression apparatus and method - **Owner:** Sperry Corp - **Granted:** 1985 - **Status:** Public domain (expired) - **Times cited:** 347 - **Field:** software, telecommunications, consumer_electronics ## What it does 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 does NOT 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. ## Real-world examples 1. ZIP file compression 2. GZIP compression 3. PNG image compression 4. Lempel-Ziv-Welch (LZW) algorithm implementations ## 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. ## Frequently asked questions ### What does How Computers Compress Data Using Dictionary Building cover? 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. ### Who owns patent US 4558302? Sperry Corp owns this patent, granted in 1985. ### When does this patent expire? This patent has expired and is now in the public domain — anyone can use the invention freely. ### What is patent US 4558302 cited by? This patent has been cited by 347 later patents that build on its ideas. ### What problem does this patent solve? 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. ### What does this patent NOT cover? Data compression that doesn't involve building a dictionary of previously seen strings. **Full plain-English explainer:** https://patentbrief.org/patent/us/4558302/lzw-compression **Original patent:** https://patents.google.com/patent/US4558302 --- _Source: PatentBrief — https://patentbrief.org. Patent facts are from public records; the plain-English explanation is PatentBrief's._ ## Related patents Semantically similar inventions in the PatentBrief corpus: - [How Computers Find Similar Text Using Compact Data Structures](https://patentbrief.org/patent/us/10878335/bert-bidirectional-encoder-representations) — This patent describes a method for efficiently identifying similar text records, like documents or product reviews, by using special compact data structures that store text terms probabilistically and then analyzing them with machine learning. - [How Digital Audio Compression Works](https://patentbrief.org/patent/us/5579430/digital-encoding-process) — A foundational method for compressing digital audio by transforming sound into spectral data and using variable-length codes to store it efficiently. - [How Multiple Computers Share a Network Cable Without Crashing](https://patentbrief.org/patent/us/4063220/ethernet-packet-network) — This patent describes how multiple computers can share a single communication cable by listening for other transmissions and stopping their own if a collision occurs, then trying again later. - [How to Create a Secret Code Key Without Meeting First](https://patentbrief.org/patent/us/4200770/diffie-hellman-public-key-exchange) — This 1980 patent describes a way for two people to create a secret code key over a public channel, like the internet, without ever meeting or sharing the key directly. - [How Modems Use Guard Time to Switch Between Data and Commands](https://patentbrief.org/patent/us/4549302/hayes-modem-escape-sequence) — This patent describes a method for modems to safely switch from sending data to accepting commands without accidentally triggering that switch while transmitting normal files.