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 $Σ$ of size $σ$ online in the following sense: it reads $W$ starting from the left, and, after reading each $r = O(\log_σ n)$ characters of $W$, updates the Lempel-Ziv factorization. The algorithm requires $O(n \log σ)$ bits of space and O(n \log^2 n) time. The basis of the algorithm is a sparse suffix tree combined with wavelet trees.

No reviews yet.

No comments yet.