Content-based segmentation scheme for data compression in storage and transmission including hierarchical segment representation

• US 7,852,237 B2
• Filed: 12/08/2008
• Issued: 12/14/2010
• Est. Priority Date: 10/30/2002
• Status: Expired due to Term

• Current Assignee: Riverbed Technology, LLC (Riverbed Technology Incorporated)
• Original Assignee: Riverbed Technology Incorporated
• Inventors: McCanne, Steven, Demmer, Michael J.
• Primary Examiner(s): Nguyen; Linh V
• Application Number:
  US12/330,197
• Publication Number:
  US 20090079597A1
• Time in Patent Office: 736 Days
• Field of Search: 341 50-107, 707/100, 707/102, 707/200, 707/203
• US Class Current: 341/50
• 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: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

In a coding system, input data within a system is encoded. The input data might include sequences of symbols that repeat in the input data or occur in other input data encoded in the system. The encoding includes determining a target segment size, determining a window size, identifying a fingerprint within a window of symbols at an offset in the input data, determining whether the offset is to be designated as a cut point and segmenting the input data as indicated by the set of cut points. For each segment so identified, the encoder determines whether the segment is to be a referenced segment or an unreferenced segment, replacing the segment data of each referenced segment with a reference label and storing a reference binding in a persistent segment store for each referenced segment, if needed. Hierarchically, the process can be repeated by grouping references into groups, replacing the grouped references with a group label, storing a binding between the grouped references and group label, if one is not already present, and repeating the process. The number of levels of hierarchy can be fixed in advanced or it can be determined from the content encoded.

Claims

1. A method comprising:

compressing a data stream by;

segmenting at least portions of the data stream into segments based on content of the data stream;

responsive to a respective segment being a recurring segment, replacing the segment with a corresponding reference; and

responsive to a respective segment not being a recurring segment, creating a reference for the segment and replacing the segment with the created reference; and

storing the compressed data in a storage system.

2. The method of claim 1, wherein the size of the segments is not fixed.

3. The method of claim 1, wherein segmenting the data stream comprises generating a fingerprint of a group of data symbols.

4. The method of claim 3, wherein segmenting the data stream comprises determining a segmentation boundary based on a respective fingerprint.

5. The method of claim 3, wherein generating the fingerprint comprises generating a hash based on the group of data symbols.

6. The method of claim 1, wherein compressing the data stream further comprises compressing the references hierarchically.

7. The method of claim 6, wherein compressing the references hierarchically comprises assigning a hash to a sequence of hashes.

8. The method of claim 6, wherein compressing the references hierarchically comprises:

segmenting a stream of references into groups;

responsive to a respective group being a recurring group, replacing the group with a corresponding reference; and

responsive to a respective group not being a recurring group, creating a reference for the group and replacing the group with the created reference.

9. The method of claim 6, wherein the compressed data stream includes references associated with different hierarchy levels.

10. The method of claim 1, further comprising storing segment-to-reference binding information in a persistent storage.

11. The method of claim 1, further comprising allowing an average segment size to be set.

12. A system, comprising:

a segmentation mechanism configured to segment at least portions of a data stream into segments based on content of the data stream;

a replacement mechanism configured to replace a respective segment with a corresponding reference in response to the segment being a recurring segment; and

a binding mechanism configured to create a reference for a respective segment and replacing the segment with the created reference in response to the segment not being a recurring segment, thereby compressing the data stream.

13. The system of claim 12, wherein the size of the segments is not fixed.

14. The system of claim 12, wherein the segmentation mechanism comprises a fingerprinting mechanism configured to generate a fingerprint of a group of data symbols.

15. The system of claim 14, wherein the segmentation mechanism is configured to determine a segmentation boundary based on a respective fingerprint.

16. The system of claim 14, wherein while generating the fingerprint, the fingerprinting mechanism is configured to generate a hash based on the group of data symbols.

17. The system of claim 12, further comprising a mechanism to hierarchically assign references to sequences of references.

18. The system of claim 17, wherein the references comprise hashes.

19. The system of claim 12,

wherein the segmentation mechanism is further configured to segment a stream of references into groups;

wherein the replacement mechanism is further configured to replacing a respective group with a corresponding reference responsive to the group being a recurring group; and

wherein the binding mechanism is further configured to create a reference for a respective group and replacing the group with the created reference responsive to the group not being a recurring group.

20. The system of claim 17, wherein the compressed data stream includes references associated with different hierarchy levels.

21. The system of claim 12, wherein the binding mechanism is further configured to store segment-to-reference binding information in a persistent storage.

22. The system of claim 12, wherein the segmentation mechanism is further configured to allow an average segment size to be set.

23. A method comprising:

receiving a file or a portion of a file;

compressing the file or portion thereof by;

at least partially segmenting the file or portion thereof into segments based on content of the file;

responsive to a respective segment being a recurring segment, replacing the segment with a corresponding reference;

responsive to a respective segment not being a recurring segment, creating a reference for the segment and replacing the segment with the created reference; and

saving the file or portion thereof to a storage system.

24. A method comprising:

compressing a file by;

segmenting at least portions of the file into segments based on content of the file;

responsive to a respective segment being a recurring segment, replacing the segment with a corresponding reference; and

responsive to a respective segment not being a recurring segment, creating a reference for the segment and replacing the segment with the created reference; and

storing the compressed file in a storage system.

25. The method of claim 24, wherein the size of the segments is not fixed.

26. The method of claim 24, wherein segmenting the file comprises generating a fingerprint of a group of data symbols.

27. The method of claim 26, wherein segmenting the file comprises determining a segmentation boundary based on a respective fingerprint.

28. The method of claim 26, wherein generating the fingerprint comprises generating a hash based on the group of data symbols.

29. The method of claim 24, wherein compressing the file further comprises compressing the references hierarchically.

30. The method of claim 29, wherein compressing the references hierarchically comprises assigning a hash to a sequence of hashes.

31. The method of claim 29, wherein compressing the references hierarchically comprises:

segmenting a stream of references into groups;

responsive to a respective group being a recurring group, replacing the group with a corresponding reference; and

responsive to a respective group not being a recurring group, creating a reference for the group and replacing the group with the created reference.

32. The method of claim 29, wherein the compressed file includes references associated with different hierarchy levels.

33. The method of claim 24, further comprising storing segment-to-reference binding information in a persistent storage.

34. The method of claim 24, further comprising allowing an average segment size to be set.