Computing the original eBWT faster, simpler, and with less memory

DOI10.1007/978-3-030-86692-1_11OpenAlexW3203859541MaRDI QIDQ2146134

Zsuzsanna Lipták, Massimiliano Rossi, Christina Boucher, Davide Cenzato, Marinella Sciortino

Publication date: 15 June 2022

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

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Related Items

r-indexing the eBWT, A new class of string transformations for compressed text indexing, Efficient construction of the BWT for repetitive text using string compression, Constructing and indexing the bijective and extended Burrows-Wheeler transform

Uses Software

• r-index
• Big-BWT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lightweight algorithms for constructing and inverting the BWT of string collections
• Burrows-Wheeler transform and Sturmian words
• Counting permutations with given cycle structure and descent set
• The Burrows-Wheeler similarity distribution between biological sequences based on Burrows-Wheeler transform
• Computing the multi-string BWT and LCP array in external memory
• Lightweight metagenomic classification via eBWT
• Efficient construction of a complete index for pan-genomics read alignment
• On the combinatorics of suffix arrays
• From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization
• An extension of the Burrows-Wheeler transform
• Space efficient linear time construction of suffix arrays
• Efficient Algorithm for Circular Burrows-Wheeler Transform
• Suffix Arrays: A New Method for On-Line String Searches
• Fast canonization of circular strings
• Construction of Fundamental Data Structures for Strings
• PFP Compressed Suffix Trees
• Two Efficient Algorithms for Linear Time Suffix Array Construction