Parallel compression and decompression using a cooperative dictionary

• US 5,729,228 A
• Filed: 07/06/1995
• Issued: 03/17/1998
• Est. Priority Date: 07/06/1995
• Status: Expired due to Term

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Thomas, Joy Aloysius, Franaszek, Peter Anthony, Robinson, John Timothy
• Primary Examiner(s): Gaffin, Jeffrey A.
• Assistant Examiner(s): KOST, JASON L
• Application Number:
  US08/498,948
• Time in Patent Office: 985 Days
• Field of Search: 341/106, 341/51, 341/61, 341/64, 341/65, 341/67, 341/81, 341/87
• US Class Current: 341/106
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77

Abstract

A method and apparatus for compressing a block of data using a shared dictionary. Data to be compressed is divided into subblocks which are each provided to a respective compressor in a plurality of compressors. The compressors cooperatively construct a dynamic compression dictionary and compress the subblocks in parallel using the dictionary. Compressed subblocks output by the compressors are concatenated to form a compressed block.

Claims

1. An apparatus for compressing a block of data, the apparatus comprising:

a splitter having an input configured to receive the block of data dividing the block of data and having an output providing sub-blocks formed from the block of data;

a plurality of compression engines configured to cooperatively construct a dynamic compression dictionary, wherein at least one sub-block is used in the compression of another sub-block; and

,

a concatenator coupled to outputs of the compression engines, and having an output providing a compressed block as formed as a concatenation of compressed sub-blocks produced by the compression engines.

2. The apparatus of claim 1 further comprising:

a router coupled to the splitter to receive the sub-blocks and connected to the compression engines to provide selected ones of the sub-blocks to respective ones of the compression engines.

3. The apparatus of claim 1 wherein the compression engines include means for substituting for phrases in the sub-blocks, pointers to a common dictionary including a plurality of subdictionaries, each of the subdictionaries including entries indicative of portions of the sub-blocks which have already been compressed.

4. The apparatus of claim 1 wherein the compressed block includes pointers to entries in the dictionary.

5. The apparatus of claim 1 further comprising an associative memory for storing the dictionary.

6. The apparatus of claim 1 wherein the dictionary comprises a plurality of physically distinct but logically shared dictionaries.

7. A method for compressing a block of data, comprising the steps of:

dividing the block of data into sub-blocks;

providing each of the sub-blocks to a respective compressor in a plurality of compressors;

cooperatively constructing a dynamic compression dictionary by the plurality of compressors, wherein at least one sub-block is used in the compression of another sub-block;

compressing the sub-blocks using the dynamic compression dictionary; and

,

concatenating outputs of the compressors to form a compressed block.

8. The method of claim 7 wherein the compressing is performed by substituting for phrases in the sub-blocks, pointers to a common dictionary including a plurality of subdictionaries, each of the subdictionaries comprising entries indicative of portions of the sub-blocks which have already been compressed.

9. The method of claim 7 wherein the compressed block includes pointers to entries in the dictionary.

10. A method of decompressing a block of compressed data, comprising the steps of:

dividing the block of the compressed data into sub-blocks;

assigning each of the sub-blocks to a respective decompressor in a plurality of decompressors;

cooperatively constructing a dynamic decompression dictionary by the plurality of decompressors;

decompressing the sub-block using the dynamic decompression dictionary, wherein said decompressing uses at least one other sub-block;

concatenating outputs of the decompressors to form a decompressed block.

11. The method of claim 10 wherein the decompressing is performed by substituting pointers to a common dictionary with phrases, the common dictionary including a plurality of subdictionaries, each of the subdictionaries comprising entries indicative of portions of the sub-blocks which have already been decompressed.

12. The method of claim 10 wherein the compressed block includes control data indicative of the location and extent of each compressed sub-block in the compressed block.

13. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for decompressing a block of data, the method steps comprising:

dividing the block of the compressed data into sub-blocks;

assigning each of the sub-blocks to a respective decompressor in a plurality of decompressors;

cooperatively constructing a dynamic decompression dictionary by the plurality of decompressors;

decompressing the sub-blocks using the dynamic decompression dictionary, wherein said decompressing uses at least one other sub-block;

concatenating outputs of the decompressors to form a decompressed block.

14. The program storage device of claim 13 wherein the decompressing is performed by substituting pointers to a common dictionary with phrases, the common dictionary including a plurality of subdictionaries, each of the subdictionaries comprising entries indicative of portions of the sub-locks which have already been decompressed.

15. A method for compressing data, comprising the steps of:

providing multiple data streams to a plurality of compressors which can operate in parallel;

cooperatively constructing a dynamic compression dictionary by the plurality of compressors; and

,

compressing the data streams using the dynamic compression dictionary, wherein data from at least one data stream is used in the compression of data from another data stream.

16. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for compressing a block of data, the method steps comprising:

dividing the block of data into sub-blocks;

providing each of the sub-blocks to a respective compressor in a plurality of compressors;

cooperatively constructing a dynamic compression dictionary by the plurality of compressors;

compressing the sub-blocks using the dynamic compression dictionary, wherein at least one sub-block is used in the compression of another sub-block; and

,

concatenating outputs of the compressors to form a compressed block.

17. A computer readable memory that can be used to direct a computer to compress a block of data when used by the computer, comprising:

means for distributing portions of the block of data among a plurality of compressors which can operate in parallel;

means for causing the compressors to cooperatively construct a dynamic compression dictionary and to compress the block of data using the dynamic compression dictionary, wherein at least one sub-block is used in the compression of another sub-block.

18. A computer readable memory that can be used to direct a computer to decompress a block of data when used by the computer, comprising:

means for dividing the block of the compressed data into sub-blocks;

means for assigning each of the sub-blocks to a respective decompressor in a plurality of decompressors;

means for causing the plurality of decompressors to cooperatively construct a dynamic decompression dictionary and to decompress the sub-blocks using the dynamic decompression dictionary wherein said decompressing uses at least one other sub-block; and

means for concatenating outputs of the decompressors to form a decompressed block.

19. A data structure instantiated in a computer readable memory, comprising:

a block of compressed data corresponding to an original block of uncompressed data, wherein the block of compressed data includes pointers to entries in the original block of uncompressed data and wherein at least some of the pointers point forward and at least some of the pointers point backward relative to an actual position of a given compressed phrase in the original block.

20. A method of data compression where a set of at least two compressors operating in parallel, each on a possibly distinct data stream, cooperate in constructing a dictionary to be used in compression, so that decompression of each output stream produced by a compressor accesses at least one other output stream produced by the set.

21. A method of data compression using multiple compressors operating in parallel, or possibly distinct data streams, where each compressor operates by sending pointers to phrases seen earlier with data streams, or in the data streams of the other compressors.

22. A method for decompressing data, comprising the steps of:

providing multiple data streams to a plurality of decompressors which can operate in parallel;

cooperatively constructing a dynamic decompression dictionary by the plurality of decompressors; and

,

decompressing the data streams using the dynamic decompression dictionary, wherein data from at least one data stream is used in the compression of data from another data stream.