Fast BWT in small space by blockwise suffix sorting

DOI10.1016/j.tcs.2007.07.018zbMath1144.68021MaRDI QIDQ2465056

Juha Kärkkäinen

Publication date: 19 December 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.07.018

zbMATH Keywords

Burrows-Wheeler transform; suffix array; space-efficient algorithms; suffix sorting

Mathematics Subject Classification ID

68P10: Searching and sorting

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

Related Items

Parallel suffix sorting for large string analytics, Lightweight algorithms for constructing and inverting the BWT of string collections, Binary block order Rouen transform, Space-efficient construction of Lempel-Ziv compressed text indexes, A four-stage algorithm for updating a Burrows-Wheeler transform, Space-efficient construction of compressed suffix trees, Parallel computation of the Burrows Wheeler transform in compact space, Computing the Burrows-Wheeler transform in place and in small space, Engineering a lightweight external memory suffix array construction algorithm, Lightweight data indexing and compression in external memory, A bijective variant of the Burrows-Wheeler transform using \(V\)-order, Faster semi-external suffix sorting, Efficient Construction of a Compressed de Bruijn Graph for Pan-Genome Analysis, Arithmetics on Suffix Arrays of Fibonacci Words, Permuted Longest-Common-Prefix Array

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Shift-or string matching with super-alphabets
• Autocorrelation on words and its applications. Analysis of suffix trees by string-ruler approach
• Engineering a lightweight suffix array construction algorithm
• Constructing suffix arrays in linear time
• Space efficient linear time construction of suffix arrays
• Compressed representations of sequences and full-text indexes
• Suffix Arrays: A New Method for On-Line String Searches
• An analysis of the Burrows—Wheeler transform
• Linear work suffix array construction
• Indexing compressed text
• Fast Lightweight Suffix Array Construction and Checking
• Breaking a Time-and-Space Barrier in Constructing Full-Text Indices
• Algorithms and Computation
• Better external memory suffix array construction
• Combinatorial Pattern Matching
• A theoretical and experimental study on the construction of suffix arrays in external memory