Automatic file differencing and updating system

• US 5,832,520 A
• Filed: 11/22/1996
• Issued: 11/03/1998
• Est. Priority Date: 07/03/1996
• Status: Expired due to Fees

• Current Assignee: Miller Call Plauck and Miller
• Original Assignee: Miller Call Plauck and Miller
• Inventors: Miller, William A.
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US08/754,486
• Time in Patent Office: 711 Days
• Field of Search: 707/203
• US Class Current: 1/1
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: G06F 16/1787 Details of non-transparently synchronising file systems
• CPC Class Codes: G06F 8/658 Incremental updates; Differential updates
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

A method and file structure for generating an efficient difference files from and old file and a new file so that a difference file can be transmitted to a second computer system where the difference file and a duplicate of the old file can quickly be used to create a copy of the new file is disclosed. A differencing process compares an old file and a new file to generate a difference file in which the old file is used as a database of byte strings. The differencing process reads strings of data from the new file, searches for the existence of those strings in the old file, and notes the locations in the old file in which strings in the new file are found and stores in a difference file an indication of the location where a matching string is found and an indication of the length. A specific file structure for the difference file is disclosed.

Claims

1. A method for generating a difference file comprising:

a) reading new file data strings from a new file;

b) searching an old file for the presence of old file data strings matching said new file data strings;

c) when a match is found, storing in said difference file an indication of the position in said old file of said matching strings, along with an indication of a copy operation;

d) when no match is found, storing said new file data string in a location where it will available to said difference file and storing in said difference file an indication of the location of said insert data along with an indication of an insert operation;

e) repeating steps a) through d) until all data in said new file has been read and corresponding insert and copy operations have been written into said difference file.

2. The method according to claim 1 wherein data strings from said new file that are searched for in said old file have a fixed and predetermined length greater than one.

3. The method according to claim 2 further comprising establishing a pointer to a current position in said old file for the purposes of minimizing the amount of position information that must be stored with a copy operation when copying from the current position.

4. The method according to claim 1 further comprising, when a match is found, continuing to compare data from said old file to said new file subsequent to said data string in order to maximize the length of said matching string.

5. The method according to claim 4 wherein when a match is found at a location different than the current position, comparing the amount of data that will need to be stored in said difference file for a copy operation versus an equivalent insert operation and choosing the operation that results in the smallest amount of data being included in said difference file.

6. The method according to claim 1 wherein said searching further comprises creating a text string index from said old file if sufficient system memory exists and using said text string index to quickly locate occurrences of said old file data string in said new file.

7. The method according to claim 6 wherein said text string index is implemented using a hash table and a hash function.

8. The method according to claim 1 further comprising:

f) after said difference file is complete, gathering all new file data stored in said difference into an optimized insertion database in order to reduce redundancies in inserted data.

9. The method according to claim 8 further comprising:

g) encoding said indications of copy operations and insert operations and position indications in order to reduce the size of said final difference file.

10. The method according to claim 1 further comprising:

f) storing along with said difference file executable code to perform file revision in order to allow said difference file to be self-executing to generate a copy of said new file from a copy of said old file.

11. The method according to claim 1 wherein said copy operations and said insert operations are stored in said difference file as commands, each comprising a plurality of fields, said fields indicating the command type, the string count, and the position where the string text is found.

12. The method according to claim 11 wherein there are two copy commands and two insert commands having a form:

CCP;

CE HE SCF! LCF! HCF!

CMP;

CE HE SCF! LCF! HCF! AO

ICP;

CE HE SCF! LCF! HCF!

IMP;

CE HE SCF! LCF! HCF! AO

with CCP indicating a copy from a current position pointer in said old file, CMP indicating a copy from an offset position in said old file, with ICP indicating a copy from a current position pointer in an insert database IMP indicating a copy from an offset position in said insert database, CE being a field for encoding the command type, HE being a field for indicating very short copy or insert string lengths, SCF!, LCF!, HCF! indicating a short count field, long count field and huge count field respectively, and being fields that are not present in all commands, and AO being an address offset field.

13. The method according to claim 12 wherein said CE field is determined by a state machine whose state is determined by the previous command.

14. A computer program product comprising:

computer code that;

a) reads data strings from a new file;

b) searches an old file for the presence of old file data strings matching said new file data strings;

c) when a match is found, stores in a difference file an indication of the position in said old file of said matching strings, along with an indication of a copy operation;

