Journal Article

In Place Differential File Compression

Dana Shapira and James A. Storer

in The Computer Journal

Published on behalf of British Computer Society

Volume 48, issue 6, pages 677-691
Published in print November 2005 | ISSN: 0010-4620
Published online August 2005 | e-ISSN: 1460-2067 | DOI:
In Place Differential File Compression

Show Summary Details


We present algorithms for in-place differential file compression, where a target file T of size n is compressed with respect to a source file S of size m using no additional space in addition to the that used to replace S by T; that is, it is possible to encode using m + n + O(1) space and decode using MAX(m,n) + O(1) space (so that when decoding the source file is overwritten by the decompressed target file). From a theoretical point of view, an optimal solution (best possible compression) to this problem is known to be NP-hard, and in previous work we have presented a factor of 4 approximation (not in-place) algorithm based on a sliding window approach. Here we consider practical in-place algorithms based on sliding window compression where our focus is on decoding; that is, although in-place encoding is possible, we will allow O(m + n) space for the encoder so as to improve its speed and present very fast decoding with only MAX(m, n) + O(1) space. Although NP-hardness implies that these algorithms cannot always be optimal, the asymptotic optimality of sliding window methods along with their ability for constant-factor approximation is evidence that they should work well for this problem in practice. We introduce the IPSW algorithm (in-place sliding window) and present experiments that indicate that it compares favorably with traditional practical approaches, even those that do not decode in-place, while at the same time having low encoding complexity and extremely low decoding complexity. IPSW is most effective when S and T are reasonably well aligned (most large common substrings occur in approximately the same order). We also present a preprocessing step for string alignment that can be employed when the encoder determines significant gains will be achieved.

Journal Article.  11088 words.  Illustrated.

Subjects: Computer Science

Full text: subscription required

How to subscribe Recommend to my Librarian

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.