Apparatus and method for reconstructing a file from a difference signature and an original file

• US 6,816,872 B1
• Filed: 07/20/1995
• Issued: 11/09/2004
• Est. Priority Date: 04/26/1990
• Status: Expired due to Fees

• Current Assignee: Carbonite Incorporated (Open Text Corporation)
• Original Assignee: TimeSpring Software Corp. (Open Text Corporation)
• Inventors: Squibb, Mark
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): Craig, Dwin M.
• Application Number:
  US08/504,562
• Time in Patent Office: 3,400 Days
• Field of Search: 395/200, 395/600, 715/511, 707/200
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]

Abstract

Invention maintains duplicate files in safe places. A SCAN computer program creates a TOKEN Table of an earlier file. The TOKEN Table reflects the indices of successive segments of the file and the exclusive-or (XR) and Cyclic redundancy check (CRC) products of the characters in each segment. An updated file is compared to the earlier file by comparing the XR and CRC products of segments in the updated file to the XR and CRC products in the TOKEN Table. On detecting matching products for identical segments, the next segments are compared. On mismatch, the segment (window) for the updated file is bumped one character and new XR and CRC products generated and compared. The indices of the TOKEN Table and the offsets from the start of the file of the first characters of the updated file matching segments are set forth in a Match Table. Next the updated file is scrolled through for the non-matching information determined by acting on the indices and offsets of the Match Table to form the TRANSITION Table which is the Match Table and the updated file non-matching information. The TRANSITION Table contains the delta information which may be sent to another location having a copy of the earlier file thereat: the whole updated file need not be sent there. A reconstruction program at the location looks at the TRANSITION Table to determine where to get the characters for the copy of the updated file it is creating.

Claims

1. A combination comprising a storage device, a file stored in said storage device, and a token table stored in said storage device, said token table comprising first and second different hashing mathematical representations for each of a plurality of fixed equal length character segments of said file.

2. A combination according to claim 1, wherein said first hashing representation of each of said segments is an exclusive-or representation of said respective one of said segments of equal character lengths.

3. A combination according to claim 1 wherein each of said segments is comprised of a plurality of sets and said exclusive-or representation is a representation that is a concatenation of an exclusive-or representation of at least a first of said plurality of sets with an exclusive-or representation of at least a second of said plurality of sets.

4. A combination according to claim 1, wherein the segments comprise successive sets of characters and are indexed for identification.

5. A combination as claimed in claim 1, wherein the first mathematical representation comprises an exclusive-or signature term of each segment of said file, each segment comprising sets and the exclusive-or signature term comprising the exclusive-or product of at least a first of said sets concatenated with the exclusive-or product of at least a second of said sets.

6. A combination according to claim 1, wherein the second mathematical representation for each of said segments comprises a cyclic redundancy check product of the characters of the respective segment of the file.

7. A combination according to claim 1, wherein the second mathematical representation for each of said segments comprises an order sensitive hash representation of the characters of the respective segments of said file.

77. The combination according to claim 1 wherein each of said first representations and each of said second representations are associated with one and only one of the segments in said file.

78. The combination according to claim 1 wherein said first and second hashing mathematical representations are generated for each segment from the characters in the segment.

8. A computer apparatus comprising a storage device, a file stored in said storage device, means for generating a token table having a signature of said file and storing said token table in said storage device, said means for generating and storing said token table comprising means for generating first and second different hashing mathematical representations for each of a plurality of fixed equal length character segments of said file.

9. An apparatus according to claim 8, wherein the means for generating said first and second different hashing mathematical representations comprises means for generating the first hashing mathematical representation for each of said segments, said first hashing mathematical representation comprising an exclusive-or representation of said respective one of said segments of equal character length.

10. An apparatus according to claim 8, wherein the segments comprise successive sets of characters and are indexed for identification.

11. An apparatus according to claim 8, wherein the means for generating the first and second different hashing mathematical representations comprises means for generating the second hashing mathematical representation comprising an exclusive-or signature of the characters of the respective segments of the file, each segment comprising sets and the exclusive-or signature of a respective segment comprising the exclusive-or product of at least a first of said sets concatenated with the exclusive-or product of at least a second of said sets.

