On Compactly Encoding With Differential Compression
Fouad B. Chedid, Pauline Mouawad · IEEE International Conference on Computer Systems and Applications, 2006. · 2006
In 2002, Ajtai et al. described a number of differential compression heuristics that run in linear time and constant space, and give good compression. In this paper, we experiment with two variations of the ideas proposed by Ajtai. In one variation, termed the l-List algorithm, which runs in linear time in practice and uses constant space,compressionwasimprovedbyasmuchas17.2%using files of size 100KB. In another variation, termed the k-Fitalgorithm, which introducesnoadditional overhead neither in time nor space, compression was improved by as much as 63.2%,using files of size about260KB.A useful connection between those heuristics and early algorithmsdeveloped originally for Bin Packing is also made.