d) when no match is found, stores said new file data string in an insert database and stores an indication of the position of said insert data in said insert database along with an indication of an insert operation;

e) repeats steps a) through d) until all the data in said new file has been examined and corresponding insert and copy operations have been written into said difference file; and

a computer-readable storage medium that stores said computer code.

15. A method for producing a reconstituted file from an existing file and a difference file comprising:

a) reading from said difference file commands indicating data strings to be copied from said existing file into a reconstituted file and data strings to be inserted from an insert database in said difference file into said reconstituted file;

b) copying said data strings indicated from said existing file into said reconstituted file; and

c) inserting data strings indicated from said insert database into said reconstituted file.

16. A method for supplying a revised computer file to a user comprising the steps of:

on a first computer system, comparing a revised file to an old file in order to generate a difference file, said difference file being smaller than said revised file;

transferring said difference file to a second computer system, said second computer system containing a copy of said old file that matches the old file on said first computer system; and

using said difference file and said old file on said second computer system to generate a copy of said revised file on said second computer system, said copy of said revised file on said second computer system matching said revised file on said first computer system.

17. The method according to claim 16 wherein said difference file is transmitted from said first computer system to said second computer system over a transmission medium.

18. The method according to claim 16 wherein said difference file is joined with an executable component at said first computer system, allowing said difference file to be self-extracting after transmission to said second computer system.

19. A difference file for creating a revised file from an existing file comprising:

a plurality of copy commands, each copy command including either implicit or explicit position information with reference to an existing file and including copy string count data;

a plurality of insert commands for inserting data from an insert database, each insert command including either implicit or explicit position information with reference to the insert database and including insert string count data; and

an insert database.

20. A difference file according to claim 19, further comprising command decode trees for decoding said copy string and insert string count data.

21. A difference file according to claim 19, further comprising an executable code unit for creating a revised file from said insert database and said existing file.

22. A file differencing system for creating a difference file from an old file and a new file, said difference file containing all the information necessary to generate said new file from said old file, comprising:

means for opening an old file;

means for opening a new file;

an indexer for creating an index from said old file when sufficient memory is detected;

a text string index for storing index fields from said old file along with a position indication;

a sorter for sorting entries in said text string index;

a search engine for searching for strings of data from said new file and looking up the position of those strings of data in said old file; and

a command writer for assembling commands and data into a raw difference file including strings of data from said new file not found in said old file.

23. The device according to claim 22 further comprising:

an insert database builder for reading insert text found in said raw difference file and creating an optimized insertion database that eliminates most redundancies in said insert data; and

a command encoder for encoding said assembled commands and a count encoder for encoding count fields associated with said commands.

24. A method for generating a difference file comprising:

a) reading a new file data string from a new file;

b) comparing said new file data string to an old file data string at a current position in said old file and if the strings match to at least a predetermined string length, determining the length of the match and writing a copy command, preceded by any accumulated insert data with an insert command, into a difference file and returning to step a;

c) searching an old file for the presence of all old file data strings matching said new file data string to at least a predetermined length and returning the longest matching string and storing in said difference file an indication of the position in said old file of said longest matching string along with an indication of a copy operation, preceded by any accumulated insert data with an insert command;

d) when no match is found, accumulating one byte of insert data, incrementing a pointer to a current position in said new and old files, and returning to step a

e) repeating steps a) through d) until all data in said new file has been read and corresponding insert and copy operations have been written into said difference file.

25. The method according to claim 24 wherein said searching further comprises creating a hash table text string index from said old file if sufficient system memory exists and using said hash table text string index to quickly locate occurrences of said old file data string in said new file.

26. The method according to claim 24 wherein when a match is found at a location different than the current position, comparing the amount of data that will need to be stored in said difference file for a copy operation versus an equivalent insert operation and choosing the operation that results in the smallest amount of data being included in said difference file.

27. The method according to claim 24 further comprising:

f) after finding a matching string at a position different from the current position, attempting to resynchronize the current position pointers in said old and new files by accumulating insert bytes so that a copy from the current position may be performed.

28. The method according to claim 24 further comprising:

f) after said difference file is complete, gathering all insert data stored in said difference into an optimized insertion database in order to reduce redundancies in inserted data;

g) encoding said indications of copy operations and insert operations using a state machine, and encoding copy and insert count indications using Huffman encoding in order to reduce the size of a final difference file.