US5229768A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Adaptive data compression system
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1992-01-29
•
Granted: 1993-07-20
•
Expires: 2012-01-29
Abstract
Abstract A system for data compression and decompression is disclosed. A series of fixed length overlapping segments, called hash strings, are formed from an input data sequence. A retrieved character is the next character in the input data sequence after a particular hash string. A hash function relates a particular hash string to a unique address in a look-up table (LUT). An associated character for the particular hash string is stored in the LUT at the address. When a particular hash string is considered, the content of the LUT address associated with the hash string is checked to determine whether the associated character matches the retrieved character following the hash string. If there is a match, a Boolean TRUE is output; if there is no match, a Boolean FALSE along with the retrieved character is output. Furthermore, if there is no match, then the LUT is updated by replacing the associated character in the LUT with the retrieved character. The process continues for each hash string until the entire input data sequence is processed. The method of decompression includes the steps of initializing a decompression LUT to mirror the initial compression LUT and receiving a representational form output from the compressor. The representational form is generally analyzed one character at a time. If the character is a Boolean TRUE, then the content of the LUT addressed by the most recently decoded hash string is output. Otherwise, if the character is a Boolean FALSE, the next character (exception character) in the representational form is output and the content of the LUT addressed by the most recently decoded hash string is output.
Inventors
- 👤 Kasman E. Thomas
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 19:01
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/3084; H03M7/3088; G; G06; G06T; G06T9/00; G06T9/005
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
180 words
An adaptive data compression method for compressing an input data sequence comprised of a plurality of sequential discrete characters, said method comprising the steps of: (a) forming a current hash string by sequentially retrieving from said input data sequence a predetermined number of characters, said current hash string having an associated character; (b) retrieving a retrieved character, said retrieved character sequentially following said current hash string in said input data sequence; (c) comparing said retrieved character to said current hash string's associated character: (i) if said retrieved character matches said current hash string's associated character, outputting a match indicator; and (ii) if said retrieved character does not match said current hash string's associated character, outputting both a no-match indicator and said retrieved character as an exception character and associating said retrieved character with said current hash string; (d) forming a new hash string having said predetermined number of characters and including said retrieved character, said new hash string having an associated character; (e) assigning said new hash string as said current hash string; and (f) repeating steps (b) through (e).
Claim 2
Dependent Claim
180 words
An adaptive data compression method for compressing an input data sequence comprised of a plurality of sequential discrete characters, said method comprising the steps of: (a) forming a current hash string by sequentially retrieving from said input data sequence a predetermined number of characters, said current hash string having an associated character; (b) retrieving a retrieved character, said retrieved character sequentially following said current hash string in said input data sequence; (c) comparing said retrieved character to said current hash string's associated character: (i) if said retrieved character matches said current hash string's associated character, outputting a match indicator; and (ii) if said retrieved character does not match said current hash string's associated character, outputting both a no-match indicator and said retrieved character as an exception character and associating said retrieved character with said current hash string; (d) forming a new hash string having said predetermined number of characters and including said retrieved character, said new hash string having an associated character; (e) assigning said new hash string as said current hash string; and (f) repeating steps (b) through (e).
Claim 3
Dependent Claim
27 words
The method of claim 1, wherein said step of repeating steps (b) through (e) is repeated until no more characters are present in said input data sequence.
Claim 4
Dependent Claim
37 words
The method of claim 1, wherein said step of forming a new hash string includes the step of concatenating said retrieved character to said current hash string and deleting the first character of said current hash string's.
Claim 5
Dependent Claim
49 words
The method of claim 1, further including the step of forming a hash table in a memory device, said hash table for storing said associated characters, said hash table comprising a plurality of memory slots for storing said associated characters, each of said memory slots having a memory address.
Claim 6
Dependent Claim
77 words
The method of claim 4, wherein said step of comparing said retrieved character includes the steps of: generating a memory slot address by performing a hash function on said current hash string; looking-up said current hash string's associated character at said memory slot address; and if said retrieved character does not match said current hash string's associated character, associating said retrieved character with said current hash string by storing said retrieved character at said memory slot address.
Claim 7
Dependent Claim
27 words
The method of claim 4, wherein an initial associated character is stored in each of said memory slots prior to said step of comparing said retrieved character.
Claim 8
Dependent Claim
22 words
The method of claim 4, wherein the output of step (c) is written to a compressed data file in said memory device.
Claim 9
Dependent Claim
23 words
The method of claim 1, wherein said match indicator is a Boolean TRUE bit and said no-match indicator is a Boolean FALSE bit.
Claim 10
Dependent Claim
14 words
The method of claim 1, wherein said hash strings are two characters in length.
Claim 11
Dependent Claim
14 words
The method of claim 1, wherein said hash strings are three characters in length.
Claim 12
Dependent Claim
144 words
The method of claim 7, further comprising the steps of decompressing said compressed input data by: (a) outputting a current decompression output hash string equivalent to said current hash string of step (a) of claim 1, said current decompression output hash string having an associated character; (b) retrieving a next sequential character from said compressed data file; and (i) if a match indicator is retrieved, outputting said current decompression output hash string's associated character; and (ii) if a no-match indicator is retrieved, retrieving and outputting said next sequential exception character from said compressed data file and associating said exception character to said current decompression output hash string; (c) forming a new decompression output hash string including said character output at step (b); (d) assigning said new decompression output hash string as said current decompression output hash string; and (e) repeating steps (b) through (d).
Claim 13
Dependent Claim
22 words
The method of claim 11, wherein said step (e) is repeated until no more characters are remaining in said compressed data file.
Claim 14
Dependent Claim
41 words
The method of claim 11, wherein said step of forming a new decompression output hash string includes the step of concatenating said retrieved character to said current decompression output hash string and deleting said current decompression output hash string's first character.
Claim 15
Dependent Claim
36 words
The method of claim 11, further including the step of forming a decompression hash table for storing said associated characters, said decompression hash table comprising a plurality of decompression memory slots for storing said associated characters.
Claim 16
Dependent Claim
155 words
The method of claim 2 further comprising the steps of decompressing said input data by: (a) forming a current output hash string identical to the current hash string of step (a) of claim 1; (b) outputting said current output hash string, said current output hash string having an associated character; (c) receiving the next match indicator or no match indicator; and (i) if a match indicator is received, outputting said current output hash string's associated character; and (ii) if a no-match indicator is received, receiving and outputting a next sequential exception character and associating said exception character to said current output hash string; (d) forming a new output hash string by deleting said current output hash string's first character and concatenating the last character output; (e) assigning said new output hash string as said current output hash string; and (f) repeating steps (c) through (e) until no more match indicators or no-match indicators are received.
Claim 17
Dependent Claim
52 words
The method of claim 15, further including the step of forming a decompression hash table in a memory device, said decompression hash table for storing said associated characters, said decompression hash table comprising a plurality of memory slots for storing said associated characters, each of said memory slots having a memory address.
Claim 18
Dependent Claim
139 words
A data compressor for compressing an input data sequence comprised of a plurality of sequential discrete characters, the data compressor comprising: (a) an input component for receiving an input data sequence; (b) processor means for: (i) forming a current hash string by sequentially retrieving from said input data sequence a predetermined number of characters, said current hash string having an associated character; (ii) retrieving and comparing a retrieved character, said retrieved character next sequentially following said current hash string in said input data sequence, to said current hash string's associated character; and (iii) outputting a match indicator if said retrieved character matches said associated character; and outputting both a no-match indicator and said retrieved character as an exception character if said retrieved character does not match said associated character and associating said retrieved character with said current hash string.
Claim 19
Dependent Claim
139 words
A data compressor for compressing an input data sequence comprised of a plurality of sequential discrete characters, the data compressor comprising: (a) an input component for receiving an input data sequence; (b) processor means for: (i) forming a current hash string by sequentially retrieving from said input data sequence a predetermined number of characters, said current hash string having an associated character; (ii) retrieving and comparing a retrieved character, said retrieved character next sequentially following said current hash string in said input data sequence, to said current hash string's associated character; and (iii) outputting a match indicator if said retrieved character matches said associated character; and outputting both a no-match indicator and said retrieved character as an exception character if said retrieved character does not match said associated character and associating said retrieved character with said current hash string.
Claim 20
Dependent Claim
68 words
A data compressor as claimed in claim 17, wherein said processor means further includes means for forming a new hash string having said predetermined number of characters and by concatenating said retrieved character to said current hash string and deleting a first character from said current hash string, and for assigning said new hash string as said current hash string, and for analyzing said entire input data sequence.
Claim 21
Dependent Claim
39 words
The compressor of claim 17, further including a memory device in which a hash table is established, said hash table comprising a plurality of memory slots for storing associated characters, each of said memory slots having a memory address.
Claim 22
Dependent Claim
69 words
The compressor of claim 17, wherein said means for comparing a retrieved character to said current hash string's associated character performs a hash function on said hash string to derive a memory slot address and compares said associated character at said memory slot address to said retrieved character and further associates said retrieved character with said current hash string by storing said retrieved character in said memory slot address.
References Cited (Backward Citations)
US3914586A
Cited
US4464650A
Cited
US4491934A
Cited
US4814746A
Cited
US4558302A
Cited
US4558302B1
Cited
US4612532A
Cited
US4872009A
Cited
US4899148A
Cited
US4876541A
Cited
US4881075A
Cited
US4870415A
Cited
US4847619A
Cited
US5049881A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-07-19 | 1997-01-18 | 1997-07-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-07-19 | 2001-01-18 | 2001-07-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-07-19 | 2005-01-18 | 2005-07-20 | $7700.00 | Window Closed / Lapsed |