STAGED DATA COMPRESSION, INCLUDING BLOCK LEVEL LONG RANGE COMPRESSION, FOR DATA STREAMS IN A COMMUNICATIONS SYSTEM

• US 20140223029A1
• Filed: 03/15/2014
• Published: 08/07/2014
• Est. Priority Date: 07/12/2011
• Status: Active Grant

• Current Assignee: Hughes Network Systems LLC (Echostar Corporation)
• Original Assignee: Hughes Network Systems LLC (Echostar Corporation)
• Inventors: BHASKAR, Udaya, SU, Chi-Jiun
• Granted Patent: US 9,363,339 B2
• Time in Patent Office: Days
• US Class Current: 709/247
• 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/3059 Digital compression and data reduction techniques where the original information is represented by a subset or similar information, e.g. lossy compression
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78
• CPC Class Codes: H03M 7/4006 Conversion to or from arithmetic code
• CPC Class Codes: H04L 69/04 Protocols for data compression, e.g. ROHC

Abstract

Approaches for staged data compression are provided, where each stage reflects a progressive increase in granularity, resulting in a scalable approach that exhibits improved efficiency and compression performance. The first stage comprises a long-range block-level compressor that determines redundancies on a block-level basis (based on entire data blocks, as opposed to partial segments within data blocks). The second stage comprises a long-range byte-level compressor that compresses an uncompressed block based on byte segments within the block that match previously transmitted segments. The duplicate segments are replaced with pointers to matching segments within a decompressor cache. Nonmatching segments of the data block are left uncompressed and passed to a third stage short-range compressor (e.g., a grammar-based compressor). The staged progression in granularity provides advantages of maximizing the compression gain while minimizing processing and storage requirements of the compressor and decompressor.

Claims

1. A method for staged data compression, comprising:

receiving, by a long-range block-level compressor of a device, a plurality of data blocks of an input data stream, generating a hash value corresponding to each data block, and storing the hash values in a block hash table;

determining whether the hash value for each data block matches any of the hash values stored in the block hash table, wherein each hash value stored in the table corresponds to a respective previously received one of the data blocks of the input stream;

when it is determined that the hash value for a one data block of the input data stream matches a one of the hash values stored in the block hash table, generating a block-level match descriptor, and removing the one data block from the input data stream;

when it is determined that the hash value for a further data block of the input data stream does not match any of the plurality of hash values stored in the block hash table,

(i) outputting the further data block,

(ii) receiving, by a long-range byte-level compressor of the device, the further data block, and performing a long-range byte-level compression function on the further data block, which includes determining one or more bit strings of the further data block that each matches a respective bit string of a previously received data block, generating a byte-level match descriptor for each such bit string of the further data block, replacing each such bit string of the further data block with the respective byte-level match descriptor, and outputting literal byte segments reflecting any uncompressed literal segments of the further data block, and

(iii) receiving, by a short-range compressor of the device, the uncompressed literal segments of the further data block, performing a short-range compression function on the literal segments, and generating resulting compressor codes; and

multiplexing the block-level match descriptor, the byte-level match descriptors and the compressor codes.

2. The method of claim 1, wherein the block-level match descriptor comprises a block-level match indicator, a location reference corresponding to a storage location within a decompressor data cache of a previously received one of the data blocks of the input data stream that matches the one data block, and a length value indicating the length of the matching data block.

3. The method of claim 1, wherein each byte-level match descriptor comprises a location reference corresponding to a storage location within a decompressor data cache of the bit string of the previously received data block that matches the respective bit string of the further data block, and a length value indicating the length of the matching bit string.

4. The method of claim 1, further comprising:

determining, with respect to each new data block of the input data stream, one or more older data blocks of the input data stream that will be overwritten by the new data block within a decompressor data cache; and

marking as stale the hash values within the block hash table corresponding to the data blocks that will be overwritten.

5. The method of claim 4, wherein each determined hash value is stored in the block hash table along with metadata providing a storage location within the decompressor data cache where the corresponding data block is stored and providing a pointer to the oldest data block within the decompressor data cache, and wherein the determination of the one or more older data blocks that will be overwritten comprises:

assessing the block hash table, based on the metadata, starting with the oldest hash value and continuing until reaching a hash value corresponding to a first data block that will not be overwritten in the decompressor data cache.

6. The method of claim 1, wherein the long-range byte-level compression function further includes, for each bit string of the further data block that matches a respective bit string of a previously received data block, determining whether the bit string has been output as or within a one of the previous literal byte segments, and, when it is determined that the bit string has been output as or within a one of the previous literal byte segments, skipping the byte-level compression of the bit string and outputting the bit string as a literal byte segment for compression via the short-range compression function.

7. The method of claim 6, wherein the determination of whether the bit string has been output as or within a one of the previous literal byte segments includes maintaining a list of descriptors respectively corresponding to previously output literal byte segments and determining whether the bit string is contained in the list of descriptors.

8. The method of claim 1, wherein the determination of the one or more bit strings of the further data block that each matches a respective bit string of a previously received data block comprises:

generating a fingerprint corresponding to each of the one or more bit strings of the further data block based on a sliding fingerprint window, and storing the finger prints in a byte hash table;

determining whether the fingerprint for each of one or more of the bit strings of the further data block matches any of the fingerprints stored in the byte has table, wherein each fingerprint stored in the table corresponds to a respective bit string of the previously received data blocks; and

when it is determined that the fingerprint for a one of the bit strings of the further data block matches a one of the fingerprints stored in the byte hash table, determining whether the one bit string matches the bit string corresponding to the matched fingerprint in the byte hash table, wherein the bit strings of the previously received data blocks are stored in a compressor byte cache.

9. The method of claim 8, wherein, when it is determined that the fingerprint for a one of the bit strings of the further data block matches a one of the fingerprints stored in the byte hash table, the determination of the one or more bit strings of the further data block that each matches a respective bit string of a previously received data block further comprises:

expanding the match determination by determining bit strings to the left and to the right of the one bit string of the further data block that match respective bit strings to the left and to the right of the bit string stored in the compressor byte cache that matches the one bit string of the further data block.

10. An apparatus for staged data compression, comprising:

a long-range block-level compressor configured to receive a plurality of data blocks of an input data stream, to generate a hash value corresponding to each data block, to store the hash values in a block hash table within a memory of the apparatus, and to determine whether the hash value for each data block matches any of the hash values stored in the block hash table, wherein each hash value stored in the table corresponds to a respective previously received one of the data blocks of the input stream; and

wherein, when it is determined that the hash value for a one data block of the input data stream matches a one of the hash values stored in the block hash table, the long-range block-level compressor is further configured to generate a block-level match descriptor and to remove the one data block from the input data stream, and

wherein, when it is determined that the hash value for a further data block of the input data stream does not match any of the plurality of hash values stored in the block hash table, the long-range block-level compressor is further configured to output the further data block; and

the apparatus further comprising a long-range byte-level compressor configured to receive the further data block and to perform a long-range byte-level compression function on the further data block, wherein the long-range byte-level compression function includes determining one or more bit strings of the further data block that each matches a respective bit string of a previously received data block, generating a byte-level match descriptor for each such bit string of the further data block, replacing each such bit string of the further data block with the respective byte-level match descriptor, and outputting literal byte segments reflecting any uncompressed literal segments of the further data block; and

the apparatus further comprising a short-range compressor configured to receive the uncompressed literal segments of the further data block, to perform a short-range compression function on the literal segments, and to generate resulting compressor codes; and

the apparatus further comprising a multiplexer configured to multiplex the block-level match descriptor, the byte-level match descriptors and the compressor codes.

11. The apparatus of claim 10, wherein the block-level match descriptor comprises a block-level match indicator, a location reference corresponding to a storage location within a decompressor data cache of a previously received one of the data blocks of the input data stream that matches the one data block, and a length value indicating the length of the matching data block.

12. The apparatus of claim 10, wherein each byte-level match descriptor comprises a location reference corresponding to a storage location within a decompressor data cache of the bit string of the previously received data block that matches the respective bit string of the further data block, and a length value indicating the length of the matching bit string.

13. The apparatus of claim 10, wherein the long-range block-level compressor is further configured to determine, with respect to each new data block of the input data stream, one or more older data blocks of the input data stream that will be overwritten by the new data block within a decompressor data cache, and to mark as stale the hash values within the block hash table corresponding to the data blocks that will be overwritten.

14. The apparatus of claim 13, wherein each determined hash value is stored in the block hash table along with metadata providing a storage location within the decompressor data cache where the corresponding data block is stored and providing a pointer to the oldest data block within the decompressor data cache, and wherein the determination of the one or more older data blocks that will be overwritten comprises:

assessing the block hash table, based on the metadata, starting with the oldest hash value and continuing until reaching a hash value corresponding to a first data block that will not be overwritten in the decompressor data cache.

15. The apparatus of claim 10, wherein the long-range byte-level compression function further includes, for each bit string of the further data block that matches a respective bit string of a previously received data block, determining whether the bit string has been output as or within a one of the previous literal byte segments, and, when it is determined that the bit string has been output as or within a one of the previous literal byte segments, skipping the byte-level compression of the bit string and outputting the bit string as a literal byte segment for compression via the short-range compression function.

16. The apparatus of claim 15, wherein the determination of whether the bit string has been output as or within a one of the previous literal byte segments includes maintaining a list of descriptors respectively corresponding to previously output literal byte segments and determining whether the bit string is contained in the list of descriptors.

17. The apparatus of claim 10, wherein the determination of the one or more bit strings of the further data block that each matches a respective bit string of a previously received data block comprises:

generating a fingerprint corresponding to each of the one or more bit strings of the further data block based on a sliding fingerprint window, and storing the finger prints in a byte hash table;

determining whether the fingerprint for each of one or more of the bit strings of the further data block matches any of the fingerprints stored in the byte has table, wherein each fingerprint stored in the table corresponds to a respective bit string of the previously received data blocks; and

when it is determined that the fingerprint for a one of the bit strings of the further data block matches a one of the fingerprints stored in the byte hash table, determining whether the one bit string matches the bit string corresponding to the matched fingerprint in the byte hash table, wherein the bit strings of the previously received data blocks are stored in a compressor byte cache.

18. The apparatus of claim 17, wherein, when it is determined that the fingerprint for a one of the bit strings of the further data block matches a one of the fingerprints stored in the byte hash table, the determination of the one or more bit strings of the further data block that each matches a respective bit string of a previously received data block further comprises:

expanding the match determination by determining bit strings to the left and to the right of the one bit string of the further data block that match respective bit strings to the left and to the right of the bit string stored in the compressor byte cache that matches the one bit string of the further data block.