US5396595A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for compression and decompression of data
Assignee: SPACELABS Inc A Corp OF
•
Filing: 1992-04-24
•
Granted: 1995-03-07
•
Expires: 2012-04-24
Abstract
Abstract A method and system for compressing and decompressing data is provided. In preferred embodiments, a computer system compresses a data buffer comprising a plurality of symbols wherein each symbol has one or more occurrences. The system generates a symbol table containing each symbol and having a corresponding index. For each occurrence of the symbol in the data buffer, the system determines the index for that symbol into the symbol table, and encodes the index into a variable-length portion, a delimiter, and a fixed-length portion. The system then outputs the encoding as the compressed data buffer.
Inventors
- 👤 Benje J. Standley
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 20:00
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/40; H03M7/42
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
87 words
A method in a computer system of compressing a data buffer, the data buffer comprising a plurality of symbols, each symbol having one or more occurrences, the method comprising the computer-implemented steps of: generating a symbol table, the symbol table containing each symbol and having a corresponding index; and for each occurrence of a symbol in the data buffer, determining the index for that symbol in the symbol table; encoding the determined index into a variable-length portion, a delimiter, and a fixed-length portion; and outputting the encoding.
Claim 2
Independent Claim
87 words
A method in a computer system of compressing a data buffer, the data buffer comprising a plurality of symbols, each symbol having one or more occurrences, the method comprising the computer-implemented steps of: generating a symbol table, the symbol table containing each symbol and having a corresponding index; and for each occurrence of a symbol in the data buffer, determining the index for that symbol in the symbol table; encoding the determined index into a variable-length portion, a delimiter, and a fixed-length portion; and outputting the encoding.
Claim 3
Dependent Claim
28 words
The method of claim 1 wherein the symbols in the symbol table are ordered based on the number of occurrences of the corresponding symbol in the data buffer.
Claim 4
Dependent Claim
16 words
The method of claim 1 including the step of determining the length of the fixed-length portion.
Claim 5
Dependent Claim
25 words
The method of claim 3 wherein the step of determining the length of the fixed-length portion is based on a resulting compressed data buffer size.
Claim 6
Dependent Claim
20 words
The method of claim 1 wherein the step of outputting the encoding stores the encoding in a compressed data buffer.
Claim 7
Dependent Claim
75 words
The method of claim 1 wherein the step of encoding the determined index generates a variable-length portion that is a string with a length equal to the integer portion of the determined index divided by 2 to the power of the length of the fixed-length portion and the fixed-length portion is the binary integer representation of the remainder of the determined index divided by 2 to the power of the length of the fixed-length portion.
Claim 8
Dependent Claim
31 words
The method of claim 1 wherein the variable-length portion comprises a string of bits each with the same bit value and the delimiter is a bit with the opposite bit value.
Claim 9
Independent Claim
83 words
A method in a computer system of decoding an encoded symbol, the encoded symbol represented as an encoded index into a symbol table, the symbol table having a plurality of symbols, each symbol having a corresponding index into the symbol table, the method comprising computer-implemented the steps of: decoding the encoded index to generate a decoded index; and using the decoded index to retrieve the corresponding symbol from the symbol table wherein the retrieved symbol is the decoded representation of the encoded symbol.
Claim 10
Independent Claim
83 words
A method in a computer system of decoding an encoded symbol, the encoded symbol represented as an encoded index into a symbol table, the symbol table having a plurality of symbols, each symbol having a corresponding index into the symbol table, the method comprising computer-implemented the steps of: decoding the encoded index to generate a decoded index; and using the decoded index to retrieve the corresponding symbol from the symbol table wherein the retrieved symbol is the decoded representation of the encoded symbol.
Claim 11
Dependent Claim
19 words
The method of claim 8 wherein the encoded index has a variable-length portion, a delimiter, and a fixed-length portion.
Claim 12
Dependent Claim
67 words
The method of claim 9 wherein the step of decoding the encoded index includes determining the length of the variable-length portion and the length of the fixed-length portion and decoding the index by the formula Lv*2.sup.Lf +f wherein Lv is the length of the variable-length portion, Lf is the length of the fixed-length portion, and f is the value of an integer represented by the fixed-length portion.
Claim 13
Independent Claim
121 words
A method in a computer system of encoding a number, the method comprising the computer-implemented steps of: determining a divisor; determining the integer quotient of the number divided by the divisor; determining the remainder of the number divided by the divisor; generating a string of quotient bits of length equal to the integer quotient, wherein each bit has the same bit value; generating a string of remainder bits representing the remainder; and generating a delimiter bit having a different bit value than the bit value of the bits in the generated string of quotient bits to indicate the end of the generated string of quotient bits, wherein the quotient bits, the delimiter bit, and the remainder bits comprise the encoded number.
Claim 14
Independent Claim
121 words
A method in a computer system of encoding a number, the method comprising the computer-implemented steps of: determining a divisor; determining the integer quotient of the number divided by the divisor; determining the remainder of the number divided by the divisor; generating a string of quotient bits of length equal to the integer quotient, wherein each bit has the same bit value; generating a string of remainder bits representing the remainder; and generating a delimiter bit having a different bit value than the bit value of the bits in the generated string of quotient bits to indicate the end of the generated string of quotient bits, wherein the quotient bits, the delimiter bit, and the remainder bits comprise the encoded number.
Claim 15
Dependent Claim
128 words
A data compression apparatus for compressing a data buffer, the data buffer containing a plurality of symbols, each symbol occurring one or more times, comprising: means for parsing the data buffer into occurrences of symbols; means for generating a symbol table having an entry for each parsed symbol, each entry having a symbol and a unique indexing identifier; means for retrieving each occurrence of each symbol from the data buffer; means for determining the unique indexing identifier of the retrieved symbol; means for encoding the determined unique indexing identifier into a variable-length portion, a delimiter, and a fixed-length portion such that the length of the variable-length portion is based on the number of occurrences of the retrieved symbol in the data buffer; and means for outputting the encoding.
Claim 16
Dependent Claim
128 words
A data compression apparatus for compressing a data buffer, the data buffer containing a plurality of symbols, each symbol occurring one or more times, comprising: means for parsing the data buffer into occurrences of symbols; means for generating a symbol table having an entry for each parsed symbol, each entry having a symbol and a unique indexing identifier; means for retrieving each occurrence of each symbol from the data buffer; means for determining the unique indexing identifier of the retrieved symbol; means for encoding the determined unique indexing identifier into a variable-length portion, a delimiter, and a fixed-length portion such that the length of the variable-length portion is based on the number of occurrences of the retrieved symbol in the data buffer; and means for outputting the encoding.
Claim 17
Dependent Claim
27 words
The compression apparatus of claim 12 including means for determining the length of the fixed-length portion such that the total length of the encodings output is minimized.
Claim 18
Dependent Claim
82 words
The compression apparatus of claim 12 wherein the means for encoding the determined unique indexing identifier generates a variable-length portion that is a string with a length equal to the integer portion of the determined unique indexing identifier divided by 2 to the power of the length of the fixed-length portion and the fixed-length portion is the binary integer representation of the remainder of the determined unique indexing identifier divided by 2 to the power of the length of the fixed-length portion.
Claim 19
Dependent Claim
75 words
A decompression apparatus for decoding an encoded symbol, the encoded symbol represented an encoded index into a symbol table, the symbol table having a plurality of symbols, each symbol having a corresponding index into the symbol table, the decompression apparatus comprising: means for decoding the encoded index to generate a decoded index; and means for retrieving the symbol corresponding to the decoded index from the symbol table wherein the retrieved symbol represents the decoded symbol.
Claim 20
Dependent Claim
75 words
A decompression apparatus for decoding an encoded symbol, the encoded symbol represented an encoded index into a symbol table, the symbol table having a plurality of symbols, each symbol having a corresponding index into the symbol table, the decompression apparatus comprising: means for decoding the encoded index to generate a decoded index; and means for retrieving the symbol corresponding to the decoded index from the symbol table wherein the retrieved symbol represents the decoded symbol.
Claim 21
Dependent Claim
20 words
The decompression apparatus of claim 15 wherein the encoded index has a variable-length portion, a delimiter, and a fixed-length portion.
Claim 22
Dependent Claim
67 words
The decompression apparatus of claim 16 wherein the means for decoding the encoded index determines the length of the variable-length portion and the length of the fixed-length portion and decodes the index by the formula Lv*2.sup.Lf +f wherein Lv is the length of the variable-length portion, Lf is the length of the fixed-length portion, and f is the value of an integer represented by the fixed-length portion.
References Cited (Backward Citations)
US5253325A
Cited
US5010345A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-03-06 | 1998-09-05 | 1999-03-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-03-06 | 2002-09-05 | 2003-03-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-03-06 | 2006-09-05 | 2007-03-07 | $7700.00 | Window Closed / Lapsed |