Adaptive multiple dictionary data compression

• US 5,870,036 A
• Filed: 02/24/1995
• Issued: 02/09/1999
• Est. Priority Date: 02/24/1995
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Thomas, Joy Aloysius, Franaszek, Peter Anthony, Robinson, John Timothy
• Primary Examiner(s): Young, Brian K.
• Application Number:
  US08/393,967
• Time in Patent Office: 1,446 Days
• Field of Search: 341/51, 341/65, 341/59, 341/106, 341/107
• US Class Current: 341/51
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77
• 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
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/132 Sampling, masking or truncation of coding units, e.g. adaptive resampling, frame skipping, frame interpolation or high-frequency transform coefficient masking
• CPC Class Codes: H04N 19/146 Data rate or code amount at the encoder output
• CPC Class Codes: H04N 19/149 by estimating the code amount by means of a model, e.g. mathematical model or statistical model
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/593 involving spatial prediction techniques
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding
• CPC Class Codes: H04N 19/94 Vector quantisation
• CPC Class Codes: H04N 19/98 Adaptive-dynamic-range coding [ADRC]

Abstract

A system and method for compressing and decompressing data using a plurality of data compression mechanisms. Representative samples of each block of data are tested to select an appropriate one of the data compression mechanisms to apply to the block. The block is then compressed using the selected one of the mechanisms and the compressed block is provided with an identifier of the selected mechanism. For decompression, the identifier is examined to select an appropriate one of the data decompression mechanisms to apply to the block. The block is then decompressed using the selected one of the mechanisms.

Claims

1. A method for compressing data using a plurality of data compression mechanisms, comprising the steps of:

compressing, using said plurality of data compression mechanisms, a portion of a block of the data to select therefrom an appropriate one of the data compression mechanisms to apply to the block;

compressing the block using the selected one of the data compression mechanisms; and

,

providing the compressed block with an identifier of the selected one of the data compression mechanisms.

2. The method of claim 1 comprising the further step of using the identifier to identify the one of the mechanisms to be used to decompress the data.

3. The method of claim 1, wherein the data compression mechanisms are selected from at least two of a run-length encoder, an adaptive dictionary and a static dictionary.

4. The method of claim 1 wherein at least one of the data compression mechanisms comprises a dictionary.

5. The method of claim 4 wherein the dictionary is of an adaptive type.

16. The method of claim 1, wherein said plurality of data compression mechanisms comprises a set of dictionaries and further comprising modifying said set of dictionaries prior to compressing subsequent data blocks.

6. A system for coding data, comprising:

a plurality of data compression mechanisms;

a memory for storing the data to be compressed;

first logic for compressing, using said plurality of data compression mechanisms, a portion of a block of the data to select therefrom an appropriate one of the data compression mechanisms to apply to the block and for routing the data to the appropriate one of the data compression mechanisms for compression; and

second logic for providing each compressed block with an identifier of the selected one of the data compression mechanisms.

7. The system of claim 6 wherein the second logic comprises further includes means for providing at least some of the blocks with a field identifying a dictionary.

8. The system of claim 6 further comprising:

a plurality of decompression mechanisms; and

,

routing logic for using the identifier to identify the one of the mechanisms to be used to decompress the data and for routing the each data block to an appropriate one of the decompression mechanisms responsive thereto.

9. A method for decompressing data using a plurality of data decompression mechanisms, comprising:

decoding a coding identifier provided with each of a data block to select an appropriate one of the data decompression mechanisms to apply to the block, said coding identifier specifying a data compression mechanism for the block which is chosen by compressing at least a portion of the block using a plurality of data compression mechanisms to select therefrom the one appropriate data compression mechanism for the block; and

,

decompressing the block using the selected one of the data decompression mechanisms.

10. The method of claim 9 wherein the data compression mechanisms are selected from at least two of a run-length encoder, an adaptive dictionary and a static dictionary.

11. The method of claim 9 wherein at least one of the data decompression mechanisms comprises a dictionary.

12. The method of claim 11 wherein the dictionary is of an adaptive type.

17. The method of claim 9, wherein said plurality of data decompression mechanisms comprises a set of dictionaries and further comprising modifying said set of dictionaries prior to decompressing subsequent data blocks.

13. A system for coding data, comprising:

a plurality of data decompression mechanisms;

a buffer for receiving blocks of the data to be decompressed, at least some of the blocks comprising multiple data elements; and

logic for testing a coding identifier associated with each block to select an appropriate one of the data decompression mechanisms to apply to the block and for routing the block to the appropriate one of the data decompression mechanisms for decompression, said coding identifier specifying a data compression mechanism for the block which is chosen by compressing at least a portion of the block using a plurality of data compression mechanisms to select therefrom the one appropriate data compression mechanism for the block.

14. The system of claim 13 wherein the logic comprises means for using a portion of each block as a dictionary.

15. The system of claim 13 wherein the logic comprises means for selecting subset of each block for use as a dictionary, which yields the best compression.