LZ78 Compression in Low Main Memory Space - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2017

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.
Fichier principal
Vignette du fichier
Canovas-spire-2017.pdf (342.05 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-01951607 , version 1 (11-12-2018)

Identifiers

Cite

Diego Arroyuelo, Rodrigo Cánovas, Gonzalo Navarro, Rajeev Raman. LZ78 Compression in Low Main Memory Space. SPIRE: String Processing and Information Retrieval, Sep 2017, Palermo, Italy. pp.38-50, ⟨10.1007/978-3-319-67428-5_4⟩. ⟨lirmm-01951607⟩
88 View
274 Download

Altmetric

Share

Gmail Facebook X LinkedIn More