Method and apparatus for finding differences between two computer files efficiently in linear time and for using these differences to update computer files

• US 7,143,115 B2
• Filed: 04/15/2003
• Issued: 11/28/2006
• Est. Priority Date: 04/15/2003
• Status: Active Grant

• Current Assignee: Pocket Soft Incorporated
• Original Assignee: Pocket Soft Incorporated
• Inventors: Wise, William F. Jr., Jones, Kerry N.
• Primary Examiner(s): Rimell, Sam
• Assistant Examiner(s): BELL, CORY C
• Application Number:
  US10/413,784
• Publication Number:
  US 20040210551A1
• Time in Patent Office: 1,323 Days
• Field of Search: 717/168, 717/174, 717/121, 707/203, 707/200
• US Class Current: 707/822
• CPC Class Codes: G06F 8/658 Incremental updates; Differential updates
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A method of updating a computer file from an old file into a new file comprises blocking the new file and the old file into fixed-size blocks, maintaining a window (collection of contiguous blocks) for each file on which lookup preprocessing has been performed, and performing match processing on each new file block in turn (comparing against both the old and new windows) using a key-sampling technique combined with approximate matching. For each new file block, the match information is then optimized for coding efficiency and encoded into a patch file that describes an algorithm for converting the old file into the new file. The patch file application method and apparatus then performs the algorithm described in the patch file. The method uses a fixed amount of random-access memory regardless of the sizes of the two files and uses no temporary mass storage. In addition, the method has a running time roughly proportional to the size of the new file and allows the use of parallel processing to reduce the time required. The system and method produce patch files which are smaller than prior systems and methods, and allow the operator of the apparatus to perform an efficiency/effectiveness trade-off.

Claims

1. A method for converting an OLD computer file into an updated NEW computer file, said method comprising the steps of:

a. identifying differences between said OLD file and a NEW computer file by passing both files through a patch build program, the patch build program comprising the steps of;

i. identifying matches between the OLD file and the NEW computer file by

(a). dividing the NEW computer file into blocks of fixed size,

(b). successively comparing each block to a contiguous group of blocks of fixed size in the OLD file, and

(c). scanning each pair of adjacent blocks of the NEW computer file for matched strings whose starting positions in the NEW computer file differ by less than a fixed window size;

.ii. creating a patch file based on identified matches in step a., wherein the patch file comprises a plurality of blocks corresponding to the fixed size blocks of the NEW computer file and incorporates matched strings in the OLD file and the matched strings in the NEW computer file; and

b. combining said OLD file and said patch file by passing both files through a patch apply program to obtain said NEW file.

2. The method of claim 1 wherein the step of identifying matches between the OLD computer file and the NEW computer file includes the steps of:

a. initializing a NEW string table;

b. selecting a plurality of adjacent blocks beginning with a first block of said OLD file;

c. processing each selected block of the plurality of adjacent blocks with a string table preparation subroutine thereby creating an OLD string table from each selected block;

d. selecting a block beginning with a first block of said NEW file;

e. processing the selected block of said NEW file, said NEW string table, and said OLD string tables with a match table preparation subroutine thereby creating a match table and updating said NEW string table initialized in step 2.a.;

f. transferring said match table to the step of creating a patch file;

g. processing said OLD string tables with a window advancement subroutine thereby possibly selecting a plurality of blocks from said OLD file and processing each selected block of the plurality of blocks with said string table preparation subroutine;

h. processing said OLD string tables with a window trimming subroutine thereby possibly deleting a plurality of said OLD string tables which are no longer required and deleting memory containing portions of said NEW file which are no longer referenced by the NEW string table;

i. selecting a next unprocessed block from said NEW file; and

j. repeating steps through (i) until said NEW file has been entirely processed.

3. The method of claim 2 wherein said match table preparation subroutine identifies exactly matching strings and approximately matching strings.

4. The method of claim 3 wherein said match table preparation subroutine defines two strings as approximately matching when the ratio of mismatches to total characters is less than a selected proportion and each block of adjacent characters contains fewer mismatches than a fixed value.

