We propose a faster algorithm for run-length BWT (RLBWT) in run-compressed space. We improve the state-of-the-art algorithm for RLBWT in terms of empirical construction time. Adopting the dynamic list for maintaining a total order, we can replace rank queries in a dynamic wavelet tree on a run-length compressed string by the direct comparison of labels in a dynamic list. The empirical result for various benchmarks show the efficiency of our algorithm, especially for highly repetitive strings. As an important consequence, we obtain a faster algorithm for LZ77 factorization, retaining the optimal $O(r\lg n)$ bits of working space and $O(n\lg r)$ construction time for the length $n$ of input string $S$ received so far and the number $r$ of runs in BWT of the reversed $S$.

plus-circle Add Review

comment

Reviews