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

• US 6,961,009 B2
• Filed: 10/18/2004
• Issued: 11/01/2005
• Est. Priority Date: 10/30/2002
• Status: Expired due to Term

• Current Assignee: Riverbed Technology, LLC (Riverbed Technology Incorporated)
• Original Assignee: NBT Technology, Inc.
• Inventors: McCanne, Steven, Demmer, Michael J.
• Primary Examiner(s): JeanPierre, Peguy
• Assistant Examiner(s): LAUTURE, JOSEPH J
• Application Number:
  US10/968,868
• Publication Number:
  US 20050162288A1
• Time in Patent Office: 379 Days
• Field of Search: 341/51, 341/50, 341/65, 370/253, 370/392, 370/386, 382/178, 386/83
• US Class Current: 341/51
• 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. An apparatus configured to process input data, wherein the input data is segmented into a plurality of segments, the apparatus comprising:

logic configured to determine one or more segments in the plurality of segments that are to be referenced segments;

for each of the one or more referenced segments, logic configured to replace data for the referenced segments with a reference label;

for each referenced segment not already present in a persistent segment store, logic configured to store a reference binding in the persistent segment store, wherein a reference binding associates a referenced segment'"'"'s data and its reference label;

logic configured to determine whether any sequence of segments is to be grouped as a reference group;

for each reference group, logic configured to replace a reference label or data for segments in the sequence with a group label; and

for each reference group not already present in the persistent segment store, logic configured to store a group reference binding in the persistent segment store, wherein a group reference binding associates a reference group'"'"'s reference labels or data with its group label.

2. The apparatus of claim 1, further comprising:

logic configured to determine whether any sequence of segments is to be grouped as a higher level reference group;

for each higher level reference group, logic configured to replace a group label, a reference label or data for segments in the sequence with a higher level group label; and

for each higher level reference group not already present in the persistent segment store, logic configured to store a higher level group reference binding in the persistent segment store, wherein a higher level group reference binding associates a higher level reference group'"'"'s group labels, reference labels or data with its higher level group label.

3. The apparatus of claim 1, further comprising:

logic to determine a set of cut points for the input data based on a fingerprint function, the fingerprint function indicating a cut point based on a number of symbols input into the fingerprint function; and

logic to segment the input data based on the set of cut points.

4. The apparatus of claim 3, wherein the logic configured to determine the set of cut points comprises:

logic to determine a fingerprint window comprising a sequence of input symbols, wherein the fingerprint window is associated with an offset;

logic to input the sequence of input symbols into the fingerprint function, the fingerprint function outputting a fingerprint value; and

logic to determine from the fingerprint value if a cut point should be determined at the offset.

5. The apparatus of claim 4, further comprising logic to repeat the advancing, inputting, and determining steps until a cut point is determined.

6. The apparatus of claim 3, wherein the logic to determine the set of cut points comprises:

if it is not determined from the fingerprint value that a cut point should be determined at a new offset, logic to advance the fingerprint window to comprise a new sequence of input symbols, wherein the fingerprint window is associated with the offset;

logic to input the new sequence of input symbols into the fingerprint function, the fingerprint function outputting a new fingerprint value; and

logic to determine from the new fingerprint value if a cut point should be determined at the new offset.

7. The apparatus of claim 1, wherein the logic to determine whether any sequence of segments is to be grouped as a reference group comprises:

logic to input the group of references into the fingerprint function, the fingerprint function outputting a fingerprint value; and

logic to determine from the fingerprint value if the group of references should be grouped as a reference group.

8. The apparatus of claim 7, further comprising:

if it is not determined from the fingerprint value that the group of references should be grouped as the reference group, logic to advance the fingerprint window to comprise a new group of reference labels;

logic to input the new group of reference labels into the fingerprint function, the fingerprint function outputting a new fingerprint value; and

logic to determine from the new fingerprint value if the new group of reference labels should be a grouped as a reference group.

9. The apparatus of claim 8, further comprising logic to repeat the advancing, inputting, and determining steps until the reference group is determined.

10. An apparatus configured to process input data, the apparatus comprising:

logic configured to determine a first set of segments for the input data based on a first fingerprint function;

logic configured to replace segments in the first set of segments for the input data with reference labels if it is determined they are referenced segments;

for each referenced segment not already present in a persistent segment store, logic configured to store a reference binding in the persistent segment store, wherein a reference binding associates a referenced segment'"'"'s data and its reference label;

logic configured to determine a second set of segments for the segmented input data based on a second fingerprint function;

logic configured to replace segments in the second set of segments for the input data with group labels if it is determined they are referenced groups; and

for each reference group not already present in the persistent segment store, logic configured to store a group reference binding in the persistent segment store, wherein a group reference binding associates a reference group'"'"'s references with its group label.

11. The apparatus of claim 10, wherein the first fingerprint function and the second fingerprint function are identical functions.

12. The apparatus of claim 10, wherein after segments in the first set of segments for the input data are replaced with reference labels, the input data includes reference labels or data.

13. The apparatus of claim 10, wherein after segments in the second set of segments for the input data are replaced with group labels, the input data includes group labels, reference labels, or data.

14. A method for processing input data, the method comprising:

(a) identifying sequences of segments in the input data, wherein sequences of segments are determined as groups to be referenced;

(b) for each group, replacing the group with a label in the input data; and

(c) for each group not already present in a persistent segment store, storing a reference binding in the persistent segment store for the group; and

(d) recursively performing steps (a–

c) with the replaced groups in the input data a number of times equal to a number of desired levels of reference bindings, wherein at least two levels of reference bindings are stored in the persistent segment store.

15. The method of claim 14, wherein the first level of reference bindings comprises bindings between reference labels and data in the input data.

16. The method of claim 15, wherein the second level of reference bindings comprises bindings between group labels and reference labels.

17. The method of claim 14, wherein identifying sequences of segments in the input data comprises identifying sequences of segments using a fingerprint function.