Simple and fast decoding is one of the main advantages of the 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 the fastest available options in practice for decoding texts that exceed the amount of available RAM.

Simon J. Puglisi is Academy of Finland Fellow in the Department of Computer Science at the University of Helsinki. Prior to that he held a Newton Fellowship at King's College London, and earlier still an Australian Postdoctoral Fellowship at Royal Melbourne Institute of Technology where he was a member of the Search Engine Group. He obtained his PhD in December 2007 from Curtin University, Western Australia. His current research focuses on efficient algorithms and data structures for searching and manipulating large strings, trees, and graphs, and applications in bioinformatics, information retrieval, and data mining. Frequent themes are the interplay between search and compression, and the boundary of theory and practice. He is the author of over 80 peer-reviewed articles, and served as PC chair of the 2015 Symposium on String Processing and Information Retrieval.