12. An apparatus according to claim 8, wherein the means for generating the first and second different hashing mathematical representations comprises means for generating the second hashing mathematical representation comprising an order sensitive cyclic redundancy check product of the characters of the respective segments of said file.

13. An apparatus according to claim 8 wherein the means for generating the first and second hashing mathematical representations comprises means for generating a first hashing mathematical representation that is an exclusive-or representation and a second hashing mathematical representation that is an order sensitive hash term of the characters of the respective segments.

14. A method for generating a file signature, in a computer having a memory with a file therein and data processing means for producing a signature of said file, said method comprising generating and maintaining a record of first and second different hashing mathematical representations for each of a plurality of fixed equal length character segments of said file.

15. A method according to claim 14, wherein the step of generating said first and second mathematical representations comprises generating the first representation comprising an exclusive-or representation of said segments of said file.

16. A method according to claim 14, wherein the segments cover successive sets of characters, comprising indexing said sets for identification.

17. A method according to claim 14, wherein the step of generating the first and second mathematical representations comprises generating the first representation comprising an exclusive-or signature for each of said plurality of segments of said file, each segment comprising sets and the exclusive-or signature of a respective segment comprising the exclusive-or product of at least a first of said sets concatenated with the exclusive-or product of at least a second of said sets.

18. A method according to claim 14, wherein the step of generating the first and second mathematical representations comprises generating a second mathematical representation comprising a cyclic redundancy check product of the characters of the respective segments.

19. A method according to claim 14, wherein the step of generating said first and second mathematical representations comprises generating a second mathematical representation comprising an order sensitive hash representation of the characters of the segments.

20. The method of claim 14 further comprising generating a second signature for storage in the memory of differences between said first file and a second file, each of said first and second files having successive segments of characters, comprising a first step of generating, using the data processing means, offsets, each of said offsets representing a distance from a reference point, consisting of a fixed position in both of said first and second data files, of character segments in the second file which are identical to character segments in the first file, said distance from said reference point being the distance of a fixed character position within each respective segment from said reference point.

21. A method according to claim 20, further comprising generating said successive segments which are of equal size and indexing them by ordinal numbers.

22. A method according to claim 20, wherein each segment has a first character, said same position within each respective segment is the position of said first character of each segment and a second step comprises generating offsets which each identify the ordinal number counted from said reference point in the first file of the first character in a character segment in the second file which is identical to a character segment in the first file.

66. A method according to claim 20, further comprising identifying character segments in the second file which are identical to character segments in the first file by generating third hashing mathematical representations for character segments in the second file and comparing the third representations with the first hashing mathematical representations for the character segments in the first file.

67. A method according to claim 66, wherein the steps of generating first hashing mathematical representations for character segments in the first file and generating third hashing mathematical representations for character segments in the second file comprise generating exclusive-or representations of the segments in the respective files.

68. A method according to claim 66, further comprising, for each character segment in the second file for which the third representation matches at least one first representation, generating a fourth mathematical representation for the character segment in the second file and comparing the fourth representation with the second representation for the character segment in the first file having the at least one first representation.

69. A method according to claim 68, wherein the steps of generating second hashing mathematical representations for character segments in the first file and generating the fourth mathematical representation for the character segment in the second file comprise generating cyclic redundancy check products of the characters of the respective segments in the respective files.

79. The method of claim 14 wherein the step of generating the record of first and second different hashing mathematical representations comprises generating one and only one first and second representation for each segment.

80. The method of claim 14 wherein the step of generating the record of first and second different hashing mathematical representations comprises generating the first and second representations for each segment from the characters in the segment.

23. A combination comprising a memory, a signature and a first data file stored in said memory, said signature indicating a difference between said first data file and a second data file with respect to one another, said first and second data files each having successive segments of an equal number of characters and having a reference point at the same character position in both of said first and second data files, said signature comprising a plurality of offsets for said second data file, each offset representing the distance from said reference point in said second data file of a respective segment of said successive segments in said second data file, which is identical to one of said segments in said first data file, the distance from said reference point being the distance of a fixed character position within each respective segment from said reference point.

