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

DOI10.1016/J.JDA.2015.01.004MaRDI QIDQ2343299zbMATH OpenOpenAlexWikidataFDO

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

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

Burrows-Wheeler transformin-place algorithmsstring algorithmssuffix sorting

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1421005
• Parallel computation of the Burrows Wheeler transform in compact space
• Algorithms – ESA 2005
• Space efficient algorithms for the Burrows-Wheeler backtransformation
• A constant-space comparison-based algorithm for computing the Burrows-Wheeler transform
• In-place bijective burrows-wheeler transforms
• Space-efficient computation of the LCP array from the Burrows-Wheeler transform
• A note on the Burrows-Wheeler transformation
• Nearly tight bounds on the encoding length of the Burrows-Wheeler transform

Cites work

• A constant-space comparison-based algorithm for computing the Burrows-Wheeler transform
• A four-stage algorithm for updating a Burrows-Wheeler transform
• A space and time efficient algorithm for constructing compressed suffix arrays
• Alphabet-independent linear-time construction of compressed suffix arrays using \(o(n \log n)\)-bit working space
• An analysis of the Burrows-Wheeler transform
• Breaking a time-and-space barrier in constructing full-text indices
• Comparison-based time-space lower bounds for selection
• Fast BWT in small space by blockwise suffix sorting
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• scientific article; zbMATH DE number 1383709 (Why is no real title available?)
• In-Place Suffix Sorting
• Indexing compressed text
• Linear time construction of compressed text indices in compact space
• Optimal Time Minimal Space Selection Algorithms
• Selection from read-only memory and sorting with minimum data movement
• Suffix Arrays: A New Method for On-Line String Searches
• Wavelet trees for all

Cited in

(18)

• A survey of string orderings and their application to the Burrows-Wheeler transform
• When a dollar makes a BWT
• Parallel computation of the Burrows Wheeler transform in compact space
• Faster average case low memory semi-external construction of the Burrows-Wheeler transform
• Computing the Burrows-Wheeler transform of a string and its reverse in parallel
• Fast BWT in small space by blockwise suffix sorting
• Can Burrows-Wheeler transform be replaced in chain code compression?
• Computing the BWT and the LCP array in constant space
• Average linear time and compressed space construction of the Burrows-Wheeler transform
• Computing the Burrows-Wheeler Transform of a String and Its Reverse
• Computing the inverse sort transform in linear time
• A constant-space comparison-based algorithm for computing the Burrows-Wheeler transform
• scientific article; zbMATH DE number 1421005 (Why is no real title available?)
• Burrows-Wheeler transform and LCP array construction in constant space
• Algorithms – ESA 2005
• Space efficient algorithms for the Burrows-Wheeler backtransformation
• On arithmetically progressed suffix arrays and related Burrows-Wheeler transforms
• A four-stage algorithm for updating a Burrows-Wheeler transform

Describes a project that uses

Uses Software

• BWA
• Find

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2343299)