Data compression with restricted parsings

Abstract

We consider a class of algorithms related to Lempel-Ziv that incorporate restrictions on the manner in which the data can be parsed with the goal of introducing new tradeoffs between implementation complexity and data compression ratios. Our main motivation lies within the field of compressed memory computer systems. Here requirements include extremely fast decompression and compression speeds, adequate compression performance on small data block lengths, and minimal hardware area and energy requirements. We describe the approach and provide experimental data concerning its compression performance with respect to known alternatives. We show that for a variety of data sets stored in a typical main memory, this direction yields results close to those of earlier techniques, but with significantly lower energy consumption at comparable or better area requirements. The technique thus may be of eventual interest for a number of applications requiring high compression bandwidths and efficient hardware implementation.