24. A combination according to claim 23, wherein said segments are indexed in said signature for identifying said segments.

25. A combination according to claim 23, wherein each segment has a first character and each offset indicates the ordinal number counted from said reference point in said second data file of the first character in a character segment in said second data file which is identical to one of said character segments in said first data file.

26. A computer apparatus having a memory with first and second files stored therein, said files each having successive segments of characters, comprising data processing means for generating first and second different hashing mathematical representations for each of a plurality of fixed equal length character segments of said files, means for comparing said hashing mathematical representations of said segments of said files to identify identical character sequences of said files, means for generating a file signature of portions of said files that are different, and means for generating offsets indicating a displacement, from a reference point, of character segments in said second file which are identical to character segments in said first file.

27. An apparatus according to claim 26, comprising means for generating said successive equal sized segments in said files and means for indexing said segments.

28. An apparatus according to claim 26, wherein each segment has a first character and said means for generating offsets generates offsets which each indicate the offset, from said reference point, of said first character of a character segment in said second data file which is identical to a respective character segment in said first data file.

70. An apparatus according to claim 26, wherein the means for comparing said hashing mathematical representations of said segments of said files comprises means for first comparing for each segment the first representation of the segment in the first file with at least one first representation of at least one segment in the second file, and, if the first representation of the segment in the first file matches a first representation of a given segment in the second file, comparing the second representation for the segment in the first file with the second representation for the given segment in the second file.

29. A method of creating, from a first file having fixed length segments of characters and a difference file signature both stored in a computer having a memory and data processing means, a copy of a second file having fixed length segments of characters, said difference file signature indicating similarities and differences between said first file and said second file, an original of said second file having been created before the creation of said difference file signature, said method comprising generating a mathematical representation for each of said segments of the first file to uniquely identify each respective segment, and generating a mathematical representation for each of said segments of the second file to identify each respective segment in the second file, and creating in said difference file signature a record of representations of segments in the original of said second file that are identical to representations of segments in the first file and of the location or offsets of identical segments in the second file, and also storing in the record information which is different in the second file, the offset of said information which is different in said second file being derived from the offsets of identical segments in both said first and second files.

30. A method according to claim 29, wherein a second computer has a memory having a copy of the first file and a data processing means, said method comprising writing in the memory of the second computer said copy of the second file, using said difference file signature and said copy of the first file in the memory of the second computer to recompose the second file.

31. A method according to claim 30 for recomposing said second file, comprising writing a copy of the second file in the memory of the second computer by using said first file in said second computer as a source from which to read segments which are identical in said first and second files in said first computer and using the difference file as a source from which to read characters that are not common to said first and second files.

32. A method according to claim 30, comprising storing copies of the first file at separate locations and one of said copies which is at a first location is, continually and independently of the other, modified thereat to create a second file, and said copy of the second file is created at a second location using said copy of the first file at the second location and said record.

33. A method according to claim 29 wherein each segment has a first character and the record identifies identical segments by the indexes of said segments in said first file and by the offsets of the first characters of identical segments in the second file.

34. A method according to claim 29, wherein the first file is a maintained data base created from the record maintained in memory protected from ordinary user intervention and the second file is a user file, comprising updating the second file.

35. A method for creating a second window segment token from a base window segment token, said method comprising creating a base window segment in a computer memory by reading a segment of a file in a computer memory, said segment in said file being of the same size as said base window segment, calculating an exclusive-or signature that is an exclusive-or representation of the characters of said base window segment of the file to create a base window segment token, creating said second window segment which comprises all characters of said base window segment except the first character of said base window segment and comprises the next character in said file after said segment in said file which was read to form the base window segment by reading said next character in said file, and creating a second window segment token for said second window segment by adjusting the base window segment token to reflect the deletion of the first character of said base window segment and the addition of said next character in said file in forming the second window segment.

63. The method of claim 35 wherein said computer memory contains a second file, the method further comprising:

calculating a second exclusive-or signature for a segment in the second file;

