Method for finding the longest common subsequences between files with applications to differential compression

摘要

A differential compression method and computer program product combines hash value techniques and suffix array techniques. The invention finds the best matches for every offset of the version file, with respect to a certain granularity and above a certain length threshold. The invention has two variations depending on block size choice. If the block size is kept fixed, the compression performance of the invention is similar to that of the greedy algorithm, without the expensive space and time requirements. If the block size is varied linearly with the reference file size, the invention can run in linear-time and constant-space. It has been shown empirically that the invention performs better than certain known differential compression algorithms in terms of compression and speed.