DSApr 15
Merging RLBWTs adaptively
arXiv:2511.1695336.51 citationsh-index: 1
Predicted impact top 34% in DS · last 90 daysOriginality Synthesis-oriented
AI Analysis
This provides a more space-efficient method for merging compressed string indexes, benefiting bioinformatics and text processing applications.
The paper presents an algorithm to merge two RLBWTs into an eBWT in O(r) space and O((r+L) log(m+n)) time, improving on previous methods that required O(m+n) space.
We show how to merge two run-length compressed Burrows-Wheeler Transforms (RLBWTs) into a run-length compressed extended Burrows-Wheeler Transform (eBWT) in $O (r)$ space and $O ((r + L) \log (m + n))$ time, where $m$ and $n$ are the lengths of the uncompressed strings, $r$ is the number of runs in the final eBWT and $L$ is the sum of its irreducible LCP values.