2026-07-24T00:45:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16440 2024-03-06T10:57:29Z ddc:004 open_access

An Optimal-Time RLBWT Construction in BWT-Runs Bounded Space Nishimoto, Takaaki Kanda, Shunsuke Tabei, Yasuo lossless data compression Burrows-Wheeler transform highly repetitive text collections The compression of highly repetitive strings (i.e., strings with many repetitions) has been a central research topic in string processing, and quite a few compression methods for these strings have been proposed thus far. Among them, an efficient compression format gathering increasing attention is the run-length Burrows-Wheeler transform (RLBWT), which is a run-length encoded BWT as a reversible permutation of an input string on the lexicographical order of suffixes. State-of-the-art construction algorithms of RLBWT have a serious issue with respect to (i) non-optimal computation time or (ii) a working space that is linearly proportional to the length of an input string. In this paper, we present r-comp, the first optimal-time construction algorithm of RLBWT in BWT-runs bounded space. That is, the computational complexity of r-comp is O(n + r log r) time and O(r log n) bits of working space for the length n of an input string and the number r of equal-letter runs in BWT. The computation time is optimal (i.e., O(n)) for strings with the property r = O(n/log n), which holds for most highly repetitive strings. Experiments using a real-world dataset of highly repetitive strings show the effectiveness of r-comp with respect to computation time and space. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Takaaki Nishimoto and Shunsuke Kanda and Yasuo Tabei 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.99 urn:nbn:de:0030-drops-164403 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.99 eng https://creativecommons.org/licenses/by/4.0/legalcode