2026-07-22T06:36:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8702 2024-03-12T11:57:57Z ddc:004 open_access

Online LZ77 Parsing and Matching Statistics with RLBWTs Bannai, Hideo Gagie, Travis I, Tomohiro Lempel-Ziv 1977 Matching Statistics Run-Length Compressed Burrows-Wheeler Transform Lempel-Ziv 1977 (LZ77) parsing, matching statistics and the Burrows-Wheeler Transform (BWT) are all fundamental elements of stringology. In a series of recent papers, Policriti and Prezza (DCC 2016 and Algorithmica, CPM 2017) showed how we can use an augmented run-length compressed BWT (RLBWT) of the reverse T^R of a text T, to compute offline the LZ77 parse of T in O(n log r) time and O(r) space, where n is the length of T and r is the number of runs in the BWT of T^R. In this paper we first extend a well-known technique for updating an unaugmented RLBWT when a character is prepended to a text, to work with Policriti and Prezza's augmented RLBWT. This immediately implies that we can build online the LZ77 parse of T while still using O(n log r) time and O(r) space; it also seems likely to be of independent interest. Our experiments, using an extension of Ohno, Takabatake, I and Sakamoto's (IWOCA 2017) implementation of updating, show our approach is both time- and space-efficient for repetitive strings. We then show how to augment the RLBWT further - albeit making it static again and increasing its space by a factor proportional to the size of the alphabet - such that later, given another string S and O(log log n)-time random access to T, we can compute the matching statistics of S with respect to T in O(|S| log log n) time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hideo Bannai and Travis Gagie and Tomohiro I 2018 Is Part Of LIPIcs, Volume 105, 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2018.7 urn:nbn:de:0030-drops-87025 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2018.7 eng https://creativecommons.org/licenses/by/3.0/legalcode