Computing Lempel-Ziv Factorization Online

We present an algorithm which computes the Lempel-Ziv factorization of a word $W$ of length $n$ on an alphabet $\mathrm{\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.