Data compression/decompression system

• US 20030090397A1
• Filed: 11/14/2001
• Published: 05/15/2003
• Est. Priority Date: 11/14/2001
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Rasmussen, Brent D.
• Granted Patent: US 6,577,254 B2
• Time in Patent Office: Days
• 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, the controller further configured to forward the smallest compressed version of the data stream.

2. The system of claim 1, wherein the controller is configured to sub-divide the data stream.

3. The system of claim 1, wherein the controller is configured to insert a header into the smallest compressed version of the data stream.

4. The system of claim 2, wherein the controller is 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.

5. The system of claim 2, wherein the data stream is sub-divided into portions having fixed byte lengths.

6. The system of claim 5, wherein the fixed byte length is selected in response to the effectiveness of the data compression algorithms used by the plurality of data compressors over data streams of the fixed byte length.

7. The system of claim 4, wherein the table comprises a memory location for each of the sub-divisions of the compressed data stream.

8. The system of claim 4, wherein the table comprises a data length for each of the sub-divisions of the compressed data stream.

9. The system of claim 5, wherein the data stream comprises information responsive to a memory location associated with each of the sub-divisions of the data stream.

10. The system of claim 5, wherein the data stream comprises information responsive to a memory length associated with each of the sub-divisions of the data stream.

11. A method for compressing data, comprising:

receiving a data stream;

applying a plurality of data compression algorithms to the received data stream;

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

buffering the compressed version of the data stream identified in the determining step; and

generating a record indicative of which of the data compression algorithms was most effective.

12. The method of claim 11, wherein the determining step identifies a data compression algorithm over sub-portions of the data stream having fixed byte lengths.

13. The method of claim 12, wherein the fixed byte length is selected in response to the effectiveness of the plurality of data compression algorithms.

14. The method of claim 11, wherein the generating step produces information responsive to a memory location associated with each of the sub-portions of the data stream.

15. The method of claim 11, wherein the generating step produces information responsive to a memory length associated with each of the sub-portions of the data stream.

16. A data processing system, comprising:

an input memory configured to receive a compressed data stream;

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.

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

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

19. The system of claim 16, wherein the controller is configured to generate the control signal in response to information identifying sub-portions of the compressed data stream.

20. The system of claim 19, wherein the identified sub-portions of the compressed data stream have their origin in a data stream sub-divided into portions having fixed byte lengths.

21. The system of claim 20, wherein the fixed byte lengths are selected in response to the effectiveness of the data compression algorithms used in generating the compressed data stream.

22. The system of claim 18, wherein the information imbedded in the compressed data stream is responsive to a data length associated with the compressed data stream.

23. The system of claim 19, wherein the information identifying sub-portions of the compressed data stream comprises a compressed data history.

24. A method for decompressing compressed data, comprising:

receiving a compressed data stream;

identifying which of a plurality of data decompression algorithms is appropriate to apply over a sub-portion of the 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.

25. The method of claim 24, wherein the identifying step is responsive to information imbedded within the compressed data stream.

26. The method of claim 24, wherein the identifying step is responsive to information in a compressed data history.

27. The method of claim 24, wherein the determining step extracts information responsive to the length of each of a plurality of sub-portions of the compressed data stream from the compressed data stream.

28. The method of claim 24, wherein the determining step extracts information responsive to the length of each of a plurality of sub-portions of the compressed data stream from a compressed data history generated concurrently with the compressed data stream.

29. 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; and

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.

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

31. The program of claim 29, 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.

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

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

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

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

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

37. The program of claim 35, 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.

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