US5680601A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Compression system for reducing the occurrence of a literal prefix
Assignee: Hewlett Packard Development Co LP
•
Filing: 1994-12-14
•
Granted: 1997-10-21
•
Expires: 2014-12-14
Abstract
Abstract A method for reducing the amount of memory used to store an original data in a processing system by reducing the occurrence of a literal prefix. The method is completed by comparing strings from the original data to valid elements in a dictionary. If a match is found, then a data code, which points to the valid dictionary element, is stored as compressed data in the memory. If a match is not found, then the entry is defined as a literal. Assuming the literal is defined, next determine if a dictionary element pointed to by the literal is valid and if so, then store a literal prefix into the compressed data in the memory. Finally, independent of whether the lateral points to a valid dictionary element, the literal itself is stored into the compressed data in the memory. To decompress the compressed data first an entry of the compressed data is retrieved from the memory. If the entry is a literal prefix, then output a next entry of the compressed data. In the alternative, if the entry points to an invalid dictionary element then output the entry because it is a literal. Finally, the only alternative remaining is that the entry points to a valid dictionary element. Thus the a code that must be decompressed before it can be output.
Inventors
- 👤 Robert A. Rust
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 14:44
CPC Classifications
G; G06; G06F; G06F7/00; H; H03; H03M; H03M7/00; H03M7/30; H03M7/3084; H03M7/3088; G06T; G06T9/00; G06T9/005; Y; Y10; Y10S; Y10S707/00; Y10S707/99931
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
103 words
A method for decompressing a compressed data into an original data where said compressed data is stored in memory, said method comprising the steps of: retrieving an entry of said compressed data from said memory; if said entry is a literal prefix, then outputting a next entry of said compressed data to said original data, in the alternative said entry is a code; if said entry points to an invalid dictionary element then outputting said entry to said original data; and if said entry points to a valid dictionary element, then said entry is a code, decompressing said code to said original data.
Claim 2
Independent Claim
103 words
A method for decompressing a compressed data into an original data where said compressed data is stored in memory, said method comprising the steps of: retrieving an entry of said compressed data from said memory; if said entry is a literal prefix, then outputting a next entry of said compressed data to said original data, in the alternative said entry is a code; if said entry points to an invalid dictionary element then outputting said entry to said original data; and if said entry points to a valid dictionary element, then said entry is a code, decompressing said code to said original data.
Claim 3
Dependent Claim
19 words
The method of claim 1 further comprises: updating said dictionary in accordance with said entry and a previous entry.
Claim 4
Dependent Claim
27 words
The method of claim 1 wherein said step of decompressing further comprises: extracting said valid dictionary element; and outputting said valid dictionary element to said original data.
Claim 5
Dependent Claim
158 words
The method of claim 2 wherein said step of updating further comprises: if said entry is said code and said previous entry was a code then first creating a new valid dictionary element, then updating said dictionary with said new valid dictionary element; if said entry is said literal prefix or is pointing to said invalid dictionary element and said previous entry was a code then second creating a first new valid dictionary element and a second new valid dictionary element, then updating said dictionary with said first new valid dictionary element and said second new valid dictionary element; and if said entry is said literal prefix or is pointing to said invalid dictionary element and said previous entry was said literal prefix or was pointing to an invalid dictionary element then third creating a third new valid dictionary element and a fourth new valid dictionary element, then updating said dictionary with said third new valid dictionary element.
Claim 6
Dependent Claim
27 words
The method of claim 1 wherein said dictionary element is invalid if said code points to a dictionary element that is past a last valid dictionary element.
Claim 7
Independent Claim
139 words
A method for compressing an original data into a compressed data where said original data is stored in memory, said method comprising the steps of: retrieving an entry of said original data from said memory; comparing said entry to valid elements in a dictionary; if said step of comparing finds a match between said entry and a valid dictionary element then first outputting into said compressed data a code that points to where in said dictionary said match is; if said step of comparing fails to find said match then defining said entry as a literal; if said literal is defined, determining if a dictionary element pointed to by said literal is valid and if so, then outputting a literal prefix into said compressed data; and if said literal is defined, second outputting said literal into said compressed data.
Claim 8
Independent Claim
139 words
A method for compressing an original data into a compressed data where said original data is stored in memory, said method comprising the steps of: retrieving an entry of said original data from said memory; comparing said entry to valid elements in a dictionary; if said step of comparing finds a match between said entry and a valid dictionary element then first outputting into said compressed data a code that points to where in said dictionary said match is; if said step of comparing fails to find said match then defining said entry as a literal; if said literal is defined, determining if a dictionary element pointed to by said literal is valid and if so, then outputting a literal prefix into said compressed data; and if said literal is defined, second outputting said literal into said compressed data.
Claim 9
Dependent Claim
42 words
The method of claim 6 further comprising: if said step of comparing finds a match between said entry and a valid dictionary element then iteratively performing said steps of retrieving and comparing until said step of comparing fails to find said match.
Claim 10
Independent Claim
236 words
A method for reducing the amount of memory used to store an original data in a processing system, said method comprising the steps of: receiving an entry of said original data; comparing said entry to valid elements in a dictionary where said dictionary is stored in said memory; if said step of comparing finds a match between said entry and a valid dictionary element then first storing a data code as compressed data in said memory, said data code points to said valid dictionary element; if said step of comparing fails to find said match then defining said entry as a literal; if said literal is defined, determining if a dictionary element pointed to by said literal is valid and if so, then second storing a literal prefix into said compressed data in said memory; if said literal is defined, third storing said literal into said compressed data in said memory; repeating said steps of receiving, comparing, first storing, defining, second storing, and third storing until all entries in said original data are processed; retrieving a second entry of said compressed data from said memory; if said second entry is said literal prefix, then first outputting a next entry of said compressed data; if said entry points to an invalid dictionary element then second outputting said entry; and if said entry points to a valid dictionary element, then said entry is a code, decompressing said code.
Claim 11
Independent Claim
236 words
A method for reducing the amount of memory used to store an original data in a processing system, said method comprising the steps of: receiving an entry of said original data; comparing said entry to valid elements in a dictionary where said dictionary is stored in said memory; if said step of comparing finds a match between said entry and a valid dictionary element then first storing a data code as compressed data in said memory, said data code points to said valid dictionary element; if said step of comparing fails to find said match then defining said entry as a literal; if said literal is defined, determining if a dictionary element pointed to by said literal is valid and if so, then second storing a literal prefix into said compressed data in said memory; if said literal is defined, third storing said literal into said compressed data in said memory; repeating said steps of receiving, comparing, first storing, defining, second storing, and third storing until all entries in said original data are processed; retrieving a second entry of said compressed data from said memory; if said second entry is said literal prefix, then first outputting a next entry of said compressed data; if said entry points to an invalid dictionary element then second outputting said entry; and if said entry points to a valid dictionary element, then said entry is a code, decompressing said code.
Claim 12
Dependent Claim
20 words
The method of claim 8 further comprises updating said dictionary in accordance with said second entry and a previous entry.
Claim 13
Dependent Claim
23 words
The method of claim 8 wherein said step of decompressing further comprises: extracting said valid dictionary element; and outputting said valid dictionary element.
Claim 14
Dependent Claim
27 words
The method of claim 8 wherein said dictionary element is invalid if said code points to a dictionary element that is past a last valid dictionary element.
Claim 15
Dependent Claim
77 words
The method of claim 8 wherein said step of comparing further comprising: if said match is found, then adding a subsequent entry of said original data said entry thereby forming a string; searching said dictionary for said string repeating said steps of adding and searching until said step of searching fails to find said string in said dictionary; creating a new valid dictionary entry that contains said string, said data code points to said new dictionary entry.
Claim 16
Dependent Claim
31 words
The method of claim 12 further comprises if said literal is defined, then second creating a second new valid entry in said dictionary, said second new valid entry contains said literal.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-10-20 | 2001-04-21 | 2001-10-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-10-20 | 2005-04-21 | 2005-10-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-10-20 | 2009-04-21 | 2009-10-21 | $7700.00 | Window Closed / Lapsed |