2026-10-12T09:35:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23915 2026-02-09T05:23:55Z ddc:004 open_access

Algorithms for Computing Very Large BWTs: a Short Survey Díaz-Domínguez, Diego Egidi, Lavinia Guerrini, Veronica Louza, Felipe A. Rosone, Giovanna Burrows-Wheeler transform Extended Burrows-Wheeler transform external memory text compression longest common prefix The Burrows-Wheeler Transform (BWT) is a fundamental string transformation that, although initially introduced for data compression, has been extensively utilized across various domains, including text indexing and pattern matching within large datasets. Although the BWT construction is linear, the constants make the task impractical for large datasets, and as highlighted by Ferragina et al. [Paolo Ferragina et al., 2012], "to use it, one must first build it!". Thus, the construction of the BWT remains a significant challenge. For these reasons, during the past three decades there has been a succession of new algorithms for its construction using techniques that work in external memory or that use text compression. In this survey, we revise some of the most important advancements and tools presented in the past years for computing large BWTs exploiting external memory or text compression approaches without using additional information about the data. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Diego Díaz-Domínguez and Lavinia Egidi and Veronica Guerrini and Felipe A. Louza and Giovanna Rosone 2025 Is Part Of OASIcs, Volume 131, The Expanding World of Compressed Data: A Festschrift for Giovanni Manzini's 60th Birthday (2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.Manzini.7 urn:nbn:de:0030-drops-239151 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Manzini.7 eng https://creativecommons.org/licenses/by/4.0/legalcode