Method and apparatus to process data based upon estimated compressibility of the data

• US 9,246,511 B2
• Filed: 03/20/2012
• Issued: 01/26/2016
• Est. Priority Date: 03/20/2012
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Inventors: Dror, Itai, Kipnis, Alon
• Primary Examiner(s): SNYDER, STEVEN G
• Application Number:
  US13/425,016
• Publication Number:
  US 20130254441A1
• Time in Patent Office: 1,407 Days
• Field of Search: None
• US Class Current: 1/1
• 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/3071 Prediction
• CPC Class Codes: H03M 7/3079 Context modeling
• CPC Class Codes: H04L 69/04 Protocols for data compression, e.g. ROHC

Abstract

A method includes, in a data storage device, determining an estimated compression ratio. The estimated compression ratio is based on hash values of a subset of a data set. The method includes selectively processing the data set based on the estimated compression ratio prior to storage of data associated with the data set in a memory of the data storage device.

Claims

1. A data storage device comprising:

a memory configured to store a data set, the data set including a first plurality of data elements; and

processing hardware coupled to the memory and configured to;

identify a first set of data elements of the data set, wherein the first set of data elements is a subset of the data set and is distinct from a second set of data elements of the data set, wherein data elements of the second set are interspersed among data elements of the first set;

generate multiple hash values for the first set of data elements; and

determine an estimated compression ratio based on the multiple hash values.

2. The data storage device of claim 1, further comprising a compressor, wherein the processing hardware is further configured to determine, based on comparing the estimated compression ratio to a threshold value, whether to initiate a compression operation of the data set at the compressor and to determine a type of compression to apply to the data set based on the estimated compression ratio.

3. The data storage device of claim 1, wherein a data element of the second set is positioned between first and second data elements of the first set.

4. The data storage device of claim 1, wherein the processing hardware is further configured to select an error correction code encoding scheme based on the estimated compression ratio.

5. A data storage device comprising:

a memory; and

processing hardware coupled to the memory and configured to;

determine an estimated compression ratio of data to be stored in the memory based on identifying first data elements that are interspersed with second data elements;

select an error correction code encoding scheme based on the estimated compression ratio;

generate encoded data by applying the error correction code encoding scheme to the data or to a compressed version of the data; and

store the encoded data in the memory.

6. The data storage device of claim 5, wherein the processing hardware is further configured to, prior to applying the error correction code encoding scheme to the compressed version of the data:

perform a comparison between the estimated compression ratio and a threshold value; and

compress the data to generate the compressed version of the data in response to the estimated compression ratio being less than the threshold value.

7. The data storage device of claim 5, wherein the processing hardware is further configured to, prior to compressing the data to generate the compressed version of the data:

divide the data into a plurality of data elements;

select a subset of data elements from the plurality of data elements; and

estimate the compression ratio based on the selected subset of data elements.

8. The data storage device of claim 7, wherein the processing hardware is further configured to estimate the compression ratio based on the selected subset of data elements by:

generating a number of hash values for the selected subset of data elements;

determining a number of distinct hash values generated based on the selected subset of data elements;

identifying an expected number of distinct hash values; and

estimating the compression ratio as a function of a ratio of the number of distinct hash values and the expected number of distinct hash values.

9. The data storage device of claim 7, wherein the processing hardware is further configured to estimate the compression ratio based on the subset of data elements by:

generating a number of hash values from the selected subset of data elements;

determining a number of collisions based on multiple hash values generated based on the subset of data elements; and

accessing a lookup table that includes multiple estimated compression ratios, wherein the estimated compression ratio is determined from the multiple estimated compression ratios of the lookup table based on the number of collisions.

10. The data storage device of claim 5, further comprising an error correction code encoder configured to select the error correction code encoding scheme from multiple error correction code encoding schemes in response to the error correction code encoder receiving the estimated compression ratio, wherein each error correction code encoding scheme of the multiple error correction code encoding schemes corresponds to a different compression algorithm of a plurality of compression algorithms.

11. The data storage device of claim 5, wherein the processing hardware is further configured to:

generate multiple hash values for data to be stored in the memory;

determine the estimated compression ratio based on the multiple hash values; and

after the estimated compression ratio is determined, compress the data to generate the compressed data.

12. A method comprising:

in a data storage device, performing;

identifying a first set of data elements of a data set, wherein the first set of data elements is a subset of the data set and is distinct from a second set of data elements of the data set, and wherein data elements of the second set are interspersed among data elements of the first set;

generating multiple hash values for the first set of data elements; and

determining an estimated compression ratio based on the multiple hash values.

13. The method of claim 12, further comprising determining whether to initiate a compression operation of the data set at a compressor of the data storage device based on comparing the estimated compression ratio to a threshold value.

14. The method of claim 13, further comprising determining to initiate the compression operation in response to the estimated compression ratio being less than the threshold value.

15. The method of claim 12, further comprising selecting, based on the estimated compression ratio, a type of error correction code encoding scheme to apply to a representation of the data set.

16. The method of claim 12, wherein the estimated compression ratio is determined based on a count of collisions of the multiple hash values or based on a number of distinct values of the multiple hash values.

17. The method of claim 12, wherein the estimated compression ratio is determined based on a comparison of a count of collisions of the multiple hash values to an expected number of collisions, and wherein a collision occurs when a first hash value of the multiple hash values has the same value as a second hash value of the multiple hash values.

18. The method of claim 12, further comprising, after determining the estimated compression ratio, generating at least one hash value for a group of data elements of the second set of data elements.

19. The method of claim 12, further comprising:

determining a number of distinct hash values included in the multiple hash values or determining a count of collisions of the multiple hash values; and

accessing a lookup table that includes multiple estimated compression ratios, wherein the estimated compression ratio is determined from the multiple estimated compression ratios of the lookup table based on the number of distinct hash values or the count of collisions of the multiple hash values.

20. The method of claim 12, wherein the estimated compression ratio is determined without generating a hash value for the second set of data elements.