Name
Abstract | ||
|---|---|---|
Run-length encoded 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(nlgr) time and O(rlgn) 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. Enlisting the proposed online RLBWT, we can efficiently compute the LZ77 factorization in run-compressed space. The empirical results show the efficiencies of both our online RLBWT and LZ77 parsing, especially for highly repetitive strings. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.jda.2018.11.002 | Journal of Discrete Algorithms |
Keywords | Field | DocType |
Run-length Burrows–Wheeler transformation,LZ77 factorization,Recompression | Discrete mathematics,Algorithm,Wavelet Tree,Factorization,Parsing,Mathematics | Journal |
Volume | ISSN | Citations |
52-53 | 1570-8667 | 0 |
PageRank | References | Authors |
0.34 | 14 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tatsuya Ohno | 1 | 1 | 1.04 |
| Kensuke Sakai | 2 | 0 | 0.34 |
| Yoshimasa Takabatake | 3 | 29 | 7.27 |
| Tomohiro I | 4 | 148 | 22.06 |
| Hiroshi Sakamoto | 5 | 47 | 6.63 |