US5506580A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Data compression apparatus and method
Assignee: HI/FN Inc
•
Filing: 1994-12-06
•
Granted: 1996-04-09
•
Expires: 2014-12-06
Abstract
Abstract An apparatus and method are 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. The history array has a plurality of entries and each entry of the history array 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 for the longest data string which matches the input data string. If the matching data string is found within the history buffer, 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, 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 11:40
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/40; G; G06; G06T; G06T9/00; G06T9/005; H03M7/3084; H03M7/3086; H03M7/46
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
127 words
A method for converting an input data stream into an encoded data character stream, said data stream including data characters, said method comprising the steps of: storing data characters into a data storage means for reference, performing a search in said data storage means for a data character string of said stored data characters which match said input data stream, and encoding a length and an offset position within said data storage means of one of said matching strings found by said search in said data storage means, wherein said offset position is encoded with a tag bit indicating either a short or a long offset, and with a predetermined number of bits indicating the location within said data storage means where said matching string is located.
Claim 2
Independent Claim
127 words
A method for converting an input data stream into an encoded data character stream, said data stream including data characters, said method comprising the steps of: storing data characters into a data storage means for reference, performing a search in said data storage means for a data character string of said stored data characters which match said input data stream, and encoding a length and an offset position within said data storage means of one of said matching strings found by said search in said data storage means, wherein said offset position is encoded with a tag bit indicating either a short or a long offset, and with a predetermined number of bits indicating the location within said data storage means where said matching string is located.
Claim 3
Dependent Claim
38 words
The method of claim 1, wherein said step of encoding said offset position further comprises: indicating a short offset with said tag bit having value "1," and indicating a long offset with said tag bit having value "0."
Claim 4
Dependent Claim
68 words
The method of claim 1, wherein said step of encoding said offset position further comprises: operative when said tag bit indicates a short offset, indicating the location within said data storage means where said matching string is located with seven bits, and operative when said tag bit indicates a long offset, indicating the location within said data storage means where said matching string is located with eleven bits.
Claim 5
Independent Claim
121 words
An apparatus for converting an input data stream into an encoded data character stream, said data stream including data characters, said apparatus comprising: means for storing data characters for reference, means for performing a search in said storing means for a data character string of said stored data characters which match said input data stream, and means for encoding a length and an offset position within said storing means of one of said matching strings found by said search in said storing means, wherein said offset position is encoded with a tag bit indicating either a short or a long offset, and with a predetermined number of bits indicating the location within said storing means where said matching string is located.
Claim 6
Independent Claim
121 words
An apparatus for converting an input data stream into an encoded data character stream, said data stream including data characters, said apparatus comprising: means for storing data characters for reference, means for performing a search in said storing means for a data character string of said stored data characters which match said input data stream, and means for encoding a length and an offset position within said storing means of one of said matching strings found by said search in said storing means, wherein said offset position is encoded with a tag bit indicating either a short or a long offset, and with a predetermined number of bits indicating the location within said storing means where said matching string is located.
Claim 7
Dependent Claim
42 words
The apparatus of claim 4, wherein said means for encoding said offset position further comprises: means for indicating a short offset with said tag bit having value "1," and means for indicating a long offset with said tag bit having value "0."
Claim 8
Dependent Claim
52 words
The apparatus of claim 33, wherein said means for encoding said offset position further comprises: means for indicating the location within said storing means where said matching string is located with seven bits, and means for indicating the location within said storing means where said matching string is located with eleven bits.
Claim 9
Independent Claim
251 words
A method for converting an input data stream into a variable length encoded data character stream in a data compression system, said data stream including data characters, said data compression system comprising a storage means for storing input data characters of said input data character stream, said method comprising the steps of: performing a search in said storage means for a data character string which matches said input data stream; operative when said matching data character string is found within said storage means, encoding said matching data character string by assigning a tag indicating that said matching data character string was found, a variable length indicator of the length of said matching data character string, and a pointer indicating the location within said storage means of said matching data character string, and said step of encoding said matching data character string including the step of representing said pointer and said variable length indicator by an encoding scheme according to a predetermined strategy, said predetermined strategy ensuring that a matching data character string of two data characters of said input data character stream is compressed to less than said two data characters of said input data character stream; operative when said matching input data character string is not found within said storage means, encoding a first character of said input data character stream by assigning a "raw" data tag indicating that no matching data character was found in said storage means and appending said first character of said input data character stream.
Claim 10
Independent Claim
251 words
A method for converting an input data stream into a variable length encoded data character stream in a data compression system, said data stream including data characters, said data compression system comprising a storage means for storing input data characters of said input data character stream, said method comprising the steps of: performing a search in said storage means for a data character string which matches said input data stream; operative when said matching data character string is found within said storage means, encoding said matching data character string by assigning a tag indicating that said matching data character string was found, a variable length indicator of the length of said matching data character string, and a pointer indicating the location within said storage means of said matching data character string, and said step of encoding said matching data character string including the step of representing said pointer and said variable length indicator by an encoding scheme according to a predetermined strategy, said predetermined strategy ensuring that a matching data character string of two data characters of said input data character stream is compressed to less than said two data characters of said input data character stream; operative when said matching input data character string is not found within said storage means, encoding a first character of said input data character stream by assigning a "raw" data tag indicating that no matching data character was found in said storage means and appending said first character of said input data character stream.
Claim 11
Dependent Claim
46 words
The method of claim 7 wherein said step of performing said search in said storage means for said matching data character string further includes the step of limiting said search to a predefined number of inquiries in said storage means for said matching data character string.
Claim 12
Dependent Claim
39 words
The method of claim 7 wherein said step of assigning said pointer indicating the location within said storage means of said matching data character string further includes the step of providing an indicator of the length of said pointer.
Claim 13
Dependent Claim
36 words
The method of claim 9 wherein said step of providing said indicator of the length of said pointer further includes the step of representing said pointer as either a long form or a short form pointer.
Claim 14
Independent Claim
214 words
An apparatus for converting an input data stream into a variable length encoded data character stream, said data stream including data characters, said apparatus comprising: a storage means for storing input data characters of said input data character stream; means for performing a search in said storage means for a data character string which matches said input data stream; means for encoding said matching data character string by assigning a tag indicating that said matching data character string was found, a variable length indicator of the length of said matching data character string, and a pointer indicating the location within said storage means of said matching data character string, said means for encoding said matching data character string including means for representing said pointer and said variable length indicator by an encoding scheme according to a predetermined strategy, said predetermined strategy ensuring that a matching data character string of two data characters of said input data character stream is compressed to less than said two data characters of said input data character stream; means for encoding a first character of said input data character stream by assigning a "raw" data tag indicating that no matching data character was found in said storage means and appending said first character of said input data character stream.
Claim 15
Independent Claim
214 words
An apparatus for converting an input data stream into a variable length encoded data character stream, said data stream including data characters, said apparatus comprising: a storage means for storing input data characters of said input data character stream; means for performing a search in said storage means for a data character string which matches said input data stream; means for encoding said matching data character string by assigning a tag indicating that said matching data character string was found, a variable length indicator of the length of said matching data character string, and a pointer indicating the location within said storage means of said matching data character string, said means for encoding said matching data character string including means for representing said pointer and said variable length indicator by an encoding scheme according to a predetermined strategy, said predetermined strategy ensuring that a matching data character string of two data characters of said input data character stream is compressed to less than said two data characters of said input data character stream; means for encoding a first character of said input data character stream by assigning a "raw" data tag indicating that no matching data character was found in said storage means and appending said first character of said input data character stream.
Claim 16
Dependent Claim
45 words
The apparatus of claim 11 wherein said means for performing said search in said storage means for said matching data character string further includes means for limiting said search to a predefined number of inquiries in said storage means for said matching data character string.
Claim 17
Dependent Claim
38 words
The apparatus of claim 11 wherein said means for assigning said pointer indicating the location within said storage means of said matching data character string further includes means for providing an indicator of the length of said pointer.
Claim 18
Dependent Claim
35 words
The apparatus of claim 13 wherein said means for providing said indicator of the length of said pointer further includes means for representing said pointer as either a long form or a short form pointer.
References Cited (Backward Citations)
CA719774A
Cited
CA811316A
Cited
US3054987A
Cited
US3390380A
Cited
US3344406A
Cited
US3394352A
Cited
US3396352A
Cited
GB1190609A
Cited
US4135214A
Cited
GB1318114A
Cited
US3612660A
Cited
US3656178A
Cited
GB1336317A
Cited
GB1289015A
Cited
US3675212A
Cited
US3675211A
Cited
US3701108A
Cited
US3694813A
Cited
US3767901A
Cited
US3717851A
Cited
US3726993A
Cited
US4021782A
Cited
US3873977A
Cited
US4031515A
Cited
US4319225A
Cited
US3970183A
Cited
US4064489A
Cited
US4034350A
Cited
US3976844A
Cited
US3995254A
Cited
US4121259A
Cited
DE2625527A1
Cited
US4054951A
Cited
US4207599A
Cited
US4145686A
Cited
US4232375A
Cited
US4376933A
Cited
US4290105A
Cited
US4494151A
Cited
US4295124A
Cited
US4382286A
Cited
US4506325A
Cited
US4386416A
Cited
US4486853A
Cited
US4412306A
Cited
US4464650A
Cited
US4543612A
Cited
US4597057A
Cited
US4516246A
Cited
US4545032A
Cited
US4491934A
Cited
US4494150A
Cited
US4507752A
Cited
US4814746A
Cited
US4558302A
Cited
US4558302B1
Cited
US4706264A
Cited
US4546342A
Cited
US4610027A
Cited
US4839649A
Cited
US4612532A
Cited
US4796003A
Cited
US4684923A
Cited
US4701745A
Cited
US4701108A
Cited
US4626824A
Cited
US4626829A
Cited
US4749983A
Cited
US4783841A
Cited
US4891643A
Cited
US4730348A
Cited
US4910751A
Cited
US4866440A
Cited
US4872009A
Cited
US4862167A
Cited
US4882754A
Cited
US4881075A
Cited
US4876541A
Cited
US4870415A
Cited
US4847619A
Cited
US4774500A
Cited
US4857993A
Cited
US4906991A
Cited
US5058144A
Cited
US4870479A
Cited
US4899147A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-04-09 | 1999-10-09 | 2000-04-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-04-09 | 2003-10-09 | 2004-04-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-04-09 | 2007-10-09 | 2008-04-09 | $7700.00 | Window Closed / Lapsed |