5. The method of claim 3 wherein said match table preparation subroutine optimizes the lengths of the approximate or exact matches prior to patch file building, said optimization based on estimates of the relative coding efficiency of matches and mismatches.

6. The method of claim 1 wherein said patch file creation method uses variable-length codes selected separately for each block of said NEW file from step 1.a.i.(a).

7. The method of claim 6 wherein said patch file creation method encodes each block from step 1.a.i.(a) using either approximate matches or exact matches, with the decision based on which method produces a smaller coded block.

8. The method of claim 3 wherein said match table preparation subroutine proceeds by locating a fixed-length exact match using said NEW string table and said OLD string tables, then extending said exact match to a longer approximate match in the forward and reverse directions.

9. The method of claim 2 wherein said string table preparation subroutine records and indexes fixed-length substrings whose positions within said selected block are a multiple of a fixed granularity, which is selected from a plurality of integer values.

10. The method of claim 2 wherein said match table preparation subroutine, after examining a string in said NEW file, will then advance by an amount which is calculated from the length of the longest exactly matching string and the length of the longest approximately matching string.

11. The method of claim 2 wherein said match table preparation subroutine, after examining a string in said NEW file, will advance by an amount which is at least a certain fixed minimum advancement increment, which is selected from a plurality of integer values.

12. The method of claim 2 wherein said match table preparation subroutine limits the number of identical fixed-length substrings which will be examined in any one of the OLD or NEW string tables to a certain fixed maximum chain length amount, which is selected from a plurality of integer values.

13. The method of claim 2 wherein said match table preparation subroutine has special provisions to efficiently process strings in said OLD file or in said NEW file consisting of repeated patterns of at least one of a plurality of lengths of characters, said special provisions to avoid repeatedly comparing substrings comprising said repeated patterns.

14. The method of claim 6 wherein said patch file creation method uses separate variable-length code tables for characters, displacements and lengths, said character code table to be used for encoding characters which are not a part of any match, as well as for encoding special codes indicating matches, which are followed by lengths and optional displacements or differences, coded using the length and displacement code tables, respectively.

15. The method of claim 14 wherein said special code for matches is selected from the group consisting of:

a. a match in a prior portion of said NEW file, with length and displacement;

b. a match in a prior portion of said OLD file, with length and displacement;

c. a match in a prior portion of said OLD file in which the displacement exceeds the displacement of the previous prior OLD file match, with length and difference;

c. a match in a prior portion of said OLD file in which the displacement is less than the displacement of the previous prior OLD file match, with length and difference;

c. a match in a prior portion of said OLD file in which the displacement is equal to the displacement of the previous prior OLD file match, with length only;

d. a match in a later portion of said OLD file, with length and displacement;

e. a match in a later portion of said OLD file in which the displacement exceeds the displacement of the previous later OLD file match, with length and difference;

f. a match in a later portion of said OLD file in which the displacement is less than the displacement of the previous later OLD file match, with length and difference;

g. a match in a later portion of said OLD file in which the displacement is equal to the displacement of the previous later OLD file match, with length only; and

h. a match at the same position of said OLD file, with length only.

16. The method of claim 14 wherein said patch file creation method uses special character table encodings for mismatches of at least one of a plurality of lengths of characters surrounded by an otherwise matching string, said character table encoding followed by the appropriate number of characters to indicate mismatch contents, followed by a displacement table encoding of the distance between the beginning of said mismatch and the end of the previous mismatch in said surrounding string, or beginning of said surrounding string if this is the first mismatch in surrounding string.

17. The method of claim 16 wherein said patch file creation method, in producing said mismatch encodings, encodes the difference between the actual character in said NEW file and the expected character in said surrounding matching string.

18. The method of claim 16 wherein said patch file creation method maintains a list of recently used mismatch differences for each mismatch size and uses special character table encodings to represent mismatches for which the mismatch difference is identical to one of the recently-used mismatches, said encodings to be followed by an index into said list and a displacement table encoding representing the position of said mismatch as described in claim 15.

19. The method of claim 14 wherein said patch file creation method encodes each fixed size block of the NEW file from step 1.a.i.(a). using one of the following encoding methods, with the decision based on which method produces the smallest encoded block:

