Patent US4909584A successfully refreshed from Google Patents.
Patent US5126739A successfully refreshed from Google Patents.
US5126739A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Data compression apparatus and method
Assignee: HI/FN Inc
•
Filing: 1990-11-27
•
Granted: 1992-06-30
•
Expires: 2010-11-27
Abstract
Abstract An apparatus and method as disclosed for converting an input data character stream into a variable length encoded data stream in a data compression system. The data compression system includes a history array means. The history array means has a plurality of entries and each entry of the history array means is for storing a portion of the input data stream. The method for converting the input data character stream includes the following steps. Performing a search in a history array means for the longest data string which matches the input data string. If the matching data string is found within the history buffer means, the next step includes encoding the longest matching data string found by appending to the encoded data stream a tag indicating the longest matching data string was found and a string substitution code. If the matching data string is not found within the history array means, the next step includes encoding the first character of the input data string by appending to the encoded data stream a raw data tag indicating that no matching data string was found and the first character of the input data string.
Inventors
- 👤 Douglas L. Whiting
- 👤 Glen A. George
- 👤 Glen E. Ivey
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 16:04
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/005; H; H03; H03M; H03M7/00; H03M7/30; H03M7/3084; H03M7/3086; H03M7/40; H03M7/46
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
128 words
A data compression system comprising: a history array means, said history array means having a plurality of entries, said entries of said history array means for storing an input data stream, a history array pointer, said history array pointer pointing to one of said entries in said history array means, a hash table means having a plurality of entries, each entry of said hash table means for storing a pointer indicating one of said entries of said history array means, and an offset array means, said offset array means having a plurality of entries, and each entry of said offset array means providing a link, if any, from one of said entries in said history array means to one or more other entries of said history array means.
Claim 2
Dependent Claim
128 words
A data compression system comprising: a history array means, said history array means having a plurality of entries, said entries of said history array means for storing an input data stream, a history array pointer, said history array pointer pointing to one of said entries in said history array means, a hash table means having a plurality of entries, each entry of said hash table means for storing a pointer indicating one of said entries of said history array means, and an offset array means, said offset array means having a plurality of entries, and each entry of said offset array means providing a link, if any, from one of said entries in said history array means to one or more other entries of said history array means.
Claim 3
Dependent Claim
36 words
The apparatus of claim 1 further including means for incrementing said history array pointer to the next entry in said history array means and means for hashing the next data characters of said input data stream.
Claim 4
Dependent Claim
45 words
The apparatus of claim 1 or 2 wherein said apparatus further includes means for periodically examining the pointer stored at each said hash table entry for determining whether said pointer at said hash table entry differs from said history array pointer by a predetermined amount.
Claim 5
Dependent Claim
27 words
The apparatus of claim 3 wherein said means further includes means for replacing said entry in said hash table by an invalid value, thereby reinitializing said entry.
Claim 6
Dependent Claim
24 words
The apparatus of claim 4 further including: means for initializing said hash table by replacing all entries of said hash table by invalid values.
Claim 7
Independent Claim
145 words
A method for compressing data in a data compression system which includes a history array means, said history array means having a plurality of entries, a history array pointer, a hash table means, said hash table means having a plurality of entries, and an offset array means, said offset array means having a plurality of entries, said method comprising the steps of: storing an input data stream in said entries of said history array means, pointing to one of said entries in said history array means by said history array pointer, storing a pointer indicating one of said entries of said history array means in each entry of said hash table means, and providing a link by each entry of said offset array means from one of said entries in said history array means to one or more other entries of said history array means.
Claim 8
Independent Claim
145 words
A method for compressing data in a data compression system which includes a history array means, said history array means having a plurality of entries, a history array pointer, a hash table means, said hash table means having a plurality of entries, and an offset array means, said offset array means having a plurality of entries, said method comprising the steps of: storing an input data stream in said entries of said history array means, pointing to one of said entries in said history array means by said history array pointer, storing a pointer indicating one of said entries of said history array means in each entry of said hash table means, and providing a link by each entry of said offset array means from one of said entries in said history array means to one or more other entries of said history array means.
Claim 9
Dependent Claim
35 words
The method of claim 6 further including the steps of incrementing said history array pointer to the next entry in said history array means and hashing the next data characters of said input data stream.
Claim 10
Dependent Claim
43 words
The method of claim 6 or 7 further including the step of periodically examining the pointer stored at each said hash table entry for determining whether said pointer at said hash table entry differs from said history array pointer by a predetermined pointer.
Claim 11
Dependent Claim
25 words
The method of claim 8 further including the step of replacing said entry in said hash table by an invalid value, thereby reinitializing said entry.
Claim 12
Dependent Claim
25 words
The method of claim 9 further including the step of: initializing said hash table by replacing all entries of said hash table by invalid values.
References Cited (Backward Citations)
US4021782A
Cited
US3976844A
Cited
US4054951A
Cited
US4370711A
Cited
US4412306A
Cited
US4464650A
Cited
US4491934A
Cited
US4814746A
Cited
US4558302A
Cited
US4558302B1
Cited
US4612532A
Cited
US4701745A
Cited
US4730348A
Cited
US4942520A
Cited
US4876541A
Cited
US5001478A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-06-30 | 1995-12-30 | 1996-06-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-06-30 | 1999-12-30 | 2000-06-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-06-30 | 2003-12-30 | 2004-06-30 | $7700.00 | Window Closed / Lapsed |