Method of producing a checkpoint which describes a box file and a method of generating a difference file defining differences between an updated file and a base file

• US 6,513,050 B1
• Filed: 02/10/1999
• Issued: 01/28/2003
• Est. Priority Date: 08/17/1998
• Status: Expired due to Fees

• Current Assignee: Connected Place Limited
• Original Assignee: Connected Place Limited
• Inventors: Williams, Dominic C. C., Korn, Christian M.
• Primary Examiner(s): Alam, Hosain T.
• Application Number:
  US09/247,511
• Time in Patent Office: 1,448 Days
• Field of Search: 707/530, 707/511, 707/101, 707/201, 707/100, 707/202-204, 714/12, 709/248
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A checkpoint which describes a base file is produced by dividing the base file into a series of segments; generating for each segment a segment description; and creating from the generated segment descriptions a segment description structure as the checkpoint. The segment descriptions represent segments of the base file at a minimum level of resolution sufficient to represent distinctly the segment. A difference file which defines differences between an updated file and the base file is produced by generating at different levels of resolution segment descriptions for segments in the updated file and comparing the generated segment descriptions with segment descriptions in the checkpoint to identify matching and non-matching segments. Data identifying segments in the updated file that match segments in the base file and data representing portions of the updated file at a minimum level of resolution sufficient to represent distinctly the portion are stored as the difference file.

Claims

1. A method of producing a checkpoint which describes a base file, the method comprising:

dividing the base file into a series of segments;

generating for each segment a segment description, wherein each segment description comprises a lossless signature and a plurality of lossey samples each describing the segment at a different level of resolution; and

creating from the generated segment descriptions a segments description structure as the checkpoint,

wherein the segments description structure is created by selecting for each segment from among the plural lossey samples and lossless signature a description that adequately distinguishes the segment to the lowest level of resolution.

2. A method as claimed in claim 1, wherein all segments are of equal, predetermined length.

3. A method as claimed in claim 1, wherein the plurality of lossey samples comprises a first lossey sample containing data selected from the segment at a first level of resolution and a second lossey sample containing data selected from the segment at a second, lower level of resolution, and the data selected for the second lossey sample is a subset of the data selected for the first lossey sample.

4. A method as claimed in claim 1, wherein each segment description comprises a segment index defining the position of the segment in the series.

5. A method as claimed in claim 1, wherein the description is selected for each segment by comparing the plural lossey samples and the signature with respective plural lossey samples and signatures of other segments earlier in the sequence starting with the lossey samples at the lower level of resolution.

6. A method as claimed in claim 1, wherein the segments description structure comprises binary tree structures created by comparing a characteristic of a segment description of one segment with the characteristic of a segment description of another, previously entered segment, and determining whether the characteristic is greater than, less than, or equal to the characteristic of the other segment.

7. A method as claimed in claim 6, wherein the segment description of the one segment is entered into a binary tree at the same level of resolution as the segment description of the other segment if the characteristic of the one segment is less than or greater than the characteristic of the other segment, and the segment description of the one segment is entered into a binary tree at a higher level of resolution than the segment description of the other segment if the characteristic of the one segment is equal to the characteristic of the other segment.

8. A method as claimed in claim 1, wherein the segments description structure is created by entering the lossless signature of a segment only if none of the plural lossey samples adequately distinguish the segment.

9. A method as claimed in claim 1, wherein, once a segment description has been placed in the segments description structure, redundant data is removed from the segment description in order to reduce the amount of data in the segments description structure.

10. A method as claimed in claim 9 wherein the redundant data comprises lossey samples at a resolution greater than that at which the segment description is entered into a binary tree.

11. A method as claimed in claim 9 wherein the redundant data comprises information derivable from lossey samples entered into binary trees at resolutions lower than that at which the segment description is entered into a binary tree.

12. A method of producing a morph list that defines an updated version of a base file with reference to the base file and a checkpoint for the base file, the method comprising:

producing the checkpoint by

dividing the base file into a series of segments,

generating for each segment a segment description, wherein each segment description comprises a lossless signature and a plurality of lossey samples each describing the segment at a different level of resolution, and

creating from the generated segment descriptions a segments description structure as the checkpoint,

wherein the segments description structure is created by selecting for each segment from among the plural lossey samples and lossless signature a description that adequately distinguishes the segment to the lowest level of resolution;

defining a first segment at a start position in the updated file;

generating a segment description for the first segment;

comparing the segment description for the first segment with segment descriptions of the checkpoint; and

if a match is found, adding the matched segment description to the morph list and, if no match is found adding data in the first segment to the morph list.

13. A method as claimed in claim 12 further comprising defining a second segment, and wherein the second segment is defined at a position adjacent to the first segment if a match is found and the second segment is defined at a position overlapping but not including the data added to the morph list if no match is found.

14. A method as claimed in claim 12 wherein the data in the first segment added to the morph list comprises a first byte in the segment.

15. A method as claimed in claim 12 wherein the segment description for the first segment is compared with segment descriptions of the checkpoint by comparing samples of the first segment with samples in the checkpoint starting with the lossey samples at the lower level of resolution.

16. A method as claimed in claim 15, wherein, when a match is found, samples are compared at increasing levels of resolution to identify matching samples until no further match is found, and then the matching samples are compared with the lossless signature.

17. A method of generating a difference file defining differences between an updated file and a base file, the method comprising:

generating a checkpoint by

dividing the base file into a series of segments,

generating for each segment a segment description, wherein each segment description comprises a lossless signature and a plurality of lossey samples each describing the segment at a different level of resolution, and

creating from the generated segment descriptions a segments description structure as the checkpoint,

wherein the segments description structure is created by selecting for each segment from among the plural lossey samples and lossless signature a description that adequately distinguishes the segment to the lowest level of resolution;

generating at different levels of resolution segment descriptions for segments in the updated file and comparing the generated segment descriptions with segment descriptions in the checkpoint to identify matching and non-matching segments; and

storing as the difference file data identifying segments in the updated file that match segments in the base file and data representing portions of the updated file at a minimum level of resolution sufficient to represent distinctly the portion.