Data compression using partial statistics

• US 10,303,402 B2
• Filed: 08/02/2016
• Issued: 05/28/2019
• Est. Priority Date: 08/02/2016
• Status: Active Grant

• Current Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Original Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Inventors: Xie, Hongmei, Chen, Zhengang, Eskandari-Gharnin, Bijan, Haratsch, Erich F.
• Primary Examiner(s): Li, Aimee
• Assistant Examiner(s): Kwong, Edmund H
• Application Number:
  US15/226,182
• Publication Number:
  US 20180039426A1
• Time in Patent Office: 1,029 Days
• Field of Search: None
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/1036 Life time enhancement
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0658 Controller construction arrangements
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: G06F 3/0674 Disk device
• 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/3079 Context modeling
• CPC Class Codes: H03M 7/607 Selection between different types of compressors
• CPC Class Codes: H03M 7/6088 according to the data type

Abstract

A data storage device includes at least one data storage medium and a controller that is operably coupled to the at least one data storage medium. The controller receives the bit stream in a data storage device and performs a first level of compression on the received bit stream to obtain a symbol frame including a plurality of symbols. The controller encodes an initial portion of the plurality of symbols contained in the symbol frame by a fixed encoding scheme. The controller also collects statistics for the initial portion of the symbol frame. The controller then selects at least one data compression algorithm based on the collected statistics. The controller then performs compression encoding on a remaining portion of the symbol frame with the selected at least one data compression algorithm.

Claims

1. A method comprising:

receiving a bit stream in a data storage device;

performing, by a processor of the data storage device, a first level of compression on the received bit stream to obtain a symbol frame comprising a plurality of symbols;

storing less than all of the plurality of symbols in a buffer memory having a pre-defined size to provide a subset of the plurality of symbols of the symbol frame, the subset of the plurality of symbols are for utilization in obtaining partial statistics;

obtaining, by the processor, the partial statistics based on the subset of the plurality of symbols;

selecting, by the processor, at least one data compression algorithm based on the obtained partial statistics, the at least one compression algorithm being applicable to different symbols of the plurality of symbols of the symbol frame that are not a part of the subset of the plurality of symbols; and

performing, by the processor, a second level of compression on all of the plurality of symbols of the symbol frame with the selected at least one data compression algorithm.

2. The method of claim 1 and wherein the plurality of symbols comprises different types of symbols.

3. The method of claim 2 and wherein obtaining the statistics for the symbols stored in the buffer memory comprises obtaining frequencies of symbols for each of the different types of symbols.

4. The method of claim 3 and wherein the different types of symbols comprise literals, lengths and offsets.

5. The method of claim 3 and wherein selecting the at least one data compression algorithm based on the obtained statistics comprises selecting the at least one data compression algorithm based on the obtained frequencies of the symbols for each of the different types of symbols.

6. The method of claim 5 and wherein performing the second level of compression on all of the plurality of symbols with the selected at least one data compression algorithm comprises performing the second level of data compression on the different types of symbols with corresponding different types of data compression algorithms.

7. The method of claim 1 and further comprising encoding at least some of the plurality of symbols by a fixed encoding scheme based on assumed statistics that are different from the statistics for the symbols stored in the buffer memory.

8. The method of claim 1 and wherein the pre-defined size of the buffer memory is less than a size of the symbol frame.

9. A method comprising:

providing, in a data storage device, a data frame having a predetermined size, wherein the data frame comprises original data bits received in the data storage device or symbols produced by performing, by a processor of the data storage device, a first level of compression on the original data bits;

encoding, by the processor of the data storage device, an initial portion of the original data bits or the symbols contained in the data frame by a fixed encoding scheme employing assumed fixed statistics;

during the encoding by the fixed encoding scheme, collecting, by the processor, statistics for the initial portion of the original data bits or the symbols;

selecting, by the processor, at least one data compression algorithm based on the collected statistics; and

performing, by the processor, compression encoding on a remaining portion of the original data bits or the symbols with the selected at least one data compression algorithm.

10. The method of claim 9 and wherein performing the compression encoding on the remaining portion of the original data bits or the symbols comprises dynamically encoding the remaining portion of the original data bits or the symbols without a wait period between completion of the encoding of the initial portion of the data bits or the symbols and commencement of the compression encoding on the remaining portion of the original data bits or the symbols.

11. The method of claim 9 and wherein the data frame comprises different types of symbols.

12. The method of claim 11 and wherein the different types of symbols comprise literals, lengths, offsets and flags.

13. The method of claim 12 and wherein the at least one data compression algorithm comprises a first data compression algorithm for literals, a second data compression algorithm for lengths and a third data compression algorithm for offsets.

14. A data storage device comprising:

at least one data storage medium; and

a controller operably coupled to the at least one data storage medium, the controller configured to;

receive a bit stream in the data storage device;

perform a first level of compression on the received bit stream to obtain a symbol frame comprising a plurality of symbols;

encode an initial portion of the plurality of symbols contained in the symbol frame by a fixed encoding scheme employing assumed fixed statistics;

collect statistics for the initial portion of the symbol frame;

select at least one data compression algorithm based on the collected statistics; and

perform compression encoding on a remaining portion of the symbol frame with the selected at least one data compression algorithm.

15. The data storage device of claim 14 and wherein the controller is further configured to collect the statistics for the initial portion of the data stream during the encoding by the fixed encoding scheme.

16. The data storage device of claim 14 and wherein the at least one data storage medium comprises a solid state memory.

17. The data storage device of claim 14 and wherein the controller is configured to perform the compression encoding on the remaining portion of the symbol frame by dynamically encoding the remaining portion of the symbol frame without employing a wait period between completion of the encoding of the initial portion of the symbol frame and commencement of the compression encoding on the remaining portion of the original data bits or the symbols.

18. The data storage device of claim 17 and wherein the symbol frame comprises different types of symbols.

19. The data storage device of claim 18 and wherein the different types of symbols comprise literals, lengths and offsets.

20. The data storage device of claim 19 and wherein the at least one data compression algorithm comprises a first data compression algorithm for literals, a second data compression algorithm for lengths and a third data compression algorithm for offsets.