Fast online Lempel-Ziv factorization in compressed space


© Springer International Publishing Switzerland 2015.Let T be a text of length n on an alphabet Σ of size σ, and let H0 be the zero-order empirical entropy of T. We show that the LZ77 factorization of T can be computed in nH0 +o(n log σ)+ (image found) (σ log n) bits of working space with an online algorithm running in (image found) (n log n) time. Previous space-efficient online solutions either work in compact space and (image found) (n log n) time, or in succinct space and (image found) (n log3 n) time.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)