Data compression/decompression system

• US 6,577,254 B2
• Filed: 11/14/2001
• Issued: 06/10/2003
• Est. Priority Date: 11/14/2001
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Rasmussen, Brent D.
• Primary Examiner(s): Williams, Howard L.
• Application Number:
  US09/992,970
• Publication Number:
  US 20030090397A1
• Time in Patent Office: 573 Days
• Field of Search: 341/51, 341/87
• US Class Current: 341/51
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• 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

An improved system and method for data compression/decompression are disclosed. A data compression system may comprise an input memory, a plurality of data compressors, and a controller. In preferred embodiments, the controller selectively forwards data compressed with the most efficient data compressor over sub-portions of a data stream. A data decompression system may be implemented with an input memory, a data compression method identifier, and a plurality of data decompressors. In preferred embodiments, the data compression method identifier selectively applies an appropriate data decompressor over sub-portions of a compressed data stream. A method for compressing data can be summarized by the following steps: receiving a data stream; applying a plurality of data compression algorithms to the data stream; determining which of the plurality of data compression algorithms was most effective; buffering the compressed data; and generating a record indicative of which the applied data compression algorithms. A method for decompressing data can be summarized as follows: receiving a compressed data stream; identifying which of a plurality of data decompression algorithms is appropriate to apply over a sub-portion of the compressed data stream; determining the length of the compressed sub-portion of the data stream; and applying the identified data decompression algorithm to the received compressed data stream for the length in bytes generated in the determining step.

Claims

1. A data processing system, comprising:

an input memory configured to receive a data stream;

a plurality of data compressors communicatively coupled with the input memory, each of the plurality of data compressors configured to apply a data compression algorithm to the data stream to generate a respective compressed version of the data stream; and

a controller communicatively coupled with each of the plurality of data compressors, the controller configured to;

determine which of the plurality of data compressors generated the smallest compressed version of the data stream;

sub-divide the data stream into a plurality of intervals each having a fixed length;

increase the length of each of the fixed intervals in response to improving data compression efficiency with a corresponding increase in the length of each of the fixed intervals; and

forward the smallest compressed version of the data stream.

2. The system of claim 1, wherein the controller is further configured to insert a header associated with each of the plurality of intervals, the header identifying the data compression scheme used to generate the smallest compressed version of the data stream.

3. The system of claim 1, wherein the controller is further configured to generate a table comprising information responsive to the particular one of the plurality of data compressors that generated the smallest compressed version of the data stream.

4. The system of claim 3, wherein the table comprises a memory location for each of the intervals of the compressed data stream.

5. The system of claim 3, wherein the table comprises a data length for each of the intervals of the compressed data stream.

6. The system of claim 1, wherein the data stream comprises information responsive to a memory location associated with each of the intervals of the data stream.

7. The system of claim 1, wherein the data stream comprises information responsive to a memory length associated with each of the intervals of the data stream.

8. A method for compressing data, comprising:

receiving a data stream;

sub-dividing the data stream into a plurality of intervals each having a fixed length;

applying the plurality of intervals to a plurality of data compression algorithms;

determining which of the plurality of data compression algorithms was most effective over a sub-portion of the data stream; and

increasing the length of each of the intervals in response to improving data compression efficiency with a corresponding increase in the length of each of the fixed intervals.

9. The method of claim 8, further comprising generating a record indicative of which of the data compression algorithms was most effective.

10. The method of claim 9, wherein generating produces information responsive to a memory location associated with each of the plurality of intervals of the data stream.

11. The method of claim 9, wherein generating produces information responsive to a memory length associated with each of the plurality of intervals of the data stream.

12. A data processing system, comprising:

an input memory configured to receive a compressed data stream, the compressed data stream comprising a plurality of intervals, the length of the intervals responsive to improving data compression efficiency over a corresponding increase in length of the intervals;

a controller communicatively coupled with the input memory, the controller configured to apply information indicative of the data compression algorithm used to compress the data stream in order to generate a control signal; and

a plurality of data decompressors each selectively coupled to an output of the input memory to receive the compressed data stream, wherein a particular data decompressor is coupled to the input memory in response to the control signal to generate a reproduction of a clear text version of the compressed data stream.

13. The system of claim 12, wherein the controller is configured to generate the control signal in response to a compressed data history.

14. The system of claim 12, wherein the controller is configured to generate the control signal in response to information imbedded within the compressed data stream.

15. The system of claim 12, wherein the controller is configured to generate the control signal in response to information identifying a plurality of intervals within the compressed data stream.

16. The system of claim 15, wherein the information identifying the plurality of intervals within the compressed data stream comprises a compressed data history.

17. A method for decompressing compressed data, comprising:

receiving a compressed data stream, the compressed data stream comprising a plurality of intervals, the length of the intervals responsive to improving data compression efficiency over a corresponding increase in length of the intervals;

identifying which of a plurality of data decompression algorithms is appropriate to apply over the plurality of intervals within the data stream;

determining the length of the compressed intervals of the data stream; and

applying the identified data decompression algorithm to the received compressed data stream for the length in bytes generated in the determining step.

18. The method of claim 17, wherein identifying is responsive to information imbedded within the compressed data stream.

19. The method of claim 17, wherein identifying is responsive to information in a compressed data history.

20. The method of claim 17, wherein determining extracts information responsive to the length of each of the plurality of intervals within the compressed data stream.

21. The method of claim 17, wherein determining extracts information responsive to the length of each the plurality of intervals within the compressed data stream from a compressed data history generated concurrently with the compressed data stream.

22. A computer program embodied on a computer-readable medium, the computer program, comprising:

a first code segment that receives a data stream, the first code segment configured to forward the data stream to a plurality of data compression algorithms to generate a plurality of compressed representations of the data stream;

a second code segment configured to receive and compare the compressed representations of the data stream, wherein the second code segment selectively forwards one of the plurality of compressed representations; and

a third code segment configured to increase the length of each of a plurality of intervals used to generate the plurality of compressed representations in response to improving data compression efficiency with a corresponding increase in the length of each of the plurality of intervals.

23. The program of claim 22, wherein the second code segment is configured to forward the most compressed representation of the data stream.

24. The program of claim 22, wherein the second code segment is configured to forward information responsive to the particular data compression algorithm that generated the most compressed representation of the data stream.

25. The program of claim 24, wherein the information is forwarded to a data compression history table.

26. The program of claim 24, wherein the information is forwarded within the compressed representation of the data stream.

27. The program of claim 26, wherein the information is inserted in a header associated with each of a plurality of segments of the data stream.

28. A computer program embodied on a computer-readable medium, the computer program, comprising:

a first code segment configured to receive a compressed data stream, the compressed data stream comprising a plurality of intervals, the length of the intervals responsive to improving data compression efficiency over a corresponding increase in length of the intervals, the first code segment configured to identify one of a plurality of data decompression algorithms wherein the identified data decompression algorithm is the corollary to a data compression algorithm used to compress an original version of the data stream; and

a second code segment configured to apply the identified data decompression algorithm to reconstruct the original data stream.

29. The program of claim 28, wherein the first code segment is configured to identify the appropriate data decompression algorithm by retrieving information from a data compression history table.

30. The program of claim 28, wherein the first code segment is configured to identify the appropriate data decompression algorithm by extracting information forwarded within the compressed representation of the data stream.

31. The program of claim 30, wherein the information is extracted from a header associated with each of a plurality of compressed segments of the data stream.