US5010345A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Data compression method
Assignee: International Business Machines Corp
•
Filing: 1989-12-28
•
Granted: 1991-04-23
•
Expires: 2009-12-28
Abstract
Abstract Disclosed is a method of compressing a sequence of data symbols. The method includes the steps of sequentially appending symbols to a working substring to find the longest string that is duplicated in a history buffer or a lexicon. If the string is duplicated in the history buffer, then a history reference is emitted. If the string is duplicated in the lexicon, then a lexicon reference is emitted. If the string is not duplicated in either the history buffer or the lexicon, then a literal reference is emitted. The history buffer is a record of uncompressed data that has most recently been processed. The lexicon is a record of strings that has been emitted by means of history references.
Inventors
- 👤 Michael E. Nagy
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 11:23
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/40; H03M7/42; H03M7/3084; H03M7/3086; H03M7/3088
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
80 words
A method of compressing data made up of a sequence of symbols, which comprises the steps of: recording in a fixed length history buffer symbols of said sequence; emitting a history reference whenever a string of symbols from said sequence is duplicated in said history buffer; recording in a lexicon strings of symbols that have been emitted by means of history references; and, emitting a lexicon reference whenever a string of symbols from said sequence is duplicated in said lexicon.
Claim 2
Independent Claim
80 words
A method of compressing data made up of a sequence of symbols, which comprises the steps of: recording in a fixed length history buffer symbols of said sequence; emitting a history reference whenever a string of symbols from said sequence is duplicated in said history buffer; recording in a lexicon strings of symbols that have been emitted by means of history references; and, emitting a lexicon reference whenever a string of symbols from said sequence is duplicated in said lexicon.
Claim 3
Dependent Claim
22 words
The method as claimed in claim 1, wherein the length of said history buffer is less than the length of said sequence.
Claim 4
Dependent Claim
14 words
The method as claimed in claim 1, wherein said lexicon has a fixed size.
Claim 5
Dependent Claim
30 words
The method as claimed in claim 1, including the step of emitting a literal reference whenever a symbol of said sequence is duplicated in neither said history buffer nor lexicon.
Claim 6
Dependent Claim
28 words
The method as claimed in claim 1, including the step of: forming the longest string of symbols that is duplicated in either said lexicon or said history buffer.
Claim 7
Dependent Claim
24 words
The method as claimed in claim 5, wherein said longest string is equal to or less than a preselected maximum history reference length value.
Claim 8
Dependent Claim
40 words
The method as claimed in claim 5, wherein said forming step includes the steps of: forming a token; sequentially appending to said token symbols from said sequence until said token is duplicated in neither said lexicon nor said history buffer.
Claim 9
Dependent Claim
112 words
The method as claimed in claim 7, wherein said step of sequentially appending symbols to said token includes the steps of: (a) appending a symbol to said token; (b) comparing said token to the contents of said lexicon; (c) appending another symbol to said token if said token is duplicated in said lexicon; (d) repeating steps b and c until said token is not duplicated in said lexicon; (e) comparing said token to the contents of said history buffer; (f) appending another symbol to said token if said token is duplicated in said history buffer and, (g) repeating steps b through f until said token is not duplicated in said history buffer.
Claim 10
Dependent Claim
34 words
The method as claimed in claim 8, including the step of repeating steps b through f as long as said token is equal to or less than a preselected maximum history reference length value.
Claim 11
Dependent Claim
13 words
The method as claimed in claim 1, wherein said lexicon is initially empty.
Claim 12
Independent Claim
177 words
A method of compressing data made up of a sequence of symbols, which comprises the steps of: (a) sequentially appending symbols to a token until said token is duplicated in neither a lexicon or a history buffer, thereby forming a longest referenced string of symbols that can be duplicated in either the lexicon or the history buffer; (b) emitting a lexicon reference representing said referenced string when said referenced string duplicated in said lexicon; (c) emitting a history reference representing said referenced string when said referenced string is duplicated in said history buffer; (d) emitting a literal reference when said referenced string is not duplicated in either the history buffer or the lexicon; (e) adding the referenced string represented by the history reference emitted in step d to the lexicon; (f) appending the referenced string represented by the reference emitted in step c, d, or e to the history buffer; (g) deleting the referenced string represented by the emitted reference from the token and, (h) repeating steps a through g until said sequence of characters is exhausted.
Claim 13
Independent Claim
177 words
A method of compressing data made up of a sequence of symbols, which comprises the steps of: (a) sequentially appending symbols to a token until said token is duplicated in neither a lexicon or a history buffer, thereby forming a longest referenced string of symbols that can be duplicated in either the lexicon or the history buffer; (b) emitting a lexicon reference representing said referenced string when said referenced string duplicated in said lexicon; (c) emitting a history reference representing said referenced string when said referenced string is duplicated in said history buffer; (d) emitting a literal reference when said referenced string is not duplicated in either the history buffer or the lexicon; (e) adding the referenced string represented by the history reference emitted in step d to the lexicon; (f) appending the referenced string represented by the reference emitted in step c, d, or e to the history buffer; (g) deleting the referenced string represented by the emitted reference from the token and, (h) repeating steps a through g until said sequence of characters is exhausted.
Claim 14
Dependent Claim
16 words
The method as claimed in claim 11, wherein said history buffer is of a fixed size.
Claim 15
Dependent Claim
116 words
The method as claimed in claim 11, wherein said step of sequentially appending characters to said working substring includes the steps of: (a) appending a symbol to said token; (b) comparing the token to the contents of the lexicon; (c) appending another symbol to the token if the token is duplicated in the lexicon; (d) repeating steps b and c until the token is not duplicated in the lexicon; (e) comparing the contents of the token to the contents of the history buffer; (f) adding another symbol to the token if the token is found in the history buffer and, (g) repeating steps b through f until the token is not found in the history buffer.
Claim 16
Dependent Claim
33 words
The method as claimed in claim 13, including the step of repeating steps b through f as long as said token is equal to or less than a preselected maximum history reference length.
Claim 17
Independent Claim
275 words
A method of compressing data made up of a sequence of symbols, which comprises the steps of: (a) forming a token, a history buffer having a fixed depth, and a lexicon having a fixed number of available entries; (b) clearing the token, history buffer, and lexicon; (c) appending a symbol to the token; (d) comparing the token to the contents of the lexicon; (e) appending another symbol to the token if the token is duplicated in the lexicon; (f) repeating steps d and e as long as the token is not greater than a preselected maximum history reference length and until the token is not duplicated in the lexicon; (g) comparing the token to the contents of the history buffer; (h) appending another symbol to the token if the token is duplicated in the history buffer; (i) repeating steps d through h as long as the token is not greater than said preselected maximum history reference length and until the token is not duplicated in the history buffer, thereby finding a match in the history buffer or the lexicon; (j) emitting a lexicon reference if the match is found in the lexicon; (k) emitting a history reference if the match is found in the history buffer; (l) emitting a literal reference if no match is found in either the history buffer or the lexicon; (m) appending the history reference string emitted in step k to the lexicon; (n) adding the reference string emitted in step j, k, or l to the history buffer; (o) deleting the transmitted reference from the token and; (p) repeating steps c through o until the sequence of characters is exhausted.
Claim 18
Independent Claim
275 words
A method of compressing data made up of a sequence of symbols, which comprises the steps of: (a) forming a token, a history buffer having a fixed depth, and a lexicon having a fixed number of available entries; (b) clearing the token, history buffer, and lexicon; (c) appending a symbol to the token; (d) comparing the token to the contents of the lexicon; (e) appending another symbol to the token if the token is duplicated in the lexicon; (f) repeating steps d and e as long as the token is not greater than a preselected maximum history reference length and until the token is not duplicated in the lexicon; (g) comparing the token to the contents of the history buffer; (h) appending another symbol to the token if the token is duplicated in the history buffer; (i) repeating steps d through h as long as the token is not greater than said preselected maximum history reference length and until the token is not duplicated in the history buffer, thereby finding a match in the history buffer or the lexicon; (j) emitting a lexicon reference if the match is found in the lexicon; (k) emitting a history reference if the match is found in the history buffer; (l) emitting a literal reference if no match is found in either the history buffer or the lexicon; (m) appending the history reference string emitted in step k to the lexicon; (n) adding the reference string emitted in step j, k, or l to the history buffer; (o) deleting the transmitted reference from the token and; (p) repeating steps c through o until the sequence of characters is exhausted.
References Cited (Backward Citations)
US4558302A
Cited
US4558302B1
Cited
US4725815A
Cited
US4701745A
Cited
US4899148A
Cited
US4876541A
Cited
US4881075A
Cited
US4906991A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1994-04-22 | 1994-10-22 | 1995-04-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1998-04-22 | 1998-10-22 | 1999-04-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2002-04-22 | 2002-10-22 | 2003-04-23 | $7700.00 | Window Closed / Lapsed |