Method of and an apparatus for merging a sequence of delta files

• US 6,542,906 B2
• Filed: 08/17/1999
• Issued: 04/01/2003
• Est. Priority Date: 08/17/1998
• Status: Expired due to Fees

• Current Assignee: Connected Place Limited
• Original Assignee: Connected Place Limited
• Inventors: Korn, Christian M.
• Primary Examiner(s): Breene, John
• Assistant Examiner(s): Ali, Mohammad
• Application Number:
  US09/375,375
• Publication Number:
  US 20020169740A1
• Time in Patent Office: 1,323 Days
• Field of Search: 707/201-204, 707/1-8, 707/103.R, 707/103
• US Class Current: 707/641
• CPC Class Codes: G06F 16/1756 based on delta files
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

A method of and an apparatus for merging a sequence of delta files is described. The delta files together define a series of changes between a base file and an updated file, each delta file defining one or more changes in terms of one or more unique tokens each identifying original data or of one or more reused tokens identifying data reused from the immediately preceding delta file or the base file. The method comprises creating an initial merge structure from the base file and the first delta file in the sequence. A further merge structure is created from the initial merge structure and the next delta file in the sequence by comparing tokens in the initial merge structures and replacing reused tokens in the further merge structure with tokens in the initial merge structure. The initial merge structure is then replaced with the further merge structure so that the further merge structure becomes the initial merge structure. The operations of creating a further merge structure and replacing the initial merge structure with a further merge structure is repeated for all delta files in sequence order. The thus created merge structure represents all changes between the base file and the updated file. The apparatus, which may comprise a suitably configured computer, comprises means suitable for carrying out the method steps.

Claims

1. A method of merging a sequence of delta files that together define a series of changes between a base file and an updated file, each delta file defining one or more changes in terms of one or more unique tokens each identifying original data or of one or more reuse tokens identifying data reused from the immediately preceding delta file or the base file, the method comprising:

creating an initial merge structure from the base file and the first delta file in the sequence;

creating a further merge structure from the initial merge structure and the next delta file in the sequence by comparing tokens in the initial and further merge structures and replacing reuse tokens in the further merge structure with tokens in the initial merge structure;

replacing the initial merge structure with the further merge structure so that the further merge structure becomes the initial merge structure; and

repeating the operations of creating a further merge structure and replacing the initial merge structure with the further merge structure, for all delta files in sequence order, whereby the thus created merge structure represents all changes between the base file and the updated file;

identifying a file position corresponding.

2. A method as claimed in claim 1, wherein the base file is itself a delta file which defines one or more changes to a preceding delta file or base file.

3. A method as claimed in claim 1, wherein the base file is an initial data file and the thus created merge structure represents all changes in terms of unique tokens, whereby an updated data file can be created from the initial data file and the thus created merge structure.

4. A method as claimed in claim 1, wherein each reuse token comprises a reuse token indicator, an offset value identifying the position of bytes in another delta file or the base file and a number value representing the number of bytes associated with the position identified by the offset value.

5. A method as claimed in claim 1, wherein each unique token comprises a unique token indicator, a file identifier for identifying the file containing unique data for the thus created merge structure, an offset value identifying the position of bytes in another delta file or the base file and a number value representing the number of bytes associated with the position identified by the offset value.

6. A method as claimed in claim 1, further comprising:

defining for each token in the further merge structure a window of locations in the initial merge structure from data associated with the token in the further merge structure;

identifying for each window in the initial merge structure the or each token in the further merge structure that refers to data in the window; and

replacing thus identified tokens in the further merge structure with data derived from tokens in the window of the initial merge structure.

7. A method as claimed in claim 1, further comprising:

identifying reuse tokens in a merge structure;

appending in the merge structure the unique token or tokens to which the reuse token pertains; and

replacing the reuse token with an offset token which comprises a pointer that identifies the position at which the unique token or tokens are appended in the merge structure.

8. A method as claimed in claim 7, wherein the unique token or tokens are appended at the end of the merge structure.

9. A method as claimed in claim 1, further comprising:

for each delta file identifying reuse tokens therein; and

for each identified reuse token modifying the token, tokens or token portions in the preceding delta file to which the reuse token pertains by replacing the same with a forward reuse token which identifies the reuse token in the delta file, thereby to create bi-directional delta files.

