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.
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01951607
Contributor : Eric Rivals <>
Submitted on : Tuesday, December 11, 2018 - 3:16:15 PM
Last modification on : Friday, March 15, 2019 - 1:15:14 AM
Long-term archiving on : Tuesday, March 12, 2019 - 3:01:11 PM

File

Canovas-spire-2017.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

86

Files downloads

73