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.

Description:
FIELD OF INVENTION  
         [0001]    The present invention relates generally to the field of transmission of computer files and, more particularly, to the practice of transmitting updated versions of computer files by transmitting another file containing the differences between the old and new files, then reconstructing the new file at the receiver from the old file and the difference file.  
         BACKGROUND OF THE INVENTION  
         [0002]    To efficiently update a version of a computer file, it is known to transmit a (smaller) file that describes the differences between the old version and the new version. More specifically, the difference file (or patch file) must describe an algorithm that converts the old file into the new file. Generally, known methods for automatically constructing such patch files have used the old file as a dictionary for encoding the new file, so that there are two parts to the patch file building process: finding substrings in the new file that match some substring of the old file, and then encoding these matches and the mismatched region in some efficient way.  
           [0003]    There are three essential features to be considered in the design of such a method: efficiency, effectiveness, and scalability. In this context, efficiency refers to the method&#39;s economical use of time, effectiveness refers to the size of the patch files produced by the method, and scalability refers to the economical use of computational resources, particularly random-access memory, as the sizes of the old and new files grow. Generally, for any method, there are tradeoffs among these three design parameters. We will discuss the prior art from these three viewpoints.  
           [0004]    First, the problems of patch file construction are similar to the problems of file compression problem. In file compression, one normally uses the earlier portion of the file (head) as a dictionary for encoding the later portion of the file (tail). The difference between file compression and patch file construction is that they use a different dictionary. Thus, it might seem that utilizing some of the well-known file compression techniques, adjusted slightly, might produce good results for patch file construction. The discussion here applies equally to the methods in Welch (U.S. Pat. No. 4,558,302); Waterworth (U.S. Pat. No. 4,701,745); Nagy (U.S. Pat. No. 5,001,478); Katz (U.S. Pat. No. 5,051,745); Seroussi et al. (U.S. Pat. No. 5,389,922); and Mayers et al. (U.S. Pat. No. 5,532,694), as well as the other standard on-line compression methods discussed in Storer,  Data Compression, Methods and Theory  (Computer Science Press, 1988). There are three problems with this general approach, no matter which of the above compression methods is used:  
           [0005]    1. The need for scalability in the compression methods requires some sort of windowing in which the dictionary is limited to “recent” strings (although, in some cases, strings that have been used frequently get moved to a sort of “Hall of Fame” in which they may continue to be used long after their initial appearance). However, in all cases, a string that isn&#39;t used at all within a certain window after its initial appearance will never be used subsequently. This causes significant effectiveness problems when these techniques are used in a patch file construction setting without a sufficiently large window. One particular problem occurs when, for example, a database file is re-sorted, maintaining nearly the same data as before, but in a completely different order. If the window is too small, this will cause the patch file construction method to fail to find all relevant matches. Extremely large files (on the order of hundreds of megabytes) tend not to manifest this modification pattern, but moderately large files (tens of megabytes) certainly do.  
           [0006]    2. All these methods utilize exact matches in the string-matching portion of the compression process. While this does not cause any effectiveness problem in the compression case, it does cause problems for patch file construction because it fails to take advantage of the pattern of changes present in many updated files, particularly executable files and databases. These files tend to have large blocks that are the same, with the exception of short (one- to four-character) bursts of mismatches, which arise from code that refers to another part of the file that has moved. Much greater effectiveness (experimentally, in some cases, a factor of 4 in patch file size has been observed) can be achieved by using a “sloppy” match method in which some mismatches are allowed in order to increase the length of the matched strings (and thereby allow fewer matches to be encoded). The mismatches must, of course, be encoded separately. This sort of coding is not used in compression methods because there one doesn&#39;t typically have this sort of “burst mismatch” phenomenon occurring.  
           [0007]    3. All these methods are what are known in the art as “greedy algorithms.” That is, (in this context) matching methods that always use the longest match possible at every stage. Methods that are not “greedy” need an additional pass of the data to make decisions about which match to use at each stage once all the facts are in. There is a good reason for this in the compression case: efficiency. In order to make a compression method sufficiently scalable, one uses the windowing technique mentioned above. One could certain add this optimization to the compression methods, but it seems not to be commonly done in the art.  
           [0008]    Consideration of problem (2) above might lead one to consider the methods derived in the field of “approximate string matching”. In this field, one basically derives efficient methods for computing the “edit distance” or “Levenshtein distance” between two strings, that is, the minimal number of character insertions, deletions or changes that is required to convert one string to the other. Other measures of similarity are occasionally used, but this is the primary one in the literature. The following discussion applies to all of the following references:  Finding approximate patterns in strings  by E. Ukkonen in  J. Algorithms,  vol. 6 (1985);  Algorithms for approximate string matching  by E. Ukkonen in  Inform. and Control,  vol. 64 (1985);  Minimum detour methods for string or sequence comparison  by F. Hadlock in  Congr. Numer.,  vol. 61 (1988);  On locally optimal alignments in genetic sequences  by N. Blum in  Lecture Notes in Comput. Sci.,  vol. 577 (1992);  String editing under a combination of constraints  by S. Petrović and J. Golić in  Inform. Sci.,  vol. 74 (1993);  Approximate string-matching over suffix trees  by E. Ukkonen in  Lecture Notes in Comput. Sci.,  vol. 684 (1993);  On suboptimal alignments of biological sequences  by D. Naor and D. Brutlag in  Lecture Notes in Comput. Sci.,  vol. 684 (1993);  O ( k )  parallel algorithms for approximate string matching  by Y. Jiang and A. Wright in  Neural Parallel Sci. Comput.,  vol. 1 (1993);  Longest common subsequences  by M. Paterson and V. Dancik in  Lecture Notes in Comput. Sci.,  vol. 841 (1994);  Parametric optimization of sequence alignment  by D. Gusfield, K. Balasubramanian and D. Naor in  Algorithmica,  vol. 12 (1994);  Approximate string matching with don&#39;t care characters  by T. Akutsu in  Inform. Process. Lett.,  vol 55 (1995); and  Fast approximate matching of words against a dictionary  by H. Bunke in  Computing,  vol. 55 (1995).  
           [0009]    All of these are quite efficient methods for accomplishing what they set out to do: generally this is to find a portion of a first file (the dictionary) that approximately matches a portion of a second file (the text string). The details of the approximate matching vary from method to method. In some cases, they locate the substring of minimal edit distance; in other cases, they locate the collection of substrings having edit distance within a fixed tolerance of the minimum; in still others, they locate various substrings that are minimal for various choices of weighting in a generalized edit distance. However, they all share two problems relating to their use in patch file building.  
           [0010]    In approximate matching, a small edit distance does not directly translate into effective patch file coding. Even using the generalized edit distance approach in which insertions, deletions and substitutions have different costs or weights assigned to them, none of these approaches deals adequately with the sorted database scenario (in which very little of the information has changed, but it has been radically re-ordered) or the very similar problem of an executable file in which the link order was changed. Both of these are quite difficult to deal with from the insertion/deletion/substitution point of view, but the “copy or add” point of view used in a non-windowed compression method deals with these quite handily.  
           [0011]    Further, all of these methods have scalability problems. Many of the methods require random-access memory that grows exponentially with the size of the files. None of them can be accomplished, without major modifications, with a fixed amount of random-access memory. These are all theoretical methods that accomplish their goals beautifully, but their design constraints do not necessarily include practicality and scalability.  
           [0012]    There is yet another method that is quite familiar to practitioners of the art, usually referred to as “diff” after the Unix command of that name built on this method. This method is discussed in Squibb (U.S. Pat. No. 5,479,654) and is widely known, since the source code to the Unix embodiment of the method is publicly available. The method, developed for use with text files, passes both files simultaneously. When a mismatch occurs, both files are scanned forward, line-by-line, in an attempt to re-align. If realignment occurs, the method proceeds to the next mismatch.  
           [0013]    This approach, while completely scalable and quite efficient, has some serious difficulties with effectiveness. First, it does not deal adequately with binary (non-text) files at all. These files are not organized into “lines” and thus the blocking method used by diff fails completely. Second, it does not deal adequately with the burst mismatches so common in executable files. As far as diff is concerned, any mismatch causes the entire block to mismatch (assuming that the blocking problem can be solved somehow). This leads to far too few matches for an effective patch file construction. Third, since it never re-examines previous portions of the old file, it deals inadequately with the sorted database scenario mentioned previously. Fourth, the method is still a “greedy” algorithm.  
           [0014]    The first of these problems has been dealt with in a program called “bdiff” (available as part of many newer versions of Unix) which does binary file comparison and patch file construction, but the other three problems have never been adequately resolved in this method: experimentally, bdiff (even when the resulting patch files are compressed) produces much larger patch files than, for example, .RTPatch by Pocket Soft, Inc., shown and described in U.S. Pat. No. 6,526,574 and assigned to the same assignee as the present invention. Its scalability, efficiency, and effectiveness may be assessed by experimental means.  
           [0015]    There is another class of patch file construction methods known in the art. These may be collectively referred to as “block-and-hash” methods. In these methods, the old file is divided into (usually fixed-size) blocks and a signature (or hash function) is computed for each block. Then, the same procedure is used on the new file and the hash tables are compared. Any blocks having the same hash value are then examined for matches and the usual “copy or add” encoding is applied to build a patch file. This class of methods includes those in Queen (U.S. Pat. No. 4,807,182); Pyne (U.S. Pat. No. 5,446,888); Squibb (U.S. Pat. No. 5,479,654); and Morris (U.S. Pat. No. 5,574,906). Like “diff,” these methods tend to be completely scalable and quite efficient, but not very effective for many purposes. In some cases, an isolated insertion at the beginning of the new file can cause the method to find no matches at all. In order to overcome this serious difficulty, some methods do away with the blocking on the new file and hash at every position. This, however, degrades the efficiency markedly. Still more problematic, however, is the fact that the burst mismatches so common in executable files cause many matches to go undiscovered by these methods. Finally, they are all “greedy” methods, which, as observed above, inherently lose some effectiveness.  
           [0016]    We have mentioned that “greedy” methods are inherently somewhat lower in effectiveness than “optimized” methods. There is a known solution to the optimal coding problem that does apply to this situation, namely, Wagner&#39;s algorithm (see Storer,  Data Compression, Methods and Theory,  Computer Science Press, 1988). This method provides a scheme for optimizing the “copy or add” encoding of a file in terms of any fixed dictionary. To apply Wagner&#39;s algorithm to this problem (in conjunction with the approximate matching method mentioned above, to help with the burst mismatches), it would be necessary to locate every approximate match between old and new files and keep track of the number of isolated mismatches within each approximate match and their positions relative to the beginning of the approximate match. With all this information in hand, Wagner&#39;s algorithm gives a “most effective possible” solution to the encoding problem. However, there are serious scalability problems here (storage of all the approximate matches as well as each mismatch within each approximate match) as well as efficiency problems (in gathering the data, not in applying Wagner&#39;s algorithm, which is itself quite efficient).  
           [0017]    Another known method is that described in Jones (U.S. Pat. No. 6,526,574). This method is efficient, effective, and scaleable in terms of mass storage and random-access memory resources, but does not scale well in terms of time. Specifically, its time is quadratic with the size of the new file, so that it is impractical to use with extremely large files (hundreds of megabytes).  
           [0018]    We conclude our discussion of the prior art with experimental results on .RTPatch, ver. 3.20 by Pocket Soft, Inc., mentioned above as being experimentally superior in effectiveness to the combination of bdiff and compression. This commercial product is fairly effective and efficient on small files, but has serious scalability problems. In order to work efficiently, it needs twice as much random-access memory as the file size and in fact fails completely on files above 20-30 million characters in size.  
           [0019]    Accordingly, several objects and advantages of our invention are that it provide a method that is scalable (all files are accessed sequentially, so they can be located offline; essentially no temporary mass storage resources are needed; random-access memory requirement is constant), effective (patch file size is, in empirical tests, significantly smaller than prior art tested—bdiff, version 3.20 of .RTPatch, version 4.00 of .RTPatch which is based on Jones (U.S. Pat. No. 6,526,574) and efficient (running time is linear in the size of the files, substantially shorter running time than existing commercial products of comparable effectiveness).  
           [0020]    This method is also tunable in the sense that the operator can perform an effectiveness/efficiency tradeoff. The method is also amenable to embodiments employing parallel processing to further reduce the time required by the method.  
           [0021]    Still further objects and advantages will become apparent from a consideration of the ensuing description and accompanying drawings. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0022]    [0022]FIG. 1 is a block diagram of the patch file construction system and process.  
         [0023]    [0023]FIG. 2 is a block diagram of the preferred embodiment of the patch file application process (that is, the process of using a patch file and an old file to produce the new file).  
         [0024]    [0024]FIG. 3 shows the preferred embodiment of the OLD String Table.  
         [0025]    [0025]FIG. 4 shows the preferred embodiment of the NEW String Table.  
         [0026]    [0026]FIG. 5 shows the layout of the Match Table.  
         [0027]    [0027]FIG. 6 is a flowchart of the Match Table Preparation Process.  
         [0028]    [0028]FIG. 7 is a flowchart of the Match Table Optimization Process.  
         [0029]    [0029]FIG. 8 shows a flowchart of the Patch File Encoding Process ( 18 )  
         [0030]    [0030]FIG. 9 shows a schematic of the data usage in the patch file construction process 
     
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS  
       [0031]    The present invention provides a method and an apparatus for comparing two binary files and producing a patch file containing the differences between the two files. The apparatus includes a file input means, a plurality of string table storage means, a match table storage means, patch file output means, a means for preparing an OLD string table, a means for preparing a match table and a NEW string table, a means for optimizing the match table, a means for patch file encoding, and a means for reconstructing the second file from the first file and the patch file. Patch Construction  
         [0032]    [0032]FIG. 1 illustrates an overview of a presently preferred embodiment of a system  10  for the construction of an output patch file. A NEW String Table, retained in a NEW String Table storage means  26 , is initialized to empty. An OLD Input File is input into an OLD Input File storage means  20  and from there to a String Table Preparation module  12 , which uses a contiguous portion of the OLD Input File storage means  20  to produce a plurality of OLD String Tables, which are stored in an OLD String Tables storage means  24 . Throughout this description, a “module” may also be referred to as a “process” or “method”, to the same extent. Next, a Match Table Preparation module  14  takes a portion of a NEW Input file stored in a NEW Input File storage means  22  and the OLD String Tables in the OLD String Tables storage means  24  and produces a Match Table, which is retained in a Match Table storage means  28 . The Match Table Preparation module also produces or alters NEW string table in a NEW String Table storage means  26 . At this point, a Match Table Optimization module  16  operates on the Match Table in the Match Table storage means  28  and alters it. A Patch File Encoding module  18  then operates on the Match Table in the Match Table storage means  28 , the OLD Input File  20  and the NEW Input File  22  to produces a portion of a Patch File, passing it to Patch File output means  32 . The OLD Input File  20  and the NEW Input File  22  are then advanced by a File Advancement module  30  and the process is repeated until the entire NEW input file  22  has been processed, as determined by a decision module  19 .  
         [0033]    Patch Application  
         [0034]    [0034]FIG. 2 illustrates an overview of a presently preferred embodiment of a system  37  for patch application. An Input Patch File  40  is passed to a Patch File Decoder module  34  which processes a block of the Input Patch File  40  and produces an Auxiliary Table  42 . A NEW File Construction module  36  then operates on the Auxiliary Table  42  and a portion of an OLD Input File  38  to produce a portion of a NEW Output File  44 . This process is repeated until the entire Input Patch File  40  has been processed, as determined by a decision module  39 . At that point, the NEW Output File  44  has been entirely constructed.  
         [0035]    OLD String Table  
         [0036]    [0036]FIG. 3 illustrates a presently preferred embodiment of one of a plurality of OLD String Tables  24  (see FIG. 1), in accordance with this invention. Each OLD String Table  24  corresponds to a block of fixed size in the OLD Input File  20 . An OLD String Table comprises two data structures: a Chain Array  52  and an eight-way B-tree  53 . The Chain Array  52  has its rows indexed by character offsets relative to the beginning of the block (with each offset being a multiple of a fixed increment). The preferred embodiment uses a block size which is 65536 multiplied by the selected increment so that the Chain Array  52  has 65536 rows. The initial strings of length three located at multiples of the selected increment are organized into chains. A chain is a group of offsets whose first three characters are identical. The eight-way B-tree  53  comprises one B-Tree Root Node  46 , a plurality of B-Tree Interior Nodes  48 , and a plurality of B-Tree Leaf Nodes  50 , and is used to locate the first entry of each chain, given the three characters with which each string in the chain begins.  
         [0037]    Each row of the Chain Array  52  comprises 8 entries, labeled in FIG. 3 as String, CH, CT, ChainNext, ChainPrev, NM, Middle, and MiddleRev. The String column contains the string of length equal to the selected increment which begins at the indicated offset. CH contains a 1 if the indicated position is the first entry of a chain and contains a 0 otherwise. CT contains a 1 if the indicated position is the last entry of a chain and contains a 0 otherwise. ChainNext (respectively, ChainPrev) contains the index of the next (respectively, previous) entry in the chain. A chain is linked together in a circular fashion, so that the ChainNext column in a row in which CT is equal to 1 points to the first entry in that chain. Similarly, the ChainPrev column in a row in which CH is equal to 1 points to the last entry in the chain. The last three columns are used to locate a position within a given chain which is closest to a fixed offset within the block. These are only in use for one OLD String Table at any given time, and are only valid for entries which have CH equal to 1. NM is equal to 1 for rows in which Middle and MiddleRev are not in use. If CH is equal to 1 and NM is equal to 0, then the Middle (respectively, MiddleRev) column contains the index of the chain member which is the first chain entry after (respectively, before) the fixed offset.  
         [0038]    NEW String Table  
         [0039]    [0039]FIG. 4 illustrates a presently preferred embodiment of the NEW String Table  26  (see FIG. 1), in accordance with this invention. The NEW String Table  26  comprises two arrays, a Hash Array  54  and a Bucket/Chain Array  56 . The Bucket/Chain Array  56  contains a row for each character of the current block of the NEW Input File  22 —the preferred embodiment uses a block size of 65536 characters—and is indexed modulo the block size, so that, for example, row  100  will represent offset  100  relative to the current block, after offset  100  has been processed, but will represent offset  100  relative to the previous block until offset  100  has been processed. The Hash Array  54  has its rows indexed by the possible values of a hash function derived from a string of fixed size (three characters in the preferred embodiment). The preferred embodiment uses a 16-bit hash function so that both arrays have 65536 rows. The initial strings of length three which have already been processed into the NEW string table are organized into hash buckets and chains. A chain is a group of offsets whose first three characters are identical. A hash bucket is a group of chains whose first three characters have the same hash function value.  
         [0040]    Each row of the Bucket/Chain Array  56  comprises 8 entries, labeled Char, BH, CH, CT, BucketNext, BucketPrev, ChainNext, and ChainPrev. The Char column contains the character located at the indicated offset of the current (or previous) block. BH contains a 1 if the indicated position is the first entry of a hash bucket and contains a 0 otherwise. CH contains a 1 if the indicated position is the first entry of a chain and contains a 0 otherwise. CT contains a 1 if the indicated position is the last entry of a chain and contains a 0 otherwise. If CH is a 1, then BucketNext (respectively, BucketPrev) contains the index of the first entry of the next (respectively, previous) chain in the bucket, otherwise BucketNext (respectively, BucketPrev) is undefined and unused. A bucket is linked together in a circular fashion, so that the last chain in a bucket may be identified as possessing a BucketNext field which indexes a row with BH equal to 1. ChainNext (respectively, ChainPrev) contains the index of the next (respectively, previous) entry in the chain. A chain is also linked together in a circular fashion, so that the ChainNext column in a row in which CT is equal to 1 points to the first entry in that chain. Similarly, the ChainPrev column in a row in which CH is equal to 1 points to the last entry in the chain.  
         [0041]    Each row of the Hash Array  54  comprises 2 columns, labeled EB and BucketHead. EB contains a value of 1 if there are no chains in the corresponding hash bucket, otherwise it contains a 0. If EB contains a 0, then BucketHead contains the index of the first entry in the first chain in the hash bucket, otherwise BucketHead is undefined and unused.  
         [0042]    An empty NEW string table  26  is indicated by setting the entire EB column to the value 1.  
         [0043]    Match Table  
         [0044]    [0044]FIG. 5 depicts a presently preferred structure for a Match Table  28  in accordance with this invention. The Match Table  28  comprises two data structures: a Match Description Array  58  and a Modification List  60  comprising a plurality of sublists. The Match Description Array  58  has rows indexed by the characters in the current block of the NEW Input File  22 —the preferred embodiment uses a block size of 65536 characters. The main list is maintained principally for convenience in erasing all the data in the sublists when they are no longer needed.  
         [0045]    Each row of the Match Description Array  58  comprises 9 entries, labeled Type, Disp, Length, ModList, NumMods, TypeExact, DispExact, LengthExact, and BEExact. Type contains an identifier of the kind of match which is the currently best identified approximate match for the indicated offset relative to the current block of the NEW Input File  22 . Match types are: literal, NEW, OLD forward and OLD reverse. Disp contains an unsigned integer which is interpreted in various ways, depending on the Type column—it is either the literal value of the character, the backward offset to the NEW file match, the forward offset to the OLD match or the reverse offset to the OLD match. Length contains the length of the currently best identified approximate match. ModList identifies a sublist entry which refers to the first mismatch within the currently best identified approximate match. NumMods is the number of entries in the ModList sublist. TypeExact identifies the type of the currently best identified exact match for the indicated offset relative to the current block of the NEW Input File  22 . DispExact and LengthExact are analogous to Disp and Length, but refer to the currently best identified exact match. BEExact is used for various purposes in various phases of the method. Except during match optimization, BEExact contains the distance that the currently best identified exact match may be extended in the reverse direction. During match optimization, BEExact contains an estimate of the number of bits required to encode the block of the NEW file from the indicated offset forward.  
         [0046]    Each sublist entry in the Modification List  60  comprises 5 entries, labeled EOC, Offset, OldWord, NewWord, and Next. EOC contains a 1 if the entry is the end of a mismatch chain, and contains 0 otherwise. Offset contains the absolute position of the mismatch in the NEW Input File  22 . OldWord contains the value expected to be at that position. NewWord contains the actual value at that position. The preferred embodiment retains four characters in OldWord and NewWord, since it allows mismatches of up to four characters in length. Next identifies the next entry in the sublist. Note that Next may be valid even when EOC is equal to 1, allowing potentially unrelated lists to be chained together for administrative convenience.  
         [0047]    Match Table Preparation Flowchart  
         [0048]    [0048]FIG. 6 illustrates graphically the steps in the Match Table Preparation Module  14 . The details of this process are discussed more fully in the Operation section below.  
         [0049]    Match Table Optimization Flowchart  
         [0050]    [0050]FIG. 7 illustrates graphically the steps in the Match Table Optimization Module  16 . The details of this process are discussed more fully in the Operation section below.  
         [0051]    Patch File Encoding Flowchart  
         [0052]    [0052]FIG. 8 illustrates graphically the steps in the Patch File Encoding Module  18 . The details of this process are discussed more fully in the Operation section below.  
         [0053]    Schematic Diagram of Patch Build Data Usage  
         [0054]    [0054]FIG. 9 shows how the various string tables and input files interrelate during the Patch Build process.  
         [0055]    Operation  
         [0056]    There are a number of design parameters for the method of the present invention that will impact our discussion of the method in various ways. We begin by enumerating these and giving the values that are used in the preferred embodiment.  
         [0057]    Speed factor (parameter 1): this parameter controls the granularity of the OLD String Tables  24 . Increasing this value allows one to increase efficiency at the expense of effectiveness. The preferred embodiment uses operator-selectable values between 0 and 15 inclusive. The granularity of the OLD String Tables is then set to one more than twice the speed factor.  
         [0058]    Approximate-matching tolerances (parameter 2): these parameters control how closely two strings must coincide to be considered a “match.” Altering these tolerances allows one to tailor the method for specific patterns of changes with different kinds of data. There is a pair of tolerances used in the preferred embodiment: a local tolerance and a global tolerance, both expressed as fractions. A local tolerance of  {fraction (8/16)} specifies that out of each  16 adjacent characters, 8 would be allowed to mismatch before the match was terminated. A global tolerance of  {fraction (1/3)} specifies that the total number of mismatches can be at most    {fraction (1/3)} of the total characters in the match. The preferred embodiment uses values of (   {fraction (8/16)}, {fraction (1/3 )}).  
         [0059]    Chain length limits (parameter 3): this parameter controls the maximum number of identical key values that will be chained together in the OLD String Tables  24  and NEW String Table  26 . It is necessary to limit this for efficiency reasons. If no limit is placed on the length of a chain, then a file consisting entirely of repeating patterns degrades the efficiency of the Match Table Preparation  14  process without helping its effectiveness. Too low a value for this limit, however, will cause effectiveness problems, since some potentially useful matches will not be found. The preferred embodiment uses a fixed value of 4096 for this parameter, but values between 250 and 16000 are certainly reasonable. Altering this parameter based on available memory size is also a potentially helpful ramification of the preferred embodiment.  
         [0060]    Coding estimation parameters (parameter 4): these control the scoring (used in the Match Table Preparation  14 ) of an approximate match. The preferred embodiment uses a score for a match of half the length of the exactly matching prefix plus the integer quotient of the number of exactly matching characters and one more than the number of mismatching characters. As an example, a match which comprises 20 characters, 6 of which mismatch, with the first mismatch occurring on the 8 th  character, would receive a score of (7/2)+(14/7)=5, whereas a match which comprises 15 characters, 2 of which mismatch, with the first mismatch occurring on the 9 th  character, would receive a score of (8/2)+(13/2)=10 and would be regarded as a better match, a priori. This scoring is used only for approximate matches; exact matches are ranked by their length.  
         [0061]    Block Size parameters (parameter 5): these control the size of the blocks used in the OLD String Tables  24  and NEW String Table  26 . These may be specified independently. The preferred embodiment uses 65536 characters for the NEW Block Size. For the OLD Block Size, it uses the maximum size which allows for the storage of 65536 strings in each table. This size is thus dependent on the granularity of the OLD String Table, which is selected by parameter 2.  
         [0062]    Window size parameter (parameter 6): this controls the number of OLD String Tables that will be maintained. The preferred embodiment allows this to be specified by the operator.  
         [0063]    Minimum NEW match size (parameter 7): this controls the size of the substring keys which are hashed into the NEW String Table  26 . The preferred embodiment uses a fixed size of 3 characters.  
         [0064]    Minimum OLD match size (parameter 8): this controls the size of the substring keys which are indexed with the B-Trees in the OLD String Tables  24 . The preferred embodiment used operator-selectable values of 4, 6 or 8 characters.  
         [0065]    Minimum advancement size (parameter 9): this affects the amount of progress made when an approximate match is located. The preferred embodiment uses operator-selectable values of 1, 4 or 8 characters. In addition, one of three strategies may be selected: normal, half-greedy and greedy. The preferred embodiment uses normal for speed factors of 0 through 7 inclusive, half-greedy for speed factors of 8 through 11 inclusive, and greedy for speed factors of 12 through 15 inclusive. Either the half-greedy or greedy strategy eliminates the use of exact matches.  
         [0066]    The patch build process proceeds by initially selecting the first block of the NEW file (size selected by parameter 5) and emptying the NEW String Table  26 . The String Table Preparation module  12  then produces a number (selected by parameter 6) of OLD String Tables  24 . These tables are designed to provide extremely rapid location of all matching strings of appropriate lengths (selected by parameter 8). All the strings in a block which begin with the same substring are chained together in circular doubly-linked lists (the information in the Chain Array  52 ), whose heads may be rapidly located by way of an 8-way B-Tree. In addition to the usual information needed for a circular doubly-linked list, the Chain Array also optionally maintains two additional pointers into each list, labeled Middle and MiddleRev. These two pointers are positioned so as to point to the strings in the chain which are the nearest strings, in the forward or reverse direction, to a fixed offset within the block of the OLD Input File  20  to which this OLD String Table  24  refers.  
         [0067]    When the OLD String Tables  24  corresponding to the initial window of the OLD Input File  20  have all been built, the Match Table Preparation Process  14  of FIG. 6 is initiated. This process locates both approximate and exact matches for substrings of the NEW Input File  22 . These matches will be located either in earlier portions of the NEW Input File  22  or in portions of the OLD Input File  20  which are indexed by the OLD String Tables  24 . The Match Table Preparation Module  14  proceeds using five state variables: Current NEW Pointer, Current OLD Pointer, Current Direction, Current FWD Table, and Current REV Table. Initially, in step  602 , Current NEW Pointer, which maintains the position of the substring in the NEW Input File  22  for which matches are being sought, is set to point to the beginning of the currently selected block of the NEW Input File  22 . In step  604 , the Current OLD Pointer is initially set to point to the OLD String Table  24  which indexes that portion of the OLD Input File  20  having its file offset closest to the file offset of the Current NEW Pointer. If the OLD String Table  24  which is pointed to by the Current OLD Pointer does not currently have valid Middle and MiddleRev columns, these are built relative to the OLD Input File  20  offset closest to the offset of the Current NEW Pointer.  
         [0068]    The Match Table Preparation Process  14  then proceeds in step  606  to locate matches by the following procedure. Throughout this description, if the match advancement strategy (selected by parameter 9) is greedy or half-greedy, the exact matching will not be used and will not be computed:  
         [0069]    1. Using the NEW String Table  26 , locate any approximate or exact matches in the recent portion of the NEW Input File  22 .  
         [0070]    2. If any are found, examine a number of matches selected by parameter 3, proceeding in reverse order from chain tail. If the string being matched begins with a repeated pattern of length 1, 2, 3, o r 4, use Repeated Pattern Handling Process  64  to avoid examining some of the matches which will never contribute a best match. Decide which matches are best, using estimates controlled by parameter 4, and record the best match in the match table, then  
         [0071]    3. Set Current Direction to “FWD” in step  608 , set both Current FWD Table and Current REV Table to point to the OLD String Table  24  indicated by Current OLD Pointer. Repeatedly use the following process until all OLD String Tables  24  have been examined:  
         [0072]    a. Use Current Direction to select either the Current FWD Table or the Current REV Table.  
         [0073]    b. Using selected table, locate any approximate or exact matches in the OLD Input File block indexed by selected table in step  610 . If any are found, examine a number of matches selected by parameter 3, proceeding in reverse order from chain tail (MiddleRev if valid) if Current Direction is “REV”, but proceeding in forward order from chain head (Middle if valid) if Current Direction is “FWD”. If the string being matched begins with a repeated pattern of length 1, 2, 3, or 4, use Repeated Pattern Handling Process  64  to avoid examining some of the matches which will never contribute a best match. In step  614 , decide which of the examined matches are best, using estimates controlled by parameter 4, and record the best match in the Match Table  28 , then  
         [0074]    c. In step  612 , if Current Direction is “FWD,” advance Current FWD Table to next OLD String Table. If Current Direction is “REV,” advance Current REV Table to previous OLD String Table. Change Current Direction.  
         [0075]    4. In step  616 , use the Match Advancement Process to adjust the Current NEW Pointer, and, if needed, Current OLD Pointer and the Middle and MiddleRev columns of the OLD String Table  24  pointed to by the Current OLD Pointer. This process also records the matches in the Match Table  28  and adjusts the NEW String Table  26  to reflect the adjustment in the Current NEW Pointer.  
         [0076]    In step  614 , to decide which matches are “best,” an approximate match will be extended exactly in the reverse direction and extended in the forward direction for a distance controlled by parameter 2. When thus extended, a “best” approximate match must have forward length greater than or equal to the forward length of the match currently recorded in the Match Table  28  for this offset, and have a score strictly greater than the score of the “best” match encountered so far, or have a score equal to the score or the “best” match encountered so far and a reverse length greater than the reverse length of the “best” match encountered so far.  
         [0077]    To be considered a “best” exact match, a match must have forward length greater than the forward length of the “best” exact match encountered so far, or have forward length equal to the forward length of the “best” exact match encountered so far and a reverse length greater than the reverse length of the “best” exact match encountered so far.  
         [0078]    The Match Advancement Process  616  first decides whether or not to override the best match found with a literal (only in the case of extremely short matches for which literal coding is shorter than coding the displacement of the match). Then, if the current best match changed, it performs the following procedure:  
         [0079]    1. Build a sublist of the Modification List  60  corresponding to the mismatches in the best approximate match found (if the best approximate match changed).  
         [0080]    2. Fill in prior entries in the Type, Disp, Length, NumMods and ModList columns of the Match Table  28  for a distance equal to the reverse length of the best approximate match so as to correspond to reverse extension of the best approximate match  
         [0081]    3. Fill in subsequent entries in the Type, Disp, Length, NumMods and ModList columns of the Match Table  28  for a distance equal to the forward length of the best approximate match so as to correspond to forward extension of the best approximate match.  
         [0082]    4. Normal strategy only: Fill in prior entries in the TypeExact, DispExact and LengthExact columns of the Match Table  28  for a distance equal to the reverse length of the best exact match so as to correspond to reverse extension of the best exact match.  
         [0083]    5. Normal strategy only: Fill in subsequent entries in the TypeExact, DispExact and LengthExact columns of the Match Table  28  for a distance equal to the forward length of the best exact match so as to correspond to forward extension of the best exact match.  
         [0084]    Then, calculate the Advancement Increment (how far to advance the Current NEW pointer). This calculation is made as follows:  
         [0085]    1. If the best match was changed, do the following:  
         [0086]    a. Do one of the following, depending on the advancement strategy in use (selected by parameter 9):  
         [0087]    i. If the normal strategy is in use, set the Advancement Increment to the length of the best exact match.  
         [0088]    ii. If the half-greedy strategy is in use, set the Advancement Increment to the length of the best approximate match. If this amount is more than 256, reduce it by one half  
         [0089]    iii. If the greedy strategy is in use, set the Advancement Increment to the length of the best approximate match.  
         [0090]    b. If the Advancement Increment is longer than the minimum advancement amount, adjust down so that the excess is a multiple of the OLD String Table granularity (one more than twice the speed factor). If the Advancement Increment is longer than the minimum of the length of the best approximate match and the length of the best exact match, set it to this minimum.  
         [0091]    2. If the best match was not changed, do the following:  
         [0092]    a. Do one of the following, depending on the advancement strategy in use (selected by parameter 9):  
         [0093]    i. If the normal strategy is in use, and there is a mismatch in the best approximate match, set the Advancement Increment to the distance between the current NEW pointer and the first matching character after the first mismatch. If this distance is longer than the minimum advancement amount, adjust up so that the excess is a multiple of the OLD String Table granularity (one more than twice the speed factor). If the Advancement Increment is longer than the minimum of the length of the best approximate match and the length of the best exact match, set it to this minimum.  
         [0094]    ii. If the normal strategy is in use, and there are no mismatches remaining in the best approximate match, set the Advancement Increment to the minimum of the length of the best approximate match and the length of the best exact match.  
         [0095]    iii. If the half-greedy or greedy strategy is in use, set the Advancement Increment to the length of the best approximate match.  
         [0096]    3. If the Advancement Increment is less than the minimum advancement amount (selected by parameter 9), fill in the Match Table  28  entries beyond the current entry whose distance lies between the Advancement Increment and the minimum advancement amount with literal matches. Set Advancement Increment to the minimum advancement amount.  
         [0097]    Once the Advancement Increment is calculated, the Current NEW Pointer is advanced by this amount. This is done by the following procedure:  
         [0098]    1. Do the following a number of repetitions equal to the Advancement Increment:  
         [0099]    a. If the NEW String Table  26  is full, delete the first string in the table.  
         [0100]    b. Add the next string in the NEW File to the NEW String Table  26 .  
         [0101]    2. If the NEW File offset of the Current NEW Pointer plus the Advancement Increment is not located in the OLD String Table  24  corresponding to the Current OLD Pointer, then do the following:  
         [0102]    a. Delete the Middle and MiddleRev columns in the OLD String Table  24  corresponding to the Current OLD Pointer.  
         [0103]    b. Set the Current OLD Pointer to correspond to the OLD String Table  24  that contains the NEW File offset of the Current NEW Pointer plus the Advancement Increment (or the last OLD String Table currently maintained).  
         [0104]    c. Build the Middle and MiddleRev columns in the OLD String Table  24  corresponding to the Current OLD Pointer, based on the offset of the NEW File offset of the Current NEW Pointer plus the Advancement Increment (or the end of the table).  
         [0105]    3. If the NEW File offset of the Current NEW Pointer plus the Advancement Increment is located in the OLD String Table  24  corresponding to the Current OLD Pointer, then adjust the Middle and MiddleRev columns to correspond to the NEW File offset of the Current NEW Pointer plus the Advancement Increment.  
         [0106]    The Repeated Pattern Handling Process  620  is responsible for ensuring that target strings that begin with repeated patterns do not cause the examination of unnecessary strings in either the NEW String Table  26  or the OLD String Tables  24 . It operates as follows:  
         [0107]    1. Calculate the Target Repeat Size (number of characters in the repeated pattern) and Target Repeat Count (number of repetitions of the pattern) in the string being matched.  
         [0108]    2. If an OLD String Table is being examined in the forward direction, calculate the Source Repeat Size and Source Repeat Count of the potential match being examined. Then,  
         [0109]    a. If the Repeat Sizes are different, ignore this potential match and skip over all the repetitions in the source string before examining another potential match.  
         [0110]    b. If the Repeat Sizes are the same and the Source Repeat Count is greater than or equal to the Target Repeat Count, advance the position in the source (OLD File) by a number of repetitions equal to the difference between the two counts, and begin extending the match after the initial repetitions (but include the repetitions in the length count). Then, skip over all the repetitions in the source string before examining another potential match.  
         [0111]    3. If an OLD String Table  24  is being examined in the reverse direction or the NEW String Table  26  is being examined (always in the reverse direction), calculate the Source Repeat Size and Source Repeat Count in the reverse direction of the potential match being examined. Then,  
         [0112]    a. If the Repeat Sizes are different, ignore this potential match and skip backward over all the repetitions in the source string before examining another potential match.  
         [0113]    b. If the Repeat Sizes are the same and the Source Repeat Count is greater than or equal to the Target Repeat Count, begin extending the match after the initial repetitions in the Target string (but include the repetitions in the length count). Then, skip backward over all the repetitions in the source string before examining another potential match.  
         [0114]    When the Match Table Preparation Process  14  is concluded, the Match Table Optimization Process  16  is executed. The logic flow of this module is shown in FIG. 7. This process passes the Match Table  28  in reverse (from the end to the beginning) two times, once to produce an approximate matching estimate and once to produce an exact matching estimate. Each pass uses a variant of Wagner&#39;s algorithm to adjust the lengths of the overlapping matches (either approximate or exact) so as to minimize the estimated total number of bits required to encode the matches. The process then selects the match method (approximate or exact) that produces the smaller bit estimate. This process has two functions:  
         [0115]    1. Adjusting the lengths of the approximate and exact matches so as to produce a non-overlapping collection of matches, doing so in such a way as to produce an optimal encoding, and  
         [0116]    2. Deciding whether to use the approximate or the exact matches in encoding the selected block of the NEW Input File  22 .  
         [0117]    The first function is achieved by processing the Match Table  28  in reverse order, using the BEExact column of the Match Table  28  to store an estimate of the number of bits needed to encode the block from that point on. The approximate matches are processed first. As each Match Table entry is processed, the subsequent entries covered by the Current Match are examined, and the entry is located which has the smallest value of BEExact plus an estimate of the number of bits required to encode the Current Match mismatches up to that entry. The length of the Current Match is then set to be the difference between the Current Match and the entry where the smallest value was found. BEExact in the Current Match row is then set to be equal to the smallest value found, plus an estimate of the number of bits needed to encode the Current Match itself, exclusive of any mismatches. When the entire Match Table  28  has been processed, the BEExact value of the first row is an estimate of the total number of bits needed to encode the entire block optimally using approximate matches. If normal strategy is set (by parameter 9), then this value is stored and the process is repeated for the exact matches.  
         [0118]    The second function is achieved by comparing the exact match estimate to the approximate match estimate and using the match type which has the lower estimate. If a strategy other than normal is being used, then approximate matches are used always, since the exact match columns were not computed in the Match Table Preparation Process  14 .  
         [0119]    When the Match Table Optimization Process  16  is concluded, the Patch File Encoding Process  18  of FIG. 8 is executed. This process makes extensive use of an internal Token List, comprising an array with one row per output codeword, with each row comprising four columns: Type, CodeWord, NumExtraBits and ExtraBits. The Type field is one of three values: C, D or L, indicating that the codeword is to be encoded with the Character, Displacement or Length table. The CodeWord field is a 9-bit or 6-bit codeword, depending on whether the Type field is a C or not (the Character table is a 9-bit table and the Displacement and Length tables are 6-bit tables). The NumExtraBits field is determined by the previous two and is stored for convenience. It indicates how many additional bits follow the variable-length codeword. One fixed codeword schema is used and its description is in Tables 1, 2 and 3 below. Many other codeword schemata are possible, as long as the Patch File Encoding Process  18  and the Patch File Decoder Process  34  agree on the particular schema being used. The ExtraBits field contains the actual bits which are to follow the variable-length codeword.  
         [0120]    The Character table is used for two distinct purposes:  
         [0121]    1. Encoding literal characters, hexadecimal 00 through hexadecimal FF, and  
         [0122]    2. Encoding match types and mismatches (hexadecimal 100 through 113).  
         [0123]    The Displacement table is also used for two distinct purposes:  
         [0124]    1. Encoding match displacements, and  
         [0125]    2. Encoding displacements between successive mismatches (or displacements between the beginning of the previous match and a mismatch).  
         [0126]    The Length table is used for a single purpose, that of encoding match lengths.  
         [0127]    Each table also has a Table Escape value (hexadecimal 114 for the Character table and hexadecimal 33 for the Displacement and Length tables).  
         [0128]    Mismatches are encoded either by a literal encoding of the one-, two- or four-character difference between the match contents and the actual file, or by referring to a Most-Recently-Used (MRU) list of the preceding 16 one-character differences or the preceding 256 two-character and four-character differences.  
         [0129]    The choice as to which of the three tables is to be used for decoding the variable-length codewords is encoded into the bit stream itself without any additional overhead by assuming that the first codeword of each token is encoded with the Character table. Any non-Character table codewords follow this Character codeword and their presence is indicated by the particular Character codeword as described in Table 1.  
         [0130]    The Patch File Encoding Process 18 comprises the following steps:  
         [0131]    1. Processing the optimized Match Table  28  to produce the Token List in step  802 .  
         [0132]    2. In steps  804 ,  806 , and  808 , calculating the number of bits necessary to encode this Token List in several different ways.  
         [0133]    3. In steps  810  through  828  inclusive, selecting the encoding method that produces the smallest number of total bits.  
         [0134]    4. Encoding the Patch File using the selected encoding method in step  830 .  
         [0135]    The encoding methods used by the preferred embodiment are:  
         [0136]    1. Constructing optimized Huffinan Code tables for each of the three code tables and prefixing the tables with the encoded bit stream.  
         [0137]    2. Using “flat” encoding, in which all of the Characters occupy 8 or 9 bits and all of the Displacements and Lengths occupy 5 or 6 bits.  
         [0138]    3. Using the code table generated for the previous block, together with appropriate Table Escapes for codewords that were not present in the previous block.  
         [0139]    4. Using “bypass” encoding, transmitting the entire NEW File block as is, with no coding at all (only necessary when a block is completely new and sufficiently random so as to defeat compression).  
         [0140]    The Patch Application process, shown in FIG. 2, consists of a Patch File Decoder module  34  which processes the Input Patch File  40  one block at a time, reversing the Patch File Encoding Process  18  to obtain an Auxiliary Table  42  which is identical to the Token List used by the Patch File Encoding Process. This Auxiliary Table  42  is then used by the NEW File Construction Process  36 , which produces a block of the NEW Output File  44  by copying matches from the OLD Input File  38  and previously constructed portions of the NEW Output File  44 , modified appropriately by the mismatch indications in the Auxiliary Table  42 . These two processes alternate until the entire NEW Output File  44  is constructed.  
                             TABLE 1                           Character Table Schema            Hexadecimal               Codeword   Meaning   Followed by               00-FF   Literal Character   Nothing       100   End of Block   Nothing       101   One-character mismatch   8 bits + Disp       102   Two-character mismatch   16 bits + Disp       103   Four-character mismatch   32 bits + Disp       104   Window match   Disp + Length       105   0 displacement match   Length       106   One-character MRU mismatch   4 bits + Disp       107   Two-character MRU   8 bits + Disp           mismatch       108   Four-character MRU   8 bits + Disp           mismatch       109   One-character previous   Disp           mismatch       10A   Two-character previous   Disp           mismatch       10B   Four-character previous   Disp           mismatch       10C   FWD match, increase from   Disp + Length           previous       10D   FWD match, same as previous   Length       10E   FWD match, decrease from   Disp + Length           previous       10F   REV match, increase from   Disp + Length           previous       110   REV match, same as previous   Length       111   REV match, decrease from   Disp + Length           previous       112   FWD match   Disp + Length       113   REV match   Disp + Length       114   Table Escape   9 bits (which are then               interpreted as the               corresponding entry in this               table)                  
 
         [0141]    [0141]                             TABLE 2                           Displacement Table Schema (dots indicate       bits which are supplied by literal suffix)            Hexadecimal   Meaning (Binary           Codeword   Displacement)   Followed by               00   1   Nothing       01   1 .   1 bit       02   1 . .   2 bits       03   1 . . .   3 bits       04-   0 0 1 . . . . -   4 bits       0A   111 . . . .       0B-   1 0 0 . . . . . -   5 bits       0E   111 . . . . .       0F-   1 0 0 . . . . . . -   6 bits       12   111 . . . . . .       13-   1 0 . . . . . . . . -   8 bits       14   11 . . . . . . . .       15-   1 0 . . . . . . . . . -   9 bits       16   11 . . . . . . . . .       17-   1 0 . . . . . . . . . . -   10 bits       18   11 . . . . . . . . . .       19-   1 0 . . . . . . . . . . . -   11 bits       1A   11 . . . . . . . . . . .       1B-   1 0 . . . . . . . . . . . . -   12 bits       1C   11 . . . . . . . . . . . .       1D-   1 0 . . . . . . . . . . . . . -   13 bits       1E   11 . . . . . . . . . . . . .       1F-   1 0 . . . . . . . . . . . . . . -   14 bits       20   11 . . . . . . . . . . . . . .       21-   0 1 . . . . . . . . . . . . . . . . -   16 bits       23   11 . . . . . . . . . . . . . . . .       24-   0 1 . . . . . . . . . . . . . . . . . . -   18 bits       26   11 . . . . . . . . . . . . . . . . . .       27-   1 . . . . . . . . . . . . . . . . . . . . -   20 bits-       32   1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   31 bits       33   Table Escape   6 bits (which               are then               interpreted               as the cor-               responding               entry in this               table)                    
         [0142]    [0142]                             TABLE 3                           Length Table Schema (dots indicate bits       which are supplied by literal suffix)            Hexadecimal               Codeword   Meaning (Binary Length)   Followed By               00-   0 1 -   Nothing       02   1 1       03-   1 0 . -   1 bit       04   11 .       05-   0 1 0 . . -   2 bits       0A   111 . .       0B-   1 0 0 . . . -   3 bits       0E   111 . . .       0F-   1 0 0 . . . . -   4 bits       12   111 . . . .       13-   1 0 . . . . . . -   6 bits       14   11 . . . . . .       15-   1 0 . . . . . . . -   7 bits       16   11 . . . . . . .       17-   1 0 . . . . . . . . -   8 bits       18   11 . . . . . . . .       19-   1 0 . . . . . . . . . -   9 bits       1A   11 . . . . . . . . .       1B-   1 0 . . . . . . . . . . -   10 bits       1C   11 . . . . . . . . . .       1D-   0 1 . . . . . . . . . . . . -   12 bits       1F   11 . . . . . . . . . . . .       20-   0 1 . . . . . . . . . . . . . . -   14 bits       22   1 1 . . . . . . . . . . . . . .       23-   1 . . . . . . . . . . . . . . . . -   16 bits-       32   1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   31 bits       33   Table Escape   6 bits (which               are then               interpreted               as the cor-               responding               entry in this               table)                    
         [0143]    [0143]FIG. 9 illustrates a presently preferred embodiment of a schematic for the use of Patch Build Data. Note that there is an array of OLD String Tables  24 , each of which corresponds to a block of the OLD Input File  20 . The entire array of OLD String Tables  24  corresponds to a contiguous collection of blocks, which comprise the currently selected window  21  of the OLD Input File  20 . The particular OLD String Table  24  which corresponds to the block containing the current file offset is the only OLD String Table  24  which has valid Middle/MiddleRev pointers, since it is processed in both the forward and reverse directions. All other OLD String Tables  24  are only processed in one direction. There is a single NEW String Table  26  which refers to a portion of the NEW Input File  22  overlapping the currently selected block and the previously selected block of the NEW Input File  22 .  
         [0144]    Alternate Parallel Processing Patch Build Process  
         [0145]    With some modifications to the preferred embodiment, multiple processors may be used on adjacent blocks of the NEW file simultaneously, allowing even more efficient use of time.  
         [0146]    In order to facilitate multiple processors simultaneously operating on the same OLD and NEW files, each processor would need its own copy of the NEW string table. Some pre-processing would also be needed to initialize the NEW string table to the values appropriate for the preceding block of the NEW file, which block may be currently undergoing processing by another processor. Most of the OLD string tables may be shared, however only the NM, Middle and MiddlePrev columns need ever be private to a particular processor, and each processor would only need such a private copy for one of the OLD string tables at any given time. Apart from these modifications, the operation is identical to the preferred embodiment.  
         [0147]    Accordingly, it can be seen that this method provides a scalable, efficient, effective and tunable means for transmission of an updated binary computer file with significant improvements over the prior art.  
         [0148]    Although the description above contains many specificities, these should not be construed as limiting the scope of the invention but as merely providing illustrations of some of the presently preferred embodiments of this invention. Various other embodiments and ramifications are possible within its scope. For example, special handling could be added to allow for file serialization (portions of the OLD file that differ between the OLD Input File  20  and the OLD Input File  38  ); other ramifications might simplify the process by, for example, making the match table optimization process not alter the match table at all, thus trading effectiveness for efficiency and effectively making this method a “greedy” algorithm.  
         [0149]    Thus the scope of the invention should be determined by the appended claims and their legal equivalents, rather than by the examples given.