Granted Patent B1

US 9,405,479 · App. 14/154,974 · Granted Aug 2, 2016

Abstract

Claims (41)

1. A method, comprising:

reading a portion of a predetermined amount of data bounded by a sliding compression window;

identifying a respective first location, within the portion of the predetermined amount of data, of a first occurrence of each respective one of a plurality of data values;

identifying respective second and subsequent locations, within the portion of the predetermined amount of data, of each second and subsequent occurrence of each respective one of the plurality of values;

determining separate instances of repeated sequences of values from the identified locations;

compressing, using the identified respective first, second and subsequent locations, at least one of the determined separate instances of repeated sequences of values identified; and

moving the sliding compression window to a next adjacent portion within the predetermined amount of data and returning to reading.

2. The method of claim 1 , wherein compressing comprises compressing each of the determined separate instances of repeated sequences of values.

3. The method of claim 1 , wherein compressing comprises replacing each repeated sequence of values with at least a reference to a previous instance of the repeated sequence and a length of the previous repeated sequence.

4. The method of claim 3 , wherein the reference comprises a pointer to the previous instance of the repeated sequence.

5. The method of claim 1 , further comprising, prior to compressing:

determining whether a length of the at least one of the determined separate instances of repeated sequences of values is greater than a threshold length; and

compressing only when the length is greater than the threshold length.

6. The method of claim 1 , wherein identifying the first location comprises populating a starting location table with each identified occurrence of the data value and wherein identifying the second and subsequent locations comprises populating a reference table with a chain of references of each of the identified occurrences of the data values of the read portion of the predetermined amount of data.

7. The method of claim 6 , further comprising continuing reading different portions of the predetermined amount of data, populating the starting location table and the reference table, determining and compressing for all of the predetermined amount of data.

8. The method of claim 6 , wherein the chain of references comprises a linked list of references.

9. The method of claim 1 , wherein compressing is lossless.

10. A device, comprising:

a memory; and

a processor coupled to the memory, the processor being configured to control storage and retrieval of data from a data storage device, the processor being further configured to:

read a portion of a predetermined amount of data bounded by a sliding compression window;

identify a respective first location, within the portion of the predetermined amount of data, of a first occurrence of each respective one of a plurality of data values;

identify respective second and subsequent locations, within the portion of the predetermined amount of data, of each second and subsequent occurrence of each respective one of the plurality of values;

determine separate instances of repeated sequences of values from the identified locations;

compress, using the identified respective first, second and subsequent locations, at least one of the determined separate instances of repeated sequences of values; and

move the sliding compression window to a next adjacent portion within the predetermined amount of data.

11. The device of claim 10 , wherein the processor is further configured to compress each of the determined separate instances of repeated sequences of values.

12. The device of claim 10 , wherein the processor is further configured to compress by replacing each repeated sequence of values with at least a reference to a previous instance of the repeated sequence and a length of the previous repeated sequence.

13. The device of claim 12 , wherein the reference comprises a pointer to the previous instance of the repeated sequence.

14. The device of claim 10 , wherein the processor is further configured to, prior to compressing:

determine whether a length of the at least one of the determined separate instances of repeated sequences of values is greater than a threshold length; and

compress only when the length is greater than the threshold length.

15. The device of claim 10 , wherein the processor is further configured to:

populate a starting location table with each identified occurrence of the data value; and

populate a reference table with a chain of references of each of the identified occurrences of the data values of the read portion of the predetermined amount of data.

16. The device of claim 15 , wherein the processor is further configured to continue reading different portions of the predetermined amount of data, populating the starting location table and the reference table, determining and compressing for all of the predetermined amount of data.

17. The device of claim 15 , wherein the chain of references comprises a linked list of references.

18. The device of claim 10 , wherein the processor is further configured to compress in a lossless manner.

19. The device of claim 10 , wherein the device comprises a Network Attached Storage (NAS).

20. The device of claim 10 , wherein the device comprises a Redundant Array of Independent Disks (RAID).

21. The device of claim 10 , wherein the device comprises a disk drive.

Assignments (8)