a. code tables having variable length codes for characters, displacements and lengths, the code tables to be computed optimally for a selected block and with the code tables included in the patch file block encoding;

b. fixed variable-length codes for characters, displacements and lengths, the fixed length codes designed to be optimal for equally-likely codewords;

c. the variable length codes for characters, displacements and lengths which were used for encoding the immediately preceding fixed size block of the NEW file;

or

d. bypass encoding, in which the block in the new file is transmitted in its entirety.

20. The method of claim 1 wherein said patch apply program comprises the steps of:

a. reconstructing any necessary variable-length code tables from information in the patch file;

b. interpreting coded data in patch file to recover character, match and mismatch information; and

c. building said NEW file from said OLD file and said character, match and mismatch information.

21. An apparatus for controlling a general purpose computer so as to compare an OLD file and a NEW file, to construct a patch file containing the differences between said files, and subsequently enabling a general purpose computer provided with said patch file to construct said NEW file from said OLD file and said patch file, comprising:

a. file input storage means for storing two currently selected blocks of said NEW file and a plurality of currently selected blocks of said OLD file;

b. string table storage means for storing a plurality of OLD string tables and a NEW string table, each comprising a plurality of fixed-length substrings and associated indices within a currently selected block of the OLD or the NEW file selected from the file input storage means;

c. a string table preparation circuit for selecting and indexing successive portions of each of the plurality of currently selected blocks of the OLD file so that contents of said string table storage means are constructed based on said selected block;

d. match table storage means for storing data structures describing exact matches and approximate matches between regions of the currently selected block of the NEW file and;

i. earlier regions of said currently selected block of the NEW file or

ii. regions of the previously selected block of the NEW file or

iii. regions of one of a plurality of currently selected blocks of the OLD file;

e. a match table preparation circuit forming contents of said match table storage means by;

i. using contents of the string table storage means to locate copies of fixed-length substrings of said selected block of the NEW file in;

(a) earlier portions of said currently selected block of the NEW file or

(b) previously selected block of the NEW file or

(c) one of said currently selected blocks of the OLD file,

ii. extending said matches to longer approximate matches in the forward and reverse directions,

iii. recording said matches, said approximate matches and mismatch information, and

iv. updating said NEW string table as portions of said NEW file are processed;

f. a match table optimization circuit controlling the lengths of the approximate matches in the data structures in the match table storage means to produce a minimized patch file, said optimization based on estimates of relative coding efficiency of matches and mismatches;

g. a patch file encoding circuit producing successive blocks of said patch file from optimized match table; and

h. a patch file apply circuit combining said patch file and said OLD file, producing said NEW file.

22. The apparatus of claim 21 wherein said match table preparation circuit defines two strings as approximately matching when the ratio of mismatches to total characters is less than a selected proportion and each block of adjacent characters contains fewer mismatches than a fixed value.

23. The apparatus of claim 21 wherein said patch file encoding circuit uses variable-length codes selected separately for each block of said NEW file.

24. The apparatus of claim 21 wherein said patch file encoding circuit encodes each block using either the approximate matches or the exact matches, with the decision based on which method produces a smaller coded block.

25. The apparatus of claim 21 wherein said string table preparation circuit records and indexes only those fixed-length substrings of the OLD file whose positions within said selected block are a multiple of a fixed granularity, which is selected from a plurality of integer values.

26. The apparatus of claim 21 wherein said match table preparation circuit, after examining a string in said NEW file, will then advance by an amount which is calculated from the length of the longest exactly matching string and the length of the longest approximately matching string.

27. The apparatus of claim 21 wherein said match table preparation circuit, after examining a string in said NEW file, will advance by an amount which is at least a certain fixed minimum advancement increment, which is selected from a plurality of integer values.

28. The apparatus of claim 21 wherein said match table preparation circuit limits the number of identical fixed-length substrings which will be examined in any one OLD or NEW string table to a certain fixed maximum chain length amount, which is selected from a plurality of integer values.

29. The apparatus of claim 21 wherein said match table preparation circuit has special provisions to efficiently process strings in said OLD file or in said NEW file consisting of repeated patterns of at least one of a plurality of lengths of characters, said special provisions to avoid repeatedly comparing substrings comprising said repeated patterns.

