{
  "patent_number": "US 4558302",
  "country": "US",
  "title": "How Computers Compress Data Using Dictionary Building",
  "original_title": "High speed data compression and decompression apparatus and method",
  "summary": "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_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."
  ],
  "filed": "1983-06-20",
  "granted": "1985-12-10",
  "expires": "2003-06-20",
  "status": "expired",
  "holder": "Sperry Corp",
  "holder_url": "https://patentbrief.org/company/sperry-corp",
  "inventors": [
    {
      "name": "Terry A. Welch",
      "url": "https://patentbrief.org/inventor/terry-a-welch"
    }
  ],
  "times_cited": 347,
  "tags": [
    "software",
    "telecommunications",
    "consumer_electronics"
  ],
  "abstract": "A data compressor compresses an input stream of data character signals by storing in a string table strings of data character signals encountered in the input stream. The compressor searches the input stream to determine the longest match to a stored string. Each stored string comprises a prefix string and an extension character where the extension character is the last character in the string and the prefix string comprises all but the extension character. Each string has a code signal associated therewith and a string is stored in the string table by, at least implicitly, storing the code signal for the string, the code signal for the string prefix and the extension character. When the longest match between the input data character stream and the stored strings is determined, the code signal for the longest match is transmitted as the compressed code signal for the encountered string of characters and an extension string is stored in the string table. The prefix of the extended string is the longest match and the extension character of the extended string is the next input data character signal following the longest match. Searching through the string table and entering extended strings therein is effected by a limited search hashing procedure. Decompression is effected by a decompressor that receives the compressed code signals and generates a string table similar to that constructed by the compressor to effect lookup of received code signals so as to recover the data character signals comprising a stored string. The decompressor string table is updated by storing a string having a prefix in accordance with a prior received code signal and an extension character in accordance with the first character of the currently recovered string.",
  "url": "https://patentbrief.org/patent/us/4558302/lzw-compression",
  "markdown_url": "https://patentbrief.org/patent/us/4558302/lzw-compression/md",
  "google_patents_url": "https://patents.google.com/patent/US4558302",
  "relatedPatents": [
    {
      "patentNumber": "10878335",
      "countryCode": "US",
      "title": "How Computers Find Similar Text Using Compact Data Structures",
      "url": "https://patentbrief.org/patent/us/10878335/bert-bidirectional-encoder-representations"
    },
    {
      "patentNumber": "5579430",
      "countryCode": "US",
      "title": "How Digital Audio Compression Works",
      "url": "https://patentbrief.org/patent/us/5579430/digital-encoding-process"
    },
    {
      "patentNumber": "4063220",
      "countryCode": "US",
      "title": "How Multiple Computers Share a Network Cable Without Crashing",
      "url": "https://patentbrief.org/patent/us/4063220/ethernet-packet-network"
    },
    {
      "patentNumber": "4200770",
      "countryCode": "US",
      "title": "How to Create a Secret Code Key Without Meeting First",
      "url": "https://patentbrief.org/patent/us/4200770/diffie-hellman-public-key-exchange"
    },
    {
      "patentNumber": "4549302",
      "countryCode": "US",
      "title": "How Modems Use Guard Time to Switch Between Data and Commands",
      "url": "https://patentbrief.org/patent/us/4549302/hayes-modem-escape-sequence"
    }
  ]
}