Efficient construction of the BWT for repetitive text using string compression

DOI10.1016/j.ic.2023.105088arXiv2204.05969MaRDI QIDQ6077847

Gonzalo Navarro, Diego Díaz-Domínguez

Publication date: 27 September 2023

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2204.05969

zbMATH Keywords

BWTstring compressionrepetitive text

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Constructing and indexing the bijective and extended Burrows-Wheeler transform

Cites Work

• Unnamed Item
• Unnamed Item
• Lightweight algorithms for constructing and inverting the BWT of string collections
• Inducing enhanced suffix arrays for string collections
• Wheeler graphs: a framework for BWT-based data structures
• Computing the multi-string BWT and LCP array in external memory
• Computing the original eBWT faster, simpler, and with less memory
• Space efficient linear time construction of suffix arrays
• Suffix Arrays: A New Method for On-Line String Searches
• Efficient randomized pattern-matching algorithms
• Grammar-based codes: a new class of universal lossless source codes
• Prefix-Free Parsing for Building Big BWTs
• Fully Functional Suffix Trees and Optimal Text Searching in BWT-Runs Bounded Space
• String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure
• Engineering External Memory Induced Suffix Sorting
• Practical Entropy-Compressed Rank/Select Dictionary
• Optimal Construction of Compressed Indexes for Highly Repetitive Texts

This page was built for publication: Efficient construction of the BWT for repetitive text using string compression