US5729228A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Parallel compression and decompression using a cooperative dictionary
Assignee: GlobalFoundries Inc
•
Filing: 1995-07-06
•
Granted: 1998-03-17
•
Expires: 2015-07-06
Abstract
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.
Inventors
- 👤 Peter Anthony Franaszek
- 👤 John Timothy Robinson
- 👤 Joy Aloysius Thomas
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 18:23
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/3084; H03M7/3086; G; G06; G06T; G06T9/00; G06T9/005
Claims Analysis
Total Claims: 34
Claim 1
Independent Claim
97 words
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.
Claim 2
Independent Claim
97 words
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.
Claim 3
Dependent Claim
37 words
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.
Claim 4
Dependent Claim
45 words
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.
Claim 5
Dependent Claim
16 words
The apparatus of claim 1 wherein the compressed block includes pointers to entries in the dictionary.
Claim 6
Dependent Claim
14 words
The apparatus of claim 1 further comprising an associative memory for storing the dictionary.
Claim 7
Dependent Claim
18 words
The apparatus of claim 1 wherein the dictionary comprises a plurality of physically distinct but logically shared dictionaries.
Claim 8
Independent Claim
76 words
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.
Claim 9
Independent Claim
76 words
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.
Claim 10
Dependent Claim
44 words
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.
Claim 11
Dependent Claim
16 words
The method of claim 7 wherein the compressed block includes pointers to entries in the dictionary.
Claim 12
Independent Claim
74 words
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.
Claim 13
Independent Claim
74 words
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.
Claim 14
Dependent Claim
44 words
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.
Claim 15
Dependent Claim
26 words
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.
Claim 16
Dependent Claim
93 words
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.
Claim 17
Dependent Claim
93 words
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.
Claim 18
Dependent Claim
46 words
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.
Claim 19
Independent Claim
63 words
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.
Claim 20
Independent Claim
63 words
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.
Claim 21
Dependent Claim
96 words
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.
Claim 22
Dependent Claim
96 words
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.
Claim 23
Dependent Claim
80 words
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.
Claim 24
Dependent Claim
80 words
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.
Claim 25
Dependent Claim
97 words
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.
Claim 26
Dependent Claim
97 words
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.
Claim 27
Dependent Claim
73 words
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.
Claim 28
Dependent Claim
73 words
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.
Claim 29
Independent Claim
55 words
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.
Claim 30
Independent Claim
55 words
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.
Claim 31
Independent Claim
39 words
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.
Claim 32
Independent Claim
39 words
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.
Claim 33
Independent Claim
63 words
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.
Claim 34
Independent Claim
63 words
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.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-03-16 | 2001-09-15 | 2002-03-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-03-16 | 2005-09-15 | 2006-03-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-03-16 | 2009-09-15 | 2010-03-17 | $7700.00 | Window Closed / Lapsed |