Differential data forming method, program, recording medium, and apparatus

• US 7,908,250 B2
• Filed: 10/07/2002
• Issued: 03/15/2011
• Est. Priority Date: 02/28/2002
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Terazono, Kohei, Okada, Yoshiyuki
• Primary Examiner(s): Lee; Wilson
• Assistant Examiner(s): Le; Michael
• Application Number:
  US10/265,317
• Publication Number:
  US 20030163496A1
• Time in Patent Office: 3,081 Days
• Field of Search: 707/204, 707/6, 707/101, 707/201, 707/203, 707/661, 707/674, 717/122, 717/168, 715/511, 714/8
• US Class Current: 707/661
• CPC Class Codes: G06F 11/1458 Management of the backup or restore process
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems

Abstract

One new file and one old file are sequentially compared from the heads of the files on a predetermined data unit basis. If a data match is found, transfer information showing a position and a data length of the old file is output. If a data mismatch is found by the sequential comparison, the old file is searched in both directions from the data position where the mismatch had been found in the old file, thereby finding a portion which matches with the data of the new file. If the matching portion can be found, shift information up to the matching portion on the old file is output. If the matching portion cannot be found, new data is added to transfer replacement information showing a length of data of the mismatching portion of the old file at a position until the matching portion can be found, and the resultant transfer replacement information is output.

Claims

1. A method for forming a differential data, with steps performed by a data processor, comprising:

comparing a new file and an old file sequentially from head of the new file and head of the old file on a predetermined data unit basis;

when said sequential comparison results in determination of a match between the new data and the old data, outputting transfer information showing a position and a data length of the matching data in the old file; and

when said sequential comparison results in determination of a mismatching between the new data and the old data, searching for a portion matching with the new data in both forward and backward directions from a position of the mismatch in the old file;

if the matching portion can be found, outputting shift information from the mismatch portion up to the matching portion in the old file; and

if the matching portion cannot be found,

when a first difference value of the mismatching portion does not match with a second difference value previously stored, outputting the transfer replacement information showing a length of the mismatching portion and the new data and storing the first difference value; and

when the first difference value matches with the second difference value previously stored, outputting transfer increase information showing the first difference value is the same as the second difference value.

2. The method according to claim 1, wherein in said searching for a matching portion, when the matching portion and continuous matching portions of a predetermined number (n) or more of data subsequent to said matching portion are found in the old file, it is determined that the data matches.

3. The method according to claim 1, wherein in said searching for a matching portion, when the matching portion and matching portions of a predetermined number (y) or more of data distributed among a predetermined number (x) of data subsequent to said matching portion are found in the old file, it is determined that the data matches.

4. The method according to claim 1, wherein in said outputting shift information, a shifting direction in which a forward position in said old file is set to a negative direction and a backward position in said old file is set to a positive direction and a shift length showing a length of data up to the matching portion in the old file is output as said shift information.

5. The method according to claim 1, wherein in said searching for a matching portion, if a structure of the old file and the new file is that of a program file written by an n-bit code, the searching is performed every other (n) bits in both forward and backward directions from the position determined to be mismatching in the old file.

6. The method according to claim 1, wherein in said outputting transfer replacement information, if the matching portion cannot be found in said searching for a matching portion due to the insertion of new data in the new file, said new data is added to the replacement information showing the data of the mismatching portion of the old file at a position until the matching portion can be searched and the resultant replacement information is output.

7. The method according to claim 1, wherein in said outputting shift information, if the matching portion with the data of the new file cannot be found in said searching for a matching portion due to deletion of the data in the old file, the shift information showing a shifting direction and the shift amount up to the backward matching portion in the old file is output.

8. An apparatus for forming a differential data comprising:

a computer system, comprising;

a data comparing unit which sequentially compares a new file and an old file from heads of the files on a predetermined data unit basis;

a transfer information forming unit which, when a match is determined between the new data and the old data, as a result of said sequential comparison, outputs transfer information showing a position in the old file and a data length of the matching data;

a matching portion search unit which, when a mismatch is determined between the new data and the old data, as a result of said sequential comparison, searches for a matching portion with the new data in both forward and backward directions from a position where the mismatch has been determined in the old file;

a shift information forming unit which, if the matching portion can be found, outputs shift information from the mismatch up to the matching portion in the old file; and

a replacement information forming unit which, if the matching portion cannot be found,

when a first difference value of a mismatching portion between the old data and the new data does not match with a second difference value previously stored, outputs by adding the new data as transfer replacement information showing a length of the mismatching portion and the new data, and storing the first difference data, and

when the first difference value matches with the second difference value, outputs transfer increase information showing the first difference value is the same as the second difference value.

9. A computer-readable storage medium which stores a differential data forming program allowing a computer to execute:

comparing a new file and an old file sequentially from head of the new file and head of the old file on a predetermined data unit basis;

when said sequential comparison results in determination of a match between the new data and the old data, outputting transfer information showing a position on the old file and a data length of the matching data; and

when said sequential comparison results in determination of a mismatch between the new data and the old data, searching for a matching portion with the new data in both forward and backward directions from a position determined to be mismatching on the old file;

if the matching portion can be found, outputting shift information from the mismatch up to the matching portion in the old file; and

if the matching portion cannot be found,

when a first difference value of a mismatching portion between the old data and the new data does not match with a second difference value previously stored, outputting transfer replacement information showing a length of the mismatching portion and the new data, and storing the first difference value; and

when the first difference value matches with the second difference value, outputting transfer increase information showing the first difference value is the same as the second difference value.

10. The storage medium according to claim 9, wherein in said searching for a matching portion, when the matching portion and continuous matching portions of a predetermined number (n) or more of data subsequent to said matching portion are found in the old file, it is determined that the data matches.

11. The storage medium according to claim 9, wherein in said searching for a matching portion, when the matching portion and matching portions of a predetermined number (y) or more of data distributed among a predetermined number (x) of data subsequent to said matching portion are found in the old file, it is determined that the data matches.

12. The storage medium according to claim 9, wherein in said outputting shift information, a shifting direction in which a forward position in said old file is set to a negative direction and a backward position in said old file is set to a positive direction and a shift length showing a length of data up to the matching portion in the old file is output as said shift information.

13. The storage medium according to claim 9, wherein in said searching for a matching portion, if a structure of the old file and the new file is that of a program file written by an n-bit code, the searching is performed every other (n) bits in both forward and backward directions from the position determined to be mismatching in the old file.

14. The storage medium according to claim 9, wherein in said outputting transfer replacement information, if the matching portion cannot be found in said searching for a matching portion due to the insertion of new data in the new file, said new data is added to the replacement information showing the data of the mismatching portion of the old file at a position until the matching portion can be found and the resultant replacement information is output.

15. The storage medium according to claim 9, wherein in said outputting shift information, if the matching portion with the data of the new file cannot be found in said searching for a matching portion due to deletion of the data in the old file, shift information showing a shifting direction and the shift amount up to the backward matching portion in the old file is output.