• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Глава

Computing Lempel-Ziv Factorization Online

P. 789-799.
Starikovskaya T.

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.

В книге

Под науч. редакцией: B. Rovan, V. Sassone, P. Widmayer. Vol. 7464: Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science. Berlin: Springer, 2012.