Computing Lempel-Ziv Factorization Online

Abstract

We present an algorithm which computes the Lempel-Ziv factorization of a word $W$ of length $n$ on an alphabet $\Sigma$ of size $\sigma$ online in the following sense: it reads $W$ starting from the left, and, after reading each $r=O({\log }_{\sigma }n)$ characters of $W$, updates the Lempel-Ziv factorization. The algorithm requires $O(n\log \sigma )$ bits of space and O(n \log^2 n) time. The basis of the algorithm is a sparse suffix tree combined with wavelet trees.

References in corpus (1)

• Light Spanner and Monotone Tree

Cited by in corpus (2)

• Efficient Large-Scale Graph Processing on Hybrid CPU and GPU Systems
• Good-for-games $\omega$-Pushdown Automata