Data compression system for successively applying at least two data compression methods to an input data stream

• US 4,988,998 A
• Filed: 09/05/1989
• Issued: 01/29/1991
• Est. Priority Date: 09/05/1989
• Status: Expired due to Term

• Current Assignee: Storage Technologies Corporation (Oracle Corporation)
• Original Assignee: Storage Technologies Corporation (Oracle Corporation)
• Inventors: O'Brien, John T.
• Primary Examiner(s): Shoop, Jr., William M.
• Assistant Examiner(s): WILLIAMS, HOWARD L
• Application Number:
  US07/403,084
• Time in Patent Office: 511 Days
• Field of Search: 341/51, 341/52, 341/55, 341/87, 341/95, 341/60, 341/63, 341/67, 341/88, 341/106, 341/107
• US Class Current: 341/55
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78
• CPC Class Codes: H03M 7/48 alternating with other codes during the code conversion process, e.g. run-length coding being performed only as long as sufficientlylong runs of digits of the same kind are present

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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.

17. 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.

18. 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.

19. 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.

20. 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.

21. 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.