  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.