30. The apparatus of claim 23 wherein said patch file encoding circuit uses separate variable-length code tables for characters, displacements and lengths, said character code table to be used for encoding characters which are not a part of any match, as well as for encoding special codes indicating matches, which are followed by lengths and optional displacements or differences, coded using the length and displacement code tables, respectively.

31. The apparatus of claim 30 wherein said special codes for matches comprise the following:

a. a match in a prior portion of said NEW file, with length and displacement;

b. a match in a prior portion of said OLD file, with length and displacement;

c. a match in a prior portion of said OLD file in which the displacement exceeds the displacement of the previous prior OLD file match, with length and difference;

d. a match in a prior portion of said OLD file in which the displacement is less than the displacement of the previous prior OLD file match, with length and difference;

e. a match in a prior portion of said OLD file in which the displacement is equal to the displacement of the previous prior OLD file match, with length only;

f. a match in a later portion of said OLD file, with length and displacement;

g. a match in a later portion of said OLD file in which the displacement exceeds the displacement of the previous later OLD file match, with length and difference;

h. a match in a later portion of said OLD file in which the displacement is less than the displacement of the previous later OLD file match, with length and difference;

i. a match in a later portion of said OLD file in which the displacement is equal to the displacement of the previous later OLD file match, with length only; and

j. a match at the same position of said OLD file, with length only.

32. The apparatus of claim 30 wherein said patch file encoding circuit uses special character table encodings for mismatches of at least one of a plurality of lengths of characters surrounded by an otherwise matching string, said character table encoding followed by the appropriate number of characters to indicate mismatch contents, followed by a displacement table encoding of the distance between the beginning of said mismatch and the end of the previous mismatch in said surrounding string, or beginning of said surrounding string if this is the first mismatch in surrounding string.

33. The apparatus of claim 32 wherein said patch file encoding circuit, in producing said mismatch encodings, encodes the difference between the actual character in said NEW file and the expected character in said surrounding matching string.

34. The apparatus of claim 33 wherein said patch file encoding circuit maintains a list of recently used mismatch differences for each mismatch size and uses special character table encodings to represent mismatches for which the mismatch difference is identical to one of the recently-used mismatches, said encodings to be followed by an index into said list and a displacement table encoding representing the position of said mismatch of claim 32.

35. The apparatus of claim 30 wherein said patch file encoding circuit encodes each fixed size block of the NEW file using one of the following encoding methods, with the decision based on which method produces the smallest encoded patch file block:

a. variable-length codes for characters, displacements and lengths, the codes to be computed optimally for this block and tables for the codes included in the patch file block encoding;

b. fixed variable-length codes for characters, displacements and lengths, the codes designed to be optimal for equally-likely codewords;

c. the variable-length codes for characters, displacements and lengths, which were used for encoding the immediately preceding fixed size block of the NEW file;

or

d. bypass encoding, in which the fixed size block in the NEW file is transmitted in its entirety.

36. The apparatus of claim 21 wherein said patch apply circuit performs the functions of:

a. reconstructing any necessary variable-length code tables from information in the patch file;

b. interpreting coded data in patch file to recover character, match and mismatch information; and

c. building said NEW file from said OLD file and said character, match and mismatch information.

37. A system for converting an OLD computer file into an updated NEW computer file, the system comprising:

a. means for identifying differences between said OLD file and a NEW computer file by passing both files through a patch build program, wherein said patch build program comprises;

i. means for identifying matches in which the NEW file is divided into blocks of fixed size and

(a.) each block is successively compared to a contiguous group of blocks of fixed size in the OLD file; and

(b.) each pair of adjacent blocks of the NEW file is scanned for matched strings whose starting positions in the NEW file differ by less than a fixed window size;

ii. means for creating a patch file based on matches identified by the match identification means, wherein said patch file comprises a plurality of blocks corresponding to the fixed size blocks of the NEW file and incorporates matched string in the OLD file and the matched strings in said NEW file; and

b. means for combining said OLD file and said patch file by passing both files through a patch apply program to obtain said NEW file.