Computing the Burrows-Wheeler transform in place and in small space

DOI10.1016/j.jda.2015.01.004zbMath1328.68325OpenAlexW1994041544WikidataQ61677839 ScholiaQ61677839MaRDI QIDQ2343299

Gad M. Landau, Juha Kärkkäinen, Roberto Grossi, Maxime Crochemore

Publication date: 4 May 2015

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2015.01.004

zbMATH Keywords

string algorithmsBurrows-Wheeler transformin-place algorithmssuffix sorting

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Related Items (4)

Can Burrows-Wheeler transform be replaced in chain code compression? ⋮ A survey of string orderings and their application to the Burrows-Wheeler transform ⋮ When a dollar makes a BWT ⋮ Burrows-Wheeler transform and LCP array construction in constant space

Uses Software

• Find
• BWA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Selection from read-only memory and sorting with minimum data movement
• A four-stage algorithm for updating a Burrows-Wheeler transform
• A space and time efficient algorithm for constructing compressed suffix arrays
• Wavelet trees for all
• Alphabet-independent linear-time construction of compressed suffix arrays using \(o(n \log n)\)-bit working space
• Fast BWT in small space by blockwise suffix sorting
• Suffix Arrays: A New Method for On-Line String Searches
• An analysis of the Burrows—Wheeler transform
• Indexing compressed text
• Breaking a Time-and-Space Barrier in Constructing Full-Text Indices
• Optimal Time Minimal Space Selection Algorithms
• A Constant-Space Comparison-Based Algorithm for Computing the Burrows–Wheeler Transform
• Optimal Dynamic Sequence Representations
• Linear time construction of compressed text indices in compact space
• In-Place Suffix Sorting

This page was built for publication: Computing the Burrows-Wheeler transform in place and in small space