SYSTEM AND METHOD FOR DIFFERENTIAL COMPRESSION OF DATA FROM A PLURALITY OF BINARY SOURCES

• US 20020010702A1
• Filed: 02/03/1997
• Published: 01/24/2002
• Est. Priority Date: 02/03/1997
• Status: Active Grant

• Current Assignee: Twitter Inc (X Holdings Corp.)
• Original Assignee: International Business Machines Corporation
• Inventors: FAGIN, RONALD, AJTAI, MIKLOS, BURNS, RANDAL C., STOCKMEYER, LARRY J.
• Granted Patent: US 6,374,250 B2
• Time in Patent Office: Days
• US Class Current: 707/101
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method and a system are presented for generating differentially compressed output from binary sources. Given two versions of the same file as input streams, a compact encoding of one of the input streams is generated, by representing it as a set of changes with respect to the other input stream. Algorithms for differencing files requiring time linear in the size of the input and a constant amount of space for execution are presented. In addition, advanced techniques for improving existing differencing algorithms are developed and applied to previous methods. These techniques allow algorithms to increase their efficiency without a loss of compression and to accept arbitrarily large inputs without sacrificing correctness or degrading the compression data rate. The differential compression methods provide a computationally efficient compression technique for applications that generate versioned data.

Claims

1. A method for handling first and second versions of a data object for storage and transmission, the method comprising the steps of:

performing a consecutive linear pass over both versions;

identifying a first matching byte-level string, occurring in the second version, which matches a string in the first version; and

producing a set containing (i) identified matching segments and, (ii) for each of the identified matching segments, an offset reflecting the relative positions of the matching segments within the first and second versions;

whereby, for versions whose matching strings are both local and sequential, the set closely approximates a set produced by a method of scanning the entire second version to find a best possible match with a string in the first version.