LZ78 Compression in Low Main Memory Space

Abstract : We present the first algorithms that perform the LZ78 compression of a text of length n over alphabet [1..σ], whose output is z integers, using only O(z lg σ) bits of main memory. The algorithms read the input text from disk in a single pass, and write the compressed output to disk. The text can also be decompressed within the same main memory usage, which is unprecedented too. The algorithms are based on hashing and, under some simplifying assumptions, run in O(n) expected time. We experimentally verify that our algorithms use 2-9 times less time and/or space than previously implemented LZ78 compressors.
Type de document :
Communication dans un congrès
Gabriele Fici; Marinella Sciortino; Rossano Venturini. SPIRE: String Processing and Information Retrieval, Sep 2017, Palermo, Italy. Springer Verlag, 24th International Symposium on String Processing and Information Retrieval, LNCS (10508), pp.38-50, 2017, String Processing and Information Retrieval. 〈10.1007/978-3-319-67428-5_4〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01951607
Contributeur : Eric Rivals <>
Soumis le : mardi 11 décembre 2018 - 15:16:15
Dernière modification le : lundi 17 décembre 2018 - 01:19:28

Fichier

Canovas-spire-2017.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Diego Arroyuelo, Rodrigo Cánovas, Gonzalo Navarro, Rajeev Raman. LZ78 Compression in Low Main Memory Space. Gabriele Fici; Marinella Sciortino; Rossano Venturini. SPIRE: String Processing and Information Retrieval, Sep 2017, Palermo, Italy. Springer Verlag, 24th International Symposium on String Processing and Information Retrieval, LNCS (10508), pp.38-50, 2017, String Processing and Information Retrieval. 〈10.1007/978-3-319-67428-5_4〉. 〈lirmm-01951607〉

Partager

Métriques

Consultations de la notice

25

Téléchargements de fichiers

12