Adaptive data compression

Patent metadata

Field	Value
Publication number	US-9515679-B1
Application number	US-201514712045-A
Country	US
Kind code	B1
Filing date	May 14, 2015
Priority date	May 14, 2015
Publication date	Dec 6, 2016
Grant date	Dec 6, 2016

Abstract

Methods, computing systems and computer program products implement embodiments of the present invention that include accessing, from a sequence of multiple data segments including a first data segment at a first location in the sequence followed by additional data segments having respective additional locations in the sequence, a current given data segment in the sequence. In some embodiments, data to be compressed is received and partitioned into the multiple data segments. The current data segment is compressed the current data segment using a first minimal match length, and a compression ratio is calculated for the compressed current data segment. Based on the compression ratio and the respective location of the current data segment, a second minimal match length is selected, a subsequent data segment that immediately follows the current data segment in the sequence is accessed, and the subsequent data segment is compressed using the second minimal match length.

First claim

The invention claimed is:

1. A method, comprising:
accessing, from a sequence of multiple data segments comprising a first data segment at a first location in the sequence followed by additional data segments having respective additional locations in the sequence, a current given data segment in the sequence;
compressing the current data segment using a first minimal match length;
calculating a compression ratio for the compressed current data segment;
selecting, based on the compression ratio and the respective location of the current data segment, a second minimal match length;
accessing a subsequent data segment that immediately follows the current data segment in the sequence;
compressing the subsequent data segment using the second minimal match length; and
specifying a high compression threshold, a low compression threshold, a maximum change threshold, a default minimal match length, and one or more of the respective locations as respective checkpoints;
wherein selecting the second minimal match length comprises setting the second minimal match length to a value greater than the first minimal match length upon detecting that the compression ratio is less than the low compression threshold.

2. The method according to claim 1 , wherein the first minimal match length comprises the default minimal match length upon the current data segment comprising the first data segment in the sequence.

3. The method according to claim 1 , wherein selecting the second minimal match length comprises setting the second minimal match length to a value less than the first minimal match length upon detecting that the compression ratio is greater than the high compression threshold.

4. The method according to claim 1 , wherein the compression ratio comprises a current compression ratio, and comprising upon the current data segment not comprising the first data segment in the sequence, identifying a first previous data segment that immediately precedes the current data segment in the sequence, identifying a third minimal match length that was used to compress the first previous data segment, identifying a previous compression ratio for the first previous data segment, and identifying a second previous data segment in the sequence that was most recently compressed using a fourth minimal match length different from the first minimal match length.

5. The method according to claim 4 , wherein selecting the second minimal match length comprises setting the second minimal match length to the third minimal match length upon detecting that the current compression ratio is greater than the previous compression ratio.

6. The method according to claim 4 , wherein selecting the second minimal match length comprises setting the second minimal match length to the fourth minimal match length upon detecting respective location of the current data segment comprises one of the one or more checkpoints.

7. The method according to claim 4 , wherein selecting the second minimal match length comprises setting the second minimal match length to the default minimal match length upon detecting that an absolute value of a difference between the first and the second compression ratios exceeds the maximum change threshold.

8. An apparatus, comprising:
a memory configured to store a sequence of multiple data segments comprising a first data segment at a first location in the sequence followed by additional data segments having respective additional locations in the sequence; and
a processor configured:
to access a current data segment in the sequence,
to compress the current data segment using a first minimal match length,
to calculate a compression ratio for the compressed current data segment,
to select, based on the compression ratio and the respective location of the current data segment, a second minimal match length,
to access a subsequent data segment that immediately follows the current data segment in the sequence,
to compress the subsequent data segment using the second minimal match length, and
to specify a high compression threshold, a low compression threshold, a maximum change threshold, a default minimal match length, and one or more of the respective locations as respective checkpoints;
wherein selecting the second minimal match length comprises setting the second minimal match length to a value greater than the first minimal match length upon detecting that the compression ratio is less than the low compression threshold.

9. The apparatus according to claim 8 , wherein the first minimal match length comprises the default minimal match length upon the current data segment comprising the first data segment in the sequence.

10. The apparatus according to claim 8 , wherein the processor is configured to select the second minimal match length by setting the second minimal match length to a value less than the first minimal match length upon detecting that the compression ratio is greater than the high compression threshold.

11. The apparatus according to claim 8 , wherein the compression ratio comprises a current compression ratio, and wherein upon the current data segment not comprising the first data segment in the sequence, the processor is configured to identify a first previous data segment that immediately precedes the current data segment in the sequence, to identify a third minimal match length that was used to compress the first previous data segment, to identify a previous compression ratio for the first previous data segment, and to identify a second previous data segment in the sequence that was most recently compressed using a fourth minimal match length different from the first minimal match length.

12. The apparatus according to claim 11 , wherein the processor is configured to select the second minimal match length by setting the second minimal match length to the third minimal match length upon detecting that the current compression ratio is greater than the previous compression ratio.

13. The apparatus according to claim 11 , wherein the processor is configured to select the second minimal match length by setting the second minimal match length to the fourth minimal match length upon detecting respective location of the current data segment comprises one of the one or more checkpoints.

14. The apparatus according to claim 11 , wherein the processor is configured to select the second minimal match length by setting the second minimal match length to the default minimal match length upon detecting that an absolute value of a difference between the first and the second compression ratios exceeds the maximum change threshold.

15. The apparatus according to claim 8 , wherein prior to storing the sequence of the multiple data segments in the memory, the processor is configured to receive the multiple data segments from a data source selected from a group consisting of a storage device and a computer network.

16. A computer program product, the computer program product comprising:
a non-transitory computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising:
computer readable program code configured to access, from a sequence of multiple data segments comprising a first data segment at a first location in the sequence followed by additional data segments having respective additional locations in the sequence, a current given data segment in the sequence;
computer readable program code configured to compress the current data segment using a first minimal match length;
computer readable program code configured to calculate a compress

Assignees

• IBM

Inventors

• Harnik Danny
• Khaitzin Ety
• Marenkov Sergey
• Sotnikov Dmitry

Classifications

• H03M7/3084 Primary

  using adaptive string matching, e.g. the Lempel-Ziv method · CPC title

• H03M7/46 Primary

  Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind · CPC title

• H03M7/6076

  Selection between compressors of the same type · CPC title