Lempel-Ziv parsing in external memory
Dominik Kempa, Simon J. Puglisi · 2013
Abstract. For decades, computing the LZ factorization (or LZ77 pars-ing) of a string has been a requisite and computationally intensive step in many diverse applications, including text indexing and data compres-sion. Many algorithms for LZ77 parsing have been discovered over the years; however, despite the increasing need to apply LZ77 to massive data sets, no algorithm to date scales to inputs that exceed the size of internal memory. In this paper we describe the first algorithm for com-puting the LZ77 parsing in external memory. Our algorithm is fast in practice and will allow the next generation of text indexes to be realised for massive strings and string collections. 1