Paper Info
Title
Conversion from RLBWT to LZ77.
Abstract
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 Prezzau0027s 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 Kempau0027s conversion algorithm [SODA 2019] are $O(n / log n + r log^{9} n + z log^{9} n)$ time and $O(n / log_{sigma} n + r log^{8} n)$ working space for the alphabet size $sigma$ of the RLBWT. In this paper, we present a new conversion algorithm by improving Policriti and Prezzau0027s 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}{loglog r}} })$ and $O(r)$, respectively.
Year
Venue
Field
2019
Combinatorial Pattern Matching
Binary logarithm,Discrete mathematics,Data structure,Combinatorics,General purpose,Working space,String processing,Sigma,Dynamic data structures,Mathematics,Alphabet
DocType
Volume
Citations 
Journal
abs/1902.05224
0
PageRank 
References 
Authors
0.34
13
2
Name
Order
Citations
PageRank
Takaaki Nishimoto1233.54
Yasuo Tabei221519.46