1 Introduction
For over three decades the Lempel-Ziv (LZ77) factorization [18] has been a fundamental tool for data compression and today it lies at the heart of popular file compressors (e.g. gzip and γzip), and information retrieval systems (see, e.g., [1]).