US4988998A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Data compression system for successively applying at least two data compression methods to an input data stream
Assignee: Storage Technology Corp
•
Filing: 1989-09-05
•
Granted: 1991-01-29
•
Expires: 2009-09-05
Abstract
Abstract The improved data compression system concurrently processes both strings of repeated characters and textual substitution of input character strings. In this system, the performance of data compression techniques based on textual substitution are improved by the use of a compact representation for identifying instances in which a character in the input data stream is repeated. This is accomplished by nesting a run length encoding system in the textual substitution system. This structure adds the recognition of runs of a repeated character before the processor performs the textual substituted data compression operation. A further performance improvement is obtained by expanding the alphabet of symbols stored in the compressor's dictionary to include both the characters of the input data stream and repeat counts which indicate the repetition of a character. The handling of these repeat counts by the textual substitution based compression technique is no different than the handling of characters, or certain modifications are made in the handling of repeat counts.
Inventors
- 👤 John T. O'Brien
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 18:51
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/46; H03M7/48; G; G06; G06T; G06T9/00; G06T9/005; H03M7/3084; H03M7/3088
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
64 words
A method of compressing an input character stream comprising the steps of: replacing a sequential repetition of a single character in said input character stream with said character and a repeat count indicative of the number of sequential repetitions of said character in said input character stream to form a once compressed character stream; and encoding said once compressed character stream using textual substitution.
Claim 2
Independent Claim
64 words
A method of compressing an input character stream comprising the steps of: replacing a sequential repetition of a single character in said input character stream with said character and a repeat count indicative of the number of sequential repetitions of said character in said input character stream to form a once compressed character stream; and encoding said once compressed character stream using textual substitution.
Claim 3
Dependent Claim
64 words
The method of claim 1 wherein said step of encoding includes the step of: replacing a string, consisting of characters in combination with repeat counts in said once compressed input character stream, that has been previously encountered and entered into a dictionary with a reference value that has been previously assigned to said previously encountered string consisting of characters in combination with repeat counts.
Claim 4
Dependent Claim
38 words
The method of claim 2 wherein said step of encoding further includes the step of: generating new reference values for strings consisting of characters in combination with repeat counts that have not been previously entered into said dictionary.
Claim 5
Dependent Claim
44 words
The method of claim 3 wherein said step of generating includes the step of: appending, in response to said not previously encountered string being followed by a character, said following character to said not previously encountered string as part of said reference value definition.
Claim 6
Dependent Claim
44 words
The method of claim 1 wherein said repetition of said single input character is greater in number than can be represented by one of said repeat counts, said step of replacing including the step of: generating a multiple repeat count representation of said repetition.
Claim 7
Dependent Claim
46 words
The method of claim 5 wherein said step of generating includes the step of: concatenating a sequence of the largest value ones of said repeat counts, said sequence of repeat counts being the largest such sequence that is less than said repetition of said single character.
Claim 8
Dependent Claim
42 words
The method of claim 6 wherein said step of generating further includes the step of: appending a repeat count to said sequence of repeat counts, said appended repeat count representative of the difference between said repetition and the value of said sequence.
Claim 9
Independent Claim
79 words
A system for compressing an input character stream comprising: means for replacing, in response to the presence of a sequential repetition of a single character in said input character stream, said sequential repetition of a single character with said character and a repeat count indicative of the number of sequential repetitions of said character in said input character stream to form a once compressed input character stream; means for encoding said once compressed input character stream using textual substitution.
Claim 10
Independent Claim
79 words
A system for compressing an input character stream comprising: means for replacing, in response to the presence of a sequential repetition of a single character in said input character stream, said sequential repetition of a single character with said character and a repeat count indicative of the number of sequential repetitions of said character in said input character stream to form a once compressed input character stream; means for encoding said once compressed input character stream using textual substitution.
Claim 11
Dependent Claim
49 words
The apparatus of claim 8 wherein said encoding means includes: means for replacing each string, consisting of characters in combination with repeat counts, in said once compressed input character stream that has been previously encountered with a reference value that had been previously assigned to said previously encountered string.
Claim 12
Dependent Claim
34 words
The system of claim 9 wherein encoding means further includes: means for generating a new reference value for each string consisting of characters in combination with repeat counts that has not been previously encountered.
Claim 13
Dependent Claim
42 words
The system of claim 10 wherein said generating means includes: means for appending, in response to said not previously encountered string being followed by a character, said following character to said not previously encountered string as part of said reference value definition.
Claim 14
Dependent Claim
42 words
The system of claim 8 wherein said repetition of said single input character is greater in number than can be represented by one of said repeat counts, said replacing means including: means for generating a multiple repeat count representation of said repetition.
Claim 15
Dependent Claim
42 words
The apparatus system of claim 12 wherein said generating means includes: means for concatenating a sequence of the largest value ones of said repeat counts, said sequence being the largest such sequence that is less than said repetition of said single character.
Claim 16
Dependent Claim
40 words
The system of claim 13 wherein said generating means further includes: means for appending a repeat count to said sequence of repeat counts, said appended repeat count representative of the difference between said repetition and the value of said sequence.
Claim 17
Independent Claim
133 words
A method of compressing an input character stream comprising the steps of: substituting the sequential repetition of a single character in said input character stream with said character and a repeat count indicative of the number of sequential repetitions of said character in said input character stream to form a once compressed input character stream; encoding said once compressed input character stream into reference values representative of strings, consisting of characters in combination with repeat counts, including the steps of: replacing each string, consisting of characters in combination with repeat counts, that has been previously encountered with a reference value that had been previously assigned to said previously encountered string, generating new reference values for strings, consisting of characters in combination with repeat counts, that have not been previously entered into a dictionary.
Claim 18
Independent Claim
133 words
A method of compressing an input character stream comprising the steps of: substituting the sequential repetition of a single character in said input character stream with said character and a repeat count indicative of the number of sequential repetitions of said character in said input character stream to form a once compressed input character stream; encoding said once compressed input character stream into reference values representative of strings, consisting of characters in combination with repeat counts, including the steps of: replacing each string, consisting of characters in combination with repeat counts, that has been previously encountered with a reference value that had been previously assigned to said previously encountered string, generating new reference values for strings, consisting of characters in combination with repeat counts, that have not been previously entered into a dictionary.
Claim 19
Independent Claim
66 words
A method of compressing an input character stream comprising the steps of: replacing a sequential repetition of a single character in said input character stream with said character and a repeat count indicative of the number of sequential repetitions of said character in said input character stream to form a once compressed input character stream; and compressing said once compressed input character stream using textual substitution.
Claim 20
Independent Claim
66 words
A method of compressing an input character stream comprising the steps of: replacing a sequential repetition of a single character in said input character stream with said character and a repeat count indicative of the number of sequential repetitions of said character in said input character stream to form a once compressed input character stream; and compressing said once compressed input character stream using textual substitution.
Claim 21
Dependent Claim
51 words
The method of claim 16 wherein said step of compressing includes the step of: replacing each string, consisting of character in combination with repeat counts, in said once compressed input character stream that have been previously encountered with a reference value that has been previously assigned to said previously encountered string.
Claim 22
Dependent Claim
38 words
The method of claim 17 wherein said step of compressing further includes the step of: generating new reference values for strings, consisting of characters in combination with repeat counts, that have not been previously entered into said dictionary.
Claim 23
Dependent Claim
44 words
The method of claim 16 wherein said repetition of said single input character is greater in number than can be represented by one of said repeat counts, said step of replacing including the step of: generating a multiple repeat count representation of said repetition.
Claim 24
Dependent Claim
43 words
The method of claim 19 wherein said step of generating includes the step of: concatenating a sequence of the largest value ones of said repeat counts, said sequence being the largest such sequence that is less than said repetition of said single character.
Claim 25
Dependent Claim
42 words
The method of claim 20 wherein said step of generating further includes the step of: appending a repeat count to said sequence of repeat counts, said appended repeat count representative of the difference between said repetition and the value of said sequence.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1994-01-28 | 1994-07-30 | 1995-01-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1998-01-28 | 1998-07-30 | 1999-01-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2002-01-28 | 2002-07-30 | 2003-01-29 | $7700.00 | Window Closed / Lapsed |