@inproceedings{10237f7bc4904eec8ad69919a6f7c82c,
title = "Lempel-Ziv decoding in external memory",
abstract = "Simple and fast decoding is one of the main advantages of LZ77-type text encoding used in many popular file compressors such as gzip and 7zip. With the recent introduction of external memory algorithms for Lempel-Ziv factorization there is a need for external memory LZ77 decoding but the standard algorithm makes random accesses to the text and cannot be trivially modified for external memory computation. We describe the first external memory algorithms for LZ77 decoding, prove that their I/O complexity is optimal, and demonstrate that they are very fast in practice, only about three times slower than in-memory decoding (when reading input and writing output is included in the time).",
author = "Djamal Belazzougui and Juha K{\"a}rkk{\"a}inen and Dominik Kempa and Puglisi, \{Simon J.\}",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 15th International Symposium on Experimental Algorithms, SEA 2016 ; Conference date: 05-06-2016 Through 08-06-2016",
year = "2016",
doi = "10.1007/978-3-319-38851-9\_5",
language = "English",
isbn = "9783319388502",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "63--74",
editor = "Kulikov, \{Alexander S.\} and Goldberg, \{Andrew V.\}",
booktitle = "Experimental Algorithms - 15th International Symposium, SEA 2016, Proceedings",
}