Byte-level file differencing and updating algorithms

Details Byte-level file differencing and updating algorithms Byte-level file differencing and updating algorithms

2005-08-02

2005-08-02

Harvey, Jack (Department: 2142)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000, C714S038110, C717S168000, C717S170000, C709S203000, C715S252000

Reexamination Certificate

active

06925467

ABSTRACT:
A method for performing differencing and updating between electronic files is provided. A byte-level file differencing algorithm receives two byte streams corresponding to an original file and a new file. The new file includes updated and revised versions of the original file. The file differencing algorithm determines a longest common sub-string (LCS) between the two byte streams and divides each of the two byte streams into sub-streams. The sub-streams include the LCS along with prefix and suffix sub-streams to the LCS. The file differencing algorithm then recursively determines an LCS and divides each sub-stream until a size of the sub-streams is less than a pre-specified size. Byte-level differences are then identified between each of the corresponding sub-streams. Further, the file differencing algorithm defines a protocol for structuring a delta file by using a set of operation codes and a variable length integer format to eliminate redundant information in the delta file. Using this protocol, the file differencing algorithm generates the delta file including an operation array that codes the identified byte-level differences.

REFERENCES:
patent: 5479654 (1995-12-01), Squibb
patent: 5742905 (1998-04-01), Pepe
patent: 5832520 (1998-11-01), Miller
patent: 6052531 (2000-04-01), Waldin et al.
patent: 6088694 (2000-07-01), Burns
patent: 6167258 (2000-12-01), Schmidt
patent: 6269456 (2001-07-01), Hodges et al.
patent: 6327671 (2001-12-01), Menon
patent: 6349311 (2002-02-01), Sobel et al.
patent: 6374250 (2002-04-01), Ajtai et al.
patent: 6470329 (2002-10-01), Livschitz
patent: 6526574 (2003-02-01), Jones
patent: 6535894 (2003-03-01), Schmidt et al.
patent: 6694336 (2004-02-01), Multer
patent: 2002/0099726 (2002-07-01), Crudele
patent: 2002/0129107 (2002-09-01), Loughran
patent: 2004/0062130 (2004-04-01), Chiang
patent: 2004/0092255 (2004-05-01), Ji
patent: 2004/0098361 (2004-05-01), Peng
patent: 2004/0098413 (2004-05-01), Peng
patent: 2004/0098420 (2004-05-01), Peng
patent: 2004/0098421 (2004-05-01), Peng
patent: 2004/0098427 (2004-05-01), Peng
patent: 2004/0111427 (2004-06-01), Gu
Walter F. Tichy, “The String-to-String Correction Problem with Block Move”, ACM Transaction On Computer Systems, vol. 2, No. 4, Nov. 1984, pp. 309-321.
Ajtai et al., “Compatly Encoding Unstructured Inputs with Differential Compression”, IBM Almaden Research Center, 44 pages.
Burns et al., “In-Place Reconstruction of Dalta Compressed Files”, IBM Almaden Research Center, 9 pages.
Burns et al., “In-Place Reconstruction of Version Differences”, IBM Almaden Research Center, 25 pages.

Affiliated with

Also associated with

Rating

Byte-level file differencing and updating algorithms does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Byte-level file differencing and updating algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Byte-level file differencing and updating algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3511601