Data Compression Conference (DCC '04)
In-Place Differential File Compression of Non-Aligned Files With Applications to File Distribution, Backups, and String Similarity
Snowbird, Utah
March 23-March 25
ISBN: 0-7695-2082-0
We consider in-place differential file compression; that is, compressing a file T of size n with respect to an existing file S of size m, where decompression is in-place by overwriting S with T, using at most MAX(m,n)+O(1) space. In previous work we presented the IPSW algorithm (In-Place Sliding Window). IPSW is fast and the compression achieved compares well with other existing methods, including those that are not in-place. IPSW is most effective when S and T are reasonably well aligned (most large common substrings occur in approximately the same order). Here we present a preprocessing step for string alignment that can be employed when the encoder determines significant gains will be achieved.
Citation:
Dana Shapira, James A. Storer, "In-Place Differential File Compression of Non-Aligned Files With Applications to File Distribution, Backups, and String Similarity," dcc, pp.82, Data Compression Conference (DCC '04), 2004