
arXiv: 1902.05224
Converting a compressed format of a string into another compressed format without an explicit decompression is one of the central research topics in string processing. We discuss the problem of converting the run-length Burrows-Wheeler Transform (RLBWT) of a string to Lempel-Ziv 77 (LZ77) phrases of the reversed string. The first results with Policriti and Prezza's conversion algorithm [Algorithmica 2018] were $O(n \log r)$ time and $O(r)$ working space for length of the string $n$, number of runs $r$ in the RLBWT, and number of LZ77 phrases $z$. Recent results with Kempa's conversion algorithm [SODA 2019] are $O(n / \log n + r \log^{9} n + z \log^{9} n)$ time and $O(n / \log_�� n + r \log^{8} n)$ working space for the alphabet size $��$ of the RLBWT. In this paper, we present a new conversion algorithm by improving Policriti and Prezza's conversion algorithm where dynamic data structures for general purpose are used. We argue that these dynamic data structures can be replaced and present new data structures for faster conversion. The time and working space of our conversion algorithm with new data structures are $O(n \min \{ \log \log n, \sqrt{\frac{\log r}{\log\log r}} \})$ and $O(r)$, respectively.
FOS: Computer and information sciences, Lempel-Ziv Parsing, Lossless Data Compression, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Burrows-Wheeler Transform, 004, ddc: ddc:004
FOS: Computer and information sciences, Lempel-Ziv Parsing, Lossless Data Compression, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Burrows-Wheeler Transform, 004, ddc: ddc:004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
