Istituto di Scienza e Tecnologie dell'Informazione     
Farruggia A., Ferragina P., Venturini R. Bicriteria data compression: efficient and usable. In: ESA 2014 - Algorithms. 22th Annual European Symposium (Wroclaw, Poland, 8-10 September 2014). Proceedings, pp. 406 - 417. Andreas S. Schulz, Dorothea Wagner (eds.). (Lecture Notes in Computer Science, vol. 8737). Springer, 2014.
Lempel-Ziv's LZ77algorithm is the de facto choice for compressing massive datasets because its algorithmic structure is flexible enough to guarantee very fast decompression speed at reasonable compressed-space occupancy. Recent theoretical results have shown how to design a bit-optimal LZ77-compressor which minimizes the compress size and how to deploy it in order to design a bicriteria data compressor, namely an LZ77-compressor which trades compressed-space occupancy versus its decompression time in a smoothed and principled way. Preliminary experiments were promising but raised many algorithmic and engineering questions which have to be addressed in order to turn these algorithmic results into an effective and practical tool. In this paper we address these issues by first designing a novel bit-optimal LZ77-compressor which is simple, cache-aware and asymptotically optimal. We benchmark our approach by investigating several algorithmic and implementation issues over many dataset types and sizes, and against an ample class of classic (LZ-based, PPM-based and BWT-based) as well as engineered compressors. We conclude noticing how our novel bicriteria Lz77-compressor improves the state-of-the-art of fast (de)compressors snappy and LZ4.
URL: http://link.springer.com/chapter/10.1007%2F978-3-662-44777-2_34
DOI: 10.1007/978-3-662-44777-2_34
Subject Data compression

Icona documento 1) Download Document PDF
Icona documento 2) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional