Bicriteria data compression

Farruggia A, Frangioni A, Ferragina P, Venturini R

Data compression  Optimization  E.4 CODING AND INFORMATION THEORY 

In this paper we address the problem of trading optimally, and in a principled way, the compressed size/decompression time of LZSE{} parsings by introducing what we call the {em Bicriteria LZSE{}-Parsing problem}. The goal is to determine an LZ77 parsing which minimizes the space occupancy in bits of the compressed file, provided that the decompression time is bounded by T. Symmetrically, we can exchange the role of the two resources and thus ask for minimizing the decompression time provided that the compressed space is bounded by a fixed amount given in advance.