Modeling delta encoding of compressed files

Summary form only given. We introduce a new model of differencing encoding, that of compressed differencing. Given two files for which at least one is in compressed form, the goal is to create a third file which is the delta file of the two original files, in time proportional to the size of the input, that is, without decompressing the compressed files. We also present an optimal algorithm in terms of processing time for constructing the delta encoding when both files are compressed using LZW. To improve the compression performance of the delta file, we check whether successive ordered pairs refer to successive substrings and can thus be combined