US5281967A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Data compression/decompression method and apparatus
Assignee: TELEDATA SOUND LLC
•
Filing: 1992-01-29
•
Granted: 1994-01-25
•
Expires: 2012-01-29
Abstract
Abstract A method and apparatus for compressing digital data uses data which has been previously compressed as a dictionary of substrings which may be replaced in an input data stream. The method and apparatus uses a hash table to take advantage of principles of locality and probability to solve the maximal matching substring problem inherent in this type of compressing apparatus, most of the time. The hash table consists of first-in, first-out (FIFO) collision chains of fixed, uniform numbers of pointers to substrings of data already compressed which potentially match an input substring. A link list is maintained for linking pointers to corresponding potentially matching strings. A companion decompressing method and apparatus receives compressed data from the compressing apparatus and expand that data back to its original form.
Inventors
- 👤 Robert K. Jung
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 13:49
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/3084; H03M7/3086
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
213 words
A system for processing digital input data, said input data being divisible into strings of bits representing symbols, comprising: a memory for holding at least first and second strings of symbols from said input data, said first string having a prefix substring of a fixed length; means for receiving said prefix substring and computing a first string hash value therefrom; a hash table for receiving said first string hash value and providing one pointer to each of a number of locations in said second string having an associated second string substring of said fixed length with a second string hash value which matches said first string hash value; means for receiving said first and second strings of symbols from said memory; means for determining the longest second string substring match of a first string substring including said first string prefix substring, said means for determining including means for finding a second string substring match of a certain length pointed to by a first pointer, and means for performing a symbol comparison of said first string substring with a second string substring pointed to by a second pointer, beginning with a symbol being at least one symbol beyond said certain length; and means for generating compressed output data responsive to said means for determining.
Claim 2
Independent Claim
213 words
A system for processing digital input data, said input data being divisible into strings of bits representing symbols, comprising: a memory for holding at least first and second strings of symbols from said input data, said first string having a prefix substring of a fixed length; means for receiving said prefix substring and computing a first string hash value therefrom; a hash table for receiving said first string hash value and providing one pointer to each of a number of locations in said second string having an associated second string substring of said fixed length with a second string hash value which matches said first string hash value; means for receiving said first and second strings of symbols from said memory; means for determining the longest second string substring match of a first string substring including said first string prefix substring, said means for determining including means for finding a second string substring match of a certain length pointed to by a first pointer, and means for performing a symbol comparison of said first string substring with a second string substring pointed to by a second pointer, beginning with a symbol being at least one symbol beyond said certain length; and means for generating compressed output data responsive to said means for determining.
Claim 3
Dependent Claim
38 words
A system as claimed in claim 1 further including a link list for storing accessible pointer information, said information including a link between every pointer which points to a location having the same associated second string hash value.
Claim 4
Dependent Claim
32 words
A system as claimed in claim 1, wherein said memory further comprises: a first buffer for holding said first string; and a second buffer for holding at least one said second string.
Claim 5
Dependent Claim
62 words
A system as claimed in claim 1 wherein said compressed output data includes: at least one of: a pointer to one of said locations in said second string and a partial pointer to one of said locations in said second string; a first symbol corresponding to said location; and a flag for identifying which of said pointer or partial pointer is included.
Claim 6
Dependent Claim
35 words
A system as claimed in claim 4 wherein said means for generating compressed output data comprises: means for selecting at least one of said pointer and said partial pointer; and means for generating said flag.
Claim 7
Dependent Claim
73 words
A system as claimed in claim 5, further including: means for receiving said compressed output data; and means for decompressing said compressed output data received; wherein said means for decompressing said compressed output data comprises: means for decoding said flag, and means responsive to said means for decoding said flag, for translating said at least one of said pointer and said partial pointer into a decompressed data sequence identical to said input data.
Claim 8
Dependent Claim
60 words
A system as claimed in claim 6, wherein said means for translating comprises: a memory for receiving sequences of decompressed data; and means for identifying in said memory for receiving decompressed data sequences pointed to by said pointers and said partial pointers; and means for copying said sequences identified by said means for identifying to new locations in said memory.
Claim 9
Dependent Claim
33 words
A system as claimed in claim 4, wherein said pointer comprises: an offset for identifying said first symbol; and a length over which said first string substring and a second string substring match.
Claim 10
Dependent Claim
26 words
A system as claimed in claim 4, wherein said partial pointer comprises: a length over which said first string substring and a second string substring match.
Claim 11
Independent Claim
212 words
A system for processing digital input data, said input data being divisible into strings of bits representing symbols, comprising: a memory for holding at least first and second strings of symbols from said input data, said first string having a prefix substring of a fixed length; means for receiving said prefix substring and computing a first string hash value therefrom; a hash table for receiving said first string hash value and providing a pointer to a location in said second string having an associated second string substring of said fixed length with the same hash value; a link list including a link between each pointer which points to a location having an associated second string substring of said fixed length with a same second string hash value; means for receiving said first and second strings of symbols from said memory; means for determining the longest second string substring match of a first string substring including said first string prefix substring, said means for determining including means for comparing said first string substring with a selected limited number of second string substrings, a fixed length of which has a same hash value as that of said first string hash value; and means for generating compressed output data responsive to said means for determining.
Claim 12
Independent Claim
212 words
A system for processing digital input data, said input data being divisible into strings of bits representing symbols, comprising: a memory for holding at least first and second strings of symbols from said input data, said first string having a prefix substring of a fixed length; means for receiving said prefix substring and computing a first string hash value therefrom; a hash table for receiving said first string hash value and providing a pointer to a location in said second string having an associated second string substring of said fixed length with the same hash value; a link list including a link between each pointer which points to a location having an associated second string substring of said fixed length with a same second string hash value; means for receiving said first and second strings of symbols from said memory; means for determining the longest second string substring match of a first string substring including said first string prefix substring, said means for determining including means for comparing said first string substring with a selected limited number of second string substrings, a fixed length of which has a same hash value as that of said first string hash value; and means for generating compressed output data responsive to said means for determining.
Claim 13
Dependent Claim
72 words
A system as claimed in claim 10 wherein said means for determining further includes: means for finding a second string substring match of a certain length pointed to by a first pointer; and means for performing a symbol comparison of said first string substring with a second string substring pointed to by a second pointer, said means for performing beginning with a symbol being at least one symbol beyond said certain length.
Claim 14
Dependent Claim
32 words
A system as claimed in claim 10, wherein said memory further comprises: a first buffer for holding said first string; and a second buffer for holding at least one said second string.
Claim 15
Dependent Claim
62 words
A system as claimed in claim 10 wherein said compressed output data includes: at least one of: a pointer to one of said locations in said second string and a partial pointer to one of said locations in said second string; a first symbol corresponding to said location; and a flag for identifying which of said pointer or partial pointer is included.
Claim 16
Dependent Claim
35 words
A system as claimed in claim 13 wherein said means for generating compressed output data comprises: means for selecting at least one of said pointer and said partial pointer; and means for generating said flag.
Claim 17
Dependent Claim
73 words
A system as claimed in claim 14 further including: means for receiving said compressed output data; and means for decompressing said compressed output data received, wherein said means for decompressing said compressed output data comprises: means for decoding said flag; and means responsive to said means for decoding said flag, for translating said at least one of said pointer and said partial pointer into a decompressed data sequence identical to said input data.
Claim 18
Dependent Claim
60 words
A system as claimed in claim 15, wherein said means for translating comprises: a memory for receiving sequences of decompressed data; and means for identifying in said memory for receiving decompressed data sequences pointed to by said pointers and said partial pointers; and means for copying said sequences identified by said means for identifying to new locations in said memory.
Claim 19
Dependent Claim
33 words
A system as claimed in claim 13, wherein said pointer comprises: an offset for identifying said first symbol; and a length over which said first string substring and a second string substring match.
Claim 20
Dependent Claim
26 words
A system as claimed in claim 13, wherein said partial pointer comprises: a length over which said first string substring and a second string substring match.
Claim 21
Independent Claim
129 words
A method for processing digital input data, said input data being divisible into symbols, comprising the steps of: receiving input data, including a first string having a prefix substring of a fixed length being less than a length of said first string; computing a hash value of said prefix substring; storing pointers in a hash table to each location in a second string; generating a link list for linking pointers together in said hash table which point to locations having fixed lengths which have a same hash value; comparing said first string with a selected limited number of substrings in said second string having linked pointers and fixed length hash values which match that of said prefix substring hash value; and generating compressed output data based upon said comparison.
Claim 22
Independent Claim
129 words
A method for processing digital input data, said input data being divisible into symbols, comprising the steps of: receiving input data, including a first string having a prefix substring of a fixed length being less than a length of said first string; computing a hash value of said prefix substring; storing pointers in a hash table to each location in a second string; generating a link list for linking pointers together in said hash table which point to locations having fixed lengths which have a same hash value; comparing said first string with a selected limited number of substrings in said second string having linked pointers and fixed length hash values which match that of said prefix substring hash value; and generating compressed output data based upon said comparison.
Claim 23
Dependent Claim
59 words
A system as claimed in claim 19 wherein said step of comparing includes: locating a second string substring match of a certain length pointed to by a first pointer; and performing a symbol comparison of said first-string with a second string substring pointed to by a second pointer, beginning with a symbol being one symbol beyond said certain length.
Claim 24
Dependent Claim
64 words
A system as claimed in claim 20 wherein the step of generating comprises the steps of: outputting at least one of a pointer to a location in said second string and a partial pointer to a location in said second string; outputting a first symbol corresponding to said location; and outputting a flag for identifying which of said pointer or partial pointer is outputted.
Claim 25
Dependent Claim
17 words
A system as claimed in claim 20 further comprising the step of: decompressing said compressed output data.
References Cited (Backward Citations)
US4464650A
Cited
US4597057A
Cited
US4814746A
Cited
US4558302A
Cited
US4558302B1
Cited
WO1990000837A1
Cited
US5126739A
Cited
US5146221A
Cited
US5049881A
Cited
US5150119A
Cited
US5051745A
Cited
US5140321A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-01-24 | 1997-07-26 | 1998-01-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-01-24 | 2001-07-26 | 2002-01-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-01-24 | 2005-07-26 | 2006-01-25 | $7700.00 | Window Closed / Lapsed |