after calculating said first exclusive-or signature for said base window segment and said second exclusive-or signature for said segment in the second file, comparing said first and second exclusive-or signatures;

if said first and second exclusive-or signatures match, calculating a first non-exclusive-or hashing representation of said base window segment and calculating a second non-exclusive-or hashing representation of the segment in the second file to verify whether both said base window segment and the segment in the second file match; and

creating said second window segment from said base window segment and creating said second window segment token from said base window segment token only if said first and second exclusive-or signatures do not match and said first and second non-exclusive-or hashing representations do not match.

71. A method according to claim 35, wherein the step of adjusting the base segment window token comprises exclusive-oring said first character of said base window segment and said next character in said file with said base segment widow token.

36. A storage device having a first file and a signature stored in said storage device, said signature representing differences of said first file with respect to a second file, said signature comprising offsets indicating a displacement of identical fixed length segments in said second file from the location of said segments in the first file.

37. A storage device according to claim 36, wherein the files have extents of successive segments in said second file which are identical to successive segments in said first file, and said signature includes representations of the extents of successive segments which are identical in both files.

38. A method of periodically maintaining, in a computer having a read/write storage device and data processing means, an archival record of a first version of a file and periodic changes to the first version of the file, the file being at least periodically updated in the read/write storage device, comprising periodically generating, using the data processing means, exclusive-or mathematical representations and order sensitive hash products of fixed length segments of the file, and creating a record in the read/write storage device of those representations and hash products that are identical to representations and hash products of segments in the file at the end of previous periods of said periodical updating, said record further comprising segments in the original version of the file that are different from said segments at the end of said previous periods of said periodical updating.

39. A method according to claim 38, comprising storing each periodically created record in the read/write storage device, and permanently storing the first version of the file and each of the records in the read/write storage device.

40. A method according to claim 39, comprising modifying said archival record to make said periodic changes with a word processor program, and the file is a word processing document.

41. A method according to claim 39 in which the computer also has a write once, read many times device comprising storing a copy of the first version of the file and the records in said write once, read many times device for a permanent archival record.

42. A method according to claim 39, wherein a copy of the first version of the file is stored in the read/write storage device, and comprising creating a copy on the read/write storage device of the file as it existed at the time one of said records was created by using the records up to that time and the first version of the file and the data processing means.

72. A method according to claim 38, wherein the step of creating a record comprises comparing exclusive-or representations of segments in the file with exclusive-or representations of segments of an earlier version of the file, and comparing order sensitive hash products of only those segments in the file whose exclusive-or representations match exclusive-or representations of segments of the earlier version of the file with order sensitive hash products of the matching segments of the earlier version of the file.

43. A method for producing a copy of a second file that is an updated version of an original file in a storage device, comprising producing a token set from each of the original file and an updated version of said original file, comparing the token sets of the original file and said updated version of said original file to identify the offsets of character segments in the updated version of said original file which are identical to character segments in said original file, thereby also identifying information in said updated version of said original file which is unmatched in said original file, each token set comprising first and second different mathematical representations of each segment of said original file and of each segment of said updated version of said original file.

44. The method of claim 43 wherein a residue comprising said unmatched information remains following said step of comparing, and further comprising combining said residue with said identical character segments in said original file and said updated version of said original file, to produce a difference signature file.

45. The method of claim 43 further comprising generating a difference signature file, in which differences between the original file and the updated version of the original file are recorded from a residue of said comparison, said residue corresponding to segments of the files that do not compare, and producing said copy of said second file from said difference signature file and a copy of said original file.

46. The method of claim 45 further comprising transmitting said difference signature file to a second storage device at a remote location for said step of producing said copy of said second file at said remote location, whereby the provision of only said original file at said remote location is necessary.

73. The method of claim 43 wherein the step of comparing the token sets of the original file and the updated versions comprises comparing the first representations of segments of the original file and updated version and comparing the second representations only for segments of the original file and updated version having identical first representations.

