US6320523B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for reducing the time required for compressing data
Assignee: Unisys Corp
•
Filing: 1999-07-30
•
Granted: 2001-11-20
•
Expires: 2019-07-30
Abstract
Abstract The present invention provides a novel method and system for obtaining maximum system speed performance for compressing coded data characters in a serial data stream by replacing strings of data with code values stored in a dictionary when strings are first observed as unique strings in the data stream. A novel pointer address is generated to represent new strings to be searched in the dictionary. The novel pointer address comprises a string code portion representative of the last matched string found in the dictionary and appended thereto an extension character code portion representative of the next character taken from the input data stream. The dictionary is constructed large enough to provide a unique memory location for every possible pointer address. The unique pointer address, representative of a string of data in the input data stream, is employed as an address pointer to access the memory. If no data is in memory at the address pointer the string has not been previously observed and a new unique compression code is stored at the pointer address in memory for the string so that the next identical pointer address will read the code for the string from the dictionary. Accordingly, every memory address accessed in the dictionary with the unique address pointer immediately causes a HIT or a MISS in the dictionary. A HIT produces the last matched string code for generating a new address pointer indicative of a longer string when the extension character code is appended onto the last matched string code to provide the next new pointer address.
Inventors
- 👤 Kenneth Lindsay York
- 👤 Thayer Lindsay York
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 16:16
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/3084; H03M7/3088
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
183 words
A method for compressing serial streams of data which includes substituting string code values for known string previously observed in the data stream, characterized by the steps of: preparing a dictionary having 2 n storage addresses to receive said string code values in the memory of some of the 2 n storage addresses, storing unique code values for new strings in said dictionary when first observed in said data stream, creating a unique 2 n bit dictionary pointer address to be used to determine if the same string being searched already has a string code stored in said dictionary, said pointer address comprising a string code portion corresponding to bits of a code for a known string and an extension character portion corresponding to bits of a code for the next character in said data stream, reading the contents of said dictionary at said one unique 2 n bit pointer address, and determining from the contents read at the single 2 n bit pointer address whether or not a code value for the memory string being searched is already present in said dictionary.
Claim 2
Independent Claim
183 words
A method for compressing serial streams of data which includes substituting string code values for known string previously observed in the data stream, characterized by the steps of: preparing a dictionary having 2 n storage addresses to receive said string code values in the memory of some of the 2 n storage addresses, storing unique code values for new strings in said dictionary when first observed in said data stream, creating a unique 2 n bit dictionary pointer address to be used to determine if the same string being searched already has a string code stored in said dictionary, said pointer address comprising a string code portion corresponding to bits of a code for a known string and an extension character portion corresponding to bits of a code for the next character in said data stream, reading the contents of said dictionary at said one unique 2 n bit pointer address, and determining from the contents read at the single 2 n bit pointer address whether or not a code value for the memory string being searched is already present in said dictionary.
Claim 3
Dependent Claim
72 words
A method as set forth in claim 1 wherein said step of determining comprises: determining that the contents of said dictionary comprise a string code indicator, creating a new unique pointer address employing the same string code as read from said dictionary, and appending the code for the next character in said data stream to the string code read to form a new pointer address for the next string to be searched.
Claim 4
Dependent Claim
70 words
A method as set forth in claim 1 wherein said step of determining comprises: determining that the contents of said dictionary do not contain a string code for the string being searched at said unique pointer address, and further includes, transmitting the last matched string code found at the previous pointer address to a receiver, and storing a next unique string code in the dictionary at the present pointer address.
Claim 5
Dependent Claim
50 words
A method as set forth in claim 3 which further includes: creating a new unique pointer address comprising the last character code read from the data stream during the previous access, and appending the code for the next character in said data stream to form said new unique pointer address.
Claim 6
Dependent Claim
33 words
A method as set forth in claim 3 wherein the step of storing a next unique string code in the dictionary comprises incrementing a code counter to provide a next unique string code.
Claim 7
Dependent Claim
40 words
A method as set forth in claim 5 which further includes a step of: determining if said string code being read from said dictionary is the highest numbered string code to be used to indicate that said dictionary is full.
Claim 8
Dependent Claim
116 words
A method as set forth in claim 1 which further includes: providing a table level memory associated with the contents of said dictionary at each pointer address, setting a level value in said table level memory each time a new unique string code is stored in said dictionary, setting a higher level value in said table level memory when it has been determined that said dictionary is full, and the step of determining from the contents read from said single pointer address further comprises determining that the table level value at the unique pointer address corresponds to a predetermined table level value indicating that the code for the string being searched is present in said dictionary.
Claim 9
Independent Claim
154 words
A method for data compression utilizing a memory dictionary for storing codes for strings of data characters encountered in an input data stream and representing known strings with string codes, characterized by: storing unique string codes in said memory dictionary representative of known strings of data, generating a 2 n bit pointer address indicative of strings of data characters in said input data stream, forming said pointer address comprising bits of the code for the last character in the previous string and appended thereto the bits of the next character from the input data stream forming a two character code string address, reading a string code from the memory said dictionary at said 2 n bit pointer address, and generating a new 2 n bit pointer address comprising the bits of the string code read from said dictionary and appended thereto the bit code for the next character taken from the input data stream.
Claim 10
Independent Claim
154 words
A method for data compression utilizing a memory dictionary for storing codes for strings of data characters encountered in an input data stream and representing known strings with string codes, characterized by: storing unique string codes in said memory dictionary representative of known strings of data, generating a 2 n bit pointer address indicative of strings of data characters in said input data stream, forming said pointer address comprising bits of the code for the last character in the previous string and appended thereto the bits of the next character from the input data stream forming a two character code string address, reading a string code from the memory said dictionary at said 2 n bit pointer address, and generating a new 2 n bit pointer address comprising the bits of the string code read from said dictionary and appended thereto the bit code for the next character taken from the input data stream.
Claim 11
Dependent Claim
66 words
The method set forth in claim 8 wherein the string code read from said dictionary at said pointer address is representative of a previously occurring string, continuing to generate new pointer addresses, continuing to read previously stored string codes from said dictionary at the new pointer addresses, and extending the length of the strings represented by said address pointers each time a previous string is found.
Claim 12
Dependent Claim
54 words
The method as set forth in claim 8 wherein the code read at said new pointer address is representative of no previously occurring string, and generating a new pointer address comprising the code for the last character taken from the previously stored string and the next character from the input data stream appended thereto.
Claim 13
Dependent Claim
53 words
The method as set forth in claim 10 which further includes transmitting the last matched string code to a receiver or a decoder, and storing a unique new string code value in the dictionary at the pointer address, said new unique string code value comprising a sequential value generated by a code generator.
Claim 14
Dependent Claim
183 words
A data compression system for compressing serial streams of data by substituting codes for known strings of characters in an input data stream, comprising: pointer address means for searching for codes representative of strings of data in said data stream, said pointer address comprising a known string code portion and a next character code portion wherein the next character is taken from the input data stream and appended as a character code to the string code portion to form a unique pointer address, a string code dictionary having a plurality of addressable memory locations at least one for each possible unique pointer address, said string code dictionary containing a unique string code value for plural character strings observed in said data stream, and means for reading said unique string code values from said string code dictionary at said unique pointer addresses, and means for determining from the contents read from said string code dictionary whether or not a string code exist in said dictionary that is representative of the string of characters in said input data stream and indicated by said pointer address.
Claim 15
Dependent Claim
183 words
A data compression system for compressing serial streams of data by substituting codes for known strings of characters in an input data stream, comprising: pointer address means for searching for codes representative of strings of data in said data stream, said pointer address comprising a known string code portion and a next character code portion wherein the next character is taken from the input data stream and appended as a character code to the string code portion to form a unique pointer address, a string code dictionary having a plurality of addressable memory locations at least one for each possible unique pointer address, said string code dictionary containing a unique string code value for plural character strings observed in said data stream, and means for reading said unique string code values from said string code dictionary at said unique pointer addresses, and means for determining from the contents read from said string code dictionary whether or not a string code exist in said dictionary that is representative of the string of characters in said input data stream and indicated by said pointer address.
Claim 16
Dependent Claim
70 words
A data compression system as set forth in claim 12 , wherein said means for determining comprises buffer register means for receiving and storing string code values read from said dictionary that are indicative of plural character strings that have previously occurred in said input data stream, and means for transmitting to a receiver the string code for the longest matching string of characters found in said input data stream.
Claim 17
Dependent Claim
77 words
A data compression system as set forth in claim 12 wherein said means for determining comprises buffer register means for receiving code values read form said dictionary that are indicative of the absence of a string code in the dictionary at said pointer address, and string code generating means for writing into said dictionary a unique string code value to be substituted for said string of characters in said input data stream indicated by said pointer address.
Claim 18
Dependent Claim
30 words
A data compression system as set forth in claim 14 wherein said pointer address means comprises a register for storing pointer addresses having a length equal to 2 n bits.
Claim 19
Dependent Claim
25 words
A data compression system as set forth in claim 15 wherein said code dictionary comprises a memory having a minimum of 2 n pointer addresses.
Claim 20
Dependent Claim
43 words
A data compression system as set forth in claim 16 wherein said string code generation means comprises means for generating variable width unique string code values at different pointer addresses, and the number of possible pointer addresses exceeds the number of code values.
Claim 21
Dependent Claim
35 words
A data compression system as set forth in claim 12 wherein said string code dictionary comprises memory locations having greater number of bits than the bits employed for said string code values having variable widths.
Claim 22
Dependent Claim
27 words
A data compression system as set forth in claim 18 wherein a portion of said memory locations comprise a table for storing table values in unused bits.
Claim 23
Dependent Claim
50 words
A data compression system as set forth in claim 12 wherein said string code dictionary further includes an associated table level value memory, and means for resetting said table level values to a higher table level when said dictionary is full of string code values at a lower table level.
References Cited (Backward Citations)
US4558302B1
Cited
US4558302A
Cited
US5016009A
Cited
US4929946A
Cited
US5049881A
Cited
US5151697A
Cited
US5373290A
Cited
US5229768A
Cited
US5455576A
Cited
US5389922A
Cited
US5525982A
Cited
US5646617A
Cited
US5642112A
Cited
US5798718A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-11-19 | 2005-05-21 | 2005-11-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-11-19 | 2009-05-21 | 2009-11-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-11-19 | 2013-05-21 | 2013-11-20 | $7700.00 | Window Closed / Lapsed |