Byte-level file differencing and updating algorithms

• US 20050234997A1
• Filed: 06/16/2005
• Published: 10/20/2005
• Est. Priority Date: 05/13/2002
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: InnoPath Software, Inc. (Qualcomm, Inc.)
• Inventors: Gu, Jinsheng, Peng, Luosheng
• Granted Patent: US 8,156,071 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99953 Recoverability

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.

Claims

1-28. -28. (canceled)

29. A system for updating electronic files, the system configured to:

receive two byte streams including byte streams corresponding to an original file and a new file, wherein the new file includes updated and revised versions of the original file;

determine a longest common sub-string (LCS) between the two byte streams and divide each of the two byte streams into sub-streams, wherein a first sub-stream is a prefix and a second sub-stream is a suffix to the respective LCS;

recursively determine an LCS and divide each sub-stream until a size of the sub-streams is less than a pre-specified size and determine a byte-level difference between each of the corresponding sub-streams; and

generate a delta file that includes the byte-level difference.