47. A method for producing a first file representative of differences between second and third files, comprising generating first and second hash tables from successive equal length segments of each of said second and third files by generating successive first and second different mathematical representations of equal length segments of said second and third files, respectively, wherein a segment is a set of successive characters, comparing said first and second hash tables, with respect to said second and third files, to identify segments of said second and third files that match one another, and producing said first file by listing segments of said second and third files that match one another.

48. The method of claim 47 wherein said comparison of said first and second hash tables identifies a residue corresponding to segments of said second and third files that do not compare, said method further comprising adding said residue to said first file.

49. The method of claim 47 wherein said step of comparing comprises successively comparing said first and second mathematical representations of said segments of said second and third files.

50. The method of claim 47 wherein said step of generating said first representations comprises generating exclusive-or representations of successive equal length segments of said second and third files.

51. The method of claim 47 wherein said step of generating said second representations comprises generating order sensitive hash representations of successive equal length segments of said second and third files.

74. The method of claim 47 wherein the step of producing said first file further comprises listing offsets of segments in said third file which match segments in said second file, wherein said offsets indicate a displacement of the matching segments in the third file from a reference point in the third file.

52. A method for producing a token table from a computer data file in a memory media, the method comprising, for each of a plurality of fixed length segments in the data file, the steps of:

(a) generating a first hashing representation for the segment;

(b) generating a second hashing representation for the segment; and

(c) concatenating said first and second hashing representations into a segment representation.

53. The method of claim 52 further comprising, for each of said plurality of fixed length segments, the steps of

(d) reading a respective fixed length segment of said data file into said memory media before generating said first hashing representation; and

(e) recording said segment representation in said memory media; and

repeating steps (a)-(e) for each of said plurality of fixed length segments until all of said segments in said data file have been read and the token table contains one segment representation for each segment in said data file.

54. The method of claim 52 wherein said plurality of segments are nonoverlapping.

55. The method of claim 54 wherein said plurality of segments are consecutive.

56. The method of claim 52 wherein said first hashing representation is an exclusive-or representation and said second hashing representation is a non-exclusive-or representation.

57. The method of claim 56 comprising generating said exclusive-or representation by

(a) calculating the exclusive-or product of each character in the segment;

(b) dividing the segment into equal length subsets;

(c) generating an exclusive-or product for at least one of said subsets of the segment; and

(d) concatenating the exclusive-or product for at least one of said subsets with the exclusive-or product of each character in the segment to form said exclusive-or representation.

58. The method of claim 56 wherein said non-exclusive-or hashing representation is a cyclic redundancy check product.

59. A method for producing a token table from a computer data file in a memory media, the method comprising, for each of a plurality of fixed length segments in the data file, the steps of:

(a) generating a first hashing representation for the segment using a first algorithm; and

(b) generating a second hashing representation for the segment using a different algorithm from said first algorithm,

said first and second hashing representations together comprising a segment representation for each segment.

60. A token table in a memory medium comprising first and second different hashing representations of each of at least two nonoverlapping, fixed equal length segments in a file in said computer.

61. The token table of claim 60 wherein said first and second different hashing representations for at least one of said segments are concatenated as a single segment representation in said token table.

62. The token table of claim 60 wherein said file comprises text and said length of said segments is independent of the length of sentences in said text.

64. A method for storing different versions of a computer file having a plurality of fixed length segments in a first memory media associated with a data processor, comprising the steps of:

(1) generating a token table in said first memory media, said token table comprising two hashing representations for each of said plurality of fixed length segments of a first version of said computer file,

(2) generating a record of differences between the first version of said computer file and a second version of said computer file using said token table, and

(3) storing said record in a second memory media.

65. The method of claim 64 wherein said first memory media is in a node of a network and said second memory media is in a server in said network.

75. A method for producing a token table from a computer data file in a memory media, the method comprising, for each of a plurality of fixed length segments in the data file, the steps of:

(a) generating a first hashing representation for the segment;

(b) generating a second hashing representation for the segment; and

(c) associating the first representation with the second representation in the token table.

76. The method of claim 75 comprising storing in the token table indexes identifying the segments and wherein the step of associating comprises associating the first and second representations with the respective index for the respective segment.