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

Lightweight algorithms for constructing and inverting the BWT of string collections, Space-efficient construction of Lempel-Ziv compressed text indexes, A four-stage algorithm for updating a Burrows-Wheeler transform, Computing the Burrows-Wheeler transform in place and in small space, 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