Skip to Main content Skip to Navigation
Conference papers

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 metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Eric Rivals Connect in order to contact the contributor
Submitted on : Tuesday, December 11, 2018 - 3:16:15 PM
Last modification on : Friday, August 5, 2022 - 3:02:17 PM
Long-term archiving on: : Tuesday, March 12, 2019 - 3:01:11 PM


Files produced by the author(s)




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⟩



Record views


Files downloads