10. A method as claimed in claim 9, further comprising, when an identified reuse token in the delta file pertains to a portion of one or more tokens in the preceding delta file, modifying the remaining portion of the one or more tokens to which the reuse token does not pertain.

11. A method as claimed in claim 1, further comprising reviewing tokens in the created merge structure to identify as redundant those delta files to which no reference is made.

12. A method as claimed in claim 11, further comprising deleting redundant delta files.

13. A method as claimed in claim 1, further comprising saving the created merge structure.

14. A method as claimed in claim 1, further comprising using the created merge structure to create the updated file from the base file.

15. A method of creating a current file from an initial file and a set of difference files that defines a sequence of changes between the initial file and the current file, the method comprising:

merging the difference files according to the method as claimed in claim 1 so as to remove redundant information therefrom and thus create a changes file representing all changes to be applied to the initial file in order to arrive at the current file; and

modifying the initial file using the information in the changes file.

16. A method as claimed in claim 15, wherein each difference file comprises one or more sets of information each defining changes in a block of data at a position in an earlier difference file or in the initial file, and the initial file is modified by effecting the changes defined by the sets of information.

17. A method as claimed in claim 16, wherein one or more of the sets of information includes information which identifies the location of data for the current file from a specified difference file or the initial file.

18. An apparatus for merging a sequence of delta files that together define a series of changes between a base file and an updated file, each delta file defining one or more changes in terms of one or more unique tokens each identifying original data or of one or more reuse tokens identifying data reused from the immediately preceding delta file or the base file, the apparatus comprising:

means for creating an initial merge structure from the base file and the first delta file in the sequence;

means for creating a further merge structure from the initial merge structure and the next delta file in the sequence by comparing tokens in the initial and further merge structures and replacing reuse tokens in the further merge structure with tokens in the initial merge structure;

means for replacing the initial merge structure with the further merge structure so that the further merge structure becomes the initial merge structure; and

means for repeating the operations of creating a further merge structure and replacing the initial merge structure with the further merge structure, for all delta files in sequence order, whereby the thus created merge structure represents all changes between the base file and the updated file;

means for identifying a file position corresponding.

19. An apparatus as claimed in claim 18, further comprising:

means for defining for each token in the further merge structure a window of locations in the initial merge structure from data associated with the token in the further merge structure;

means for identifying for each window in the initial merge structure the or each token in the further merge structure that refers to data in the window; and

means for replacing thus identified tokens in the further merge structure with data derived from tokens in the window of the initial merge structure.

20. An apparatus as claimed in claim 18, further comprising:

means for identifying reuse tokens in a merge structure;

means for appending in the merge structure the unique token or tokens to which the reuse token pertains; and

means for replacing the reuse token with an offset token which comprises a pointer that identifies the position at which the unique token or tokens are appended in the merge structure.

21. An apparatus as claimed in claim 20, wherein the means for appending is arranged to append the unique token or tokens at the end of the merge structure.

22. An apparatus as claimed in claim 18, further comprising:

means for identifying, for each delta file, reuse tokens therein; and

means for modifying for each identified reuse token, the token, tokens or token portions in the preceding delta file to which the reuse token pertains by replacing the same with a forward reuse token which identifies the reuse token in the delta file, thereby to create bi-directional delta files.

23. An apparatus as claimed in claim 22, further comprising means for modifying, when an identified reuse token in the delta file pertains to a portion of one or more tokens in the preceding delta file, the remaining portion of the one or more tokens to which the reuse token does not pertain.

24. An apparatus as claimed in claim 18, further comprising means for reviewing tokens in the created merge structure to identify as redundant those delta files to which no reference is made.

25. An apparatus as claimed in claim 24, further comprising means for deleting redundant delta files.

26. An apparatus as claimed in claim 18, further comprising means for saving the created merge structure.

27. An apparatus as claimed in any of claim 18, further comprising means for using the created merge structure to create the updated file from the base file.

28. An apparatus for creating a current file from an initial file and set of difference files that defines a sequence of changes between the initial file and the current file, the apparatus comprising:

apparatus according to claim 18 for merging the difference files to remove redundant information therefrom and thus create a changes file representing all changes to be applied to the initial file in order to arrive at the current file; and

means for modifying the initial file using the information in the changes file.

29. An apparatus as claimed in claim 28, wherein each difference file comprises one or more sets of information each defining changes in a block of data at a position in an earlier difference file or in the initial file, and the means for modifying the initial file is arranged to effect the changes defined by the sets of information.