Title: A Faster Implementation of Online Run-Length Burrows-Wheeler Transform,
Abstract: Run-length encoding Burrows-Wheeler Transformed strings, resulting in
Run-Length BWT (RLBWT), is a powerful tool for processing highly repetitive
strings. We propose a new algorithm for online RLBWT working in run-compressed
space, which runs in $O(n\lg r)$ time and $O(r\lg n)$ bits of space, where $n$
is the length of input string $S$ received so far and $r$ is the number of runs
in the BWT of the reversed $S$. We improve the state-of-the-art algorithm for
online 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.