Post-processing algorithm for byte-level file differencing

• US 20050010870A1
• Filed: 07/09/2003
• Published: 01/13/2005
• Est. Priority Date: 07/09/2003
• Status: Abandoned Application

• Current Assignee: InnoPath Software, Inc. (Qualcomm, Inc.)
• Original Assignee: InnoPath Software, Inc. (Qualcomm, Inc.)
• Inventors: Gu, Jinsheng, Ren, Liwei
• Application Number:
  US10/616,681
• Publication Number:
  US 20050010870A1
• Time in Patent Office: Days
• US Class Current: 715/229
• CPC Class Codes: G06F 8/658 Incremental updates; Differential updates

Abstract

Devices and methods are provided for generating difference files that include encoded differences between byte streams of original and new file versions. Generation of the difference files includes processing by components of an optimizing system and/or algorithm to identify replacement content in a first area of the new byte stream. The replacement content includes a group of bytes of the new byte stream identified as at least one of byte insertions and byte replacements in a corresponding operation array. The optimizing system identifies content similarities between the replacement content and at least one of the original byte stream and a second area of the new byte stream. The optimizing system generates information of the difference file by encoding information of the content similarities.

Claims

1. An apparatus comprising an optimizing system that generates difference files between an original byte stream and a new byte stream by identifying replacement content in a first area of the new byte stream, wherein the replacement content includes a group of bytes of the new byte streams identified as at least one of byte insertions and byte replacements in an operation array, identifying content similarities between the replacement content and at least one of the original byte stream and a second area of the new byte stream, and encoding information of the content similarities to the difference file.

2. An apparatus for generating difference files, comprising:

means for receiving an original byte stream that is a segment of an original file and a new byte stream that is a segment of a new file, wherein the new file includes an updated version of the original file;

means for identifying replacement content of the new byte stream, wherein replacement content includes a group of bytes of the new byte stream identified as at least one of byte insertions and byte replacements in an operation array;

means for comparing the replacement content and portions of the new byte stream and identifying a first set of content similarities resulting from the comparison;

means for comparing the replacement content and portions of the original byte stream and identifying a second set of content similarities resulting from the comparison; and

means for generating the difference file by encoding information of the first set and second set of content similarities.

3. The apparatus of claim 2, further comprising means for transferring the difference file to a remote system that hosts a copy of the original file, the remote system updating the hosted copy of the original file using the difference file.

4. A method for generating difference files, comprising:

receiving an original byte stream that is a segment of an original file and a new byte stream that is a segment of a new file, wherein the new file includes an updated version of the original file;

identifying replacement content of the new byte stream, wherein replacement content includes a group of bytes of the new byte stream identified as at least one of byte insertions and byte replacements in an operation array;

comparing the replacement content and portions of the new byte stream and identifying a first set of content similarities resulting from the comparison;

comparing the replacement content and portions of the original byte stream and identifying a second set of content similarities resulting from the comparison; and

generating the difference file by encoding information of the first set and second set of content similarities.

5. The method of claim 4, wherein comparing the replacement content with portions of the new byte stream further includes:

identifying at least one first largest common sub-string (LCS) of bytes in response to the comparison; and

identifying the first set of content similarities between the replacement content and the new byte stream using the first LCS.

6. The method of claim 4, wherein comparing the replacement content with portions of the original byte stream further includes:

identifying at least one second LCS in response to the comparison; and

identifying the second set of content similarities between the replacement content and the original byte stream using the second LCS.

7. The method of claim 4, further comprising:

encoding a first edit distance between the replacement content and portions of the new byte stream; and

encoding a second edit distance between the replacement content and portions of the original byte stream.

8. The method of claim 7, wherein generating the difference file further includes comparing information including at least one of a number of bytes used to encode the first edit distance, a number of bytes used to encode the second edit distance, a number of bytes of the replacement content, and a degree of content similarity.

9. The method of claim 4, wherein generating the difference file by encoding information of the first set of content similarities further comprises:

encoding a first edit distance between the replacement content and portions of the new byte stream and encoding a second edit distance between the replacement content and portions of the original byte stream;

comparing a number of bytes used to encode the first edit distance to a number of bytes used to encode the second edit distance;

comparing the number of bytes used to encode the first edit distance to a length of the replacement content and a degree of content similarity; and

encoding information of the first set of content similarities when the number of bytes used to encode the first edit distance is less than or equal to the number of bytes used to encode the second edit distance and a quantity formed by dividing the number of bytes used to encode the first edit distance by the length of the replacement content is less than the degree of content similarity.

10. The method of claim 4, wherein generating the difference file by encoding information of the second set of content similarities further comprises:

encoding a first edit distance between the replacement content and portions of the new byte stream and encoding a second edit distance between the replacement content and portions of the original byte stream;

comparing a number of bytes used to encode the second edit distance to a number of bytes used to encode the first edit distance;

comparing the number of bytes used to encode the second edit distance to a length of the replacement content and a degree of content similarity; and

encoding information of the second set of content similarities when the number of bytes used to encode the second edit distance is less than or equal to the number of bytes used to encode the first edit distance and a quantity formed by dividing the number of bytes used to encode the second edit distance by the length of the replacement content is less than the degree of content similarity.

11. A system for updating electronic files of remote devices, comprising:

a first device including a file differencing engine that generates differences between an original version and a new version of an electronic file by;

receiving an original byte stream that is a segment of the original version and a new byte stream that is a segment of the new version;

identifying replacement content of the new byte stream, wherein replacement content includes a group of bytes of the new byte stream identified as at least one of byte insertions and byte replacements in an operation array;

comparing the replacement content and portions of the new byte stream and identifying a first set of content similarities resulting from the comparison;

comparing the replacement content and portions of the original byte stream and identifying a second set of content similarities resulting from the comparison;

generating a difference file including encoded information of the first set and second set of content similarities; and

a file updating engine hosted on the remote devices, the file updating engine generating a copy of the new version using the difference file.

12. The system of claim 11, wherein the remote device includes at least one of cellular telephones, portable communication devices, personal digital assistants, personal computers, and portable processor-based devices.

13. A computer readable medium including executable instructions which, when executed in a processing system, reduce a size of a difference file that includes coded differences between an original version and a new version of an electronic file by:

identifying replacement content of a new byte stream that is a segment of the new version, wherein replacement content includes a group of bytes of the new byte stream identified as at least one of byte insertions and byte replacements in an operation array;

comparing the replacement content and portions of the new byte stream and identifying a first set of content similarities resulting from the comparison;

comparing the replacement content and portions of an original byte stream and identifying a second set of content similarities resulting from the comparison, wherein the original byte stream is a segment of the original version; and

generating the difference file by encoding information of the first set and second set of content similarities.