A four-stage algorithm for updating a Burrows-Wheeler transform

DOI10.1016/j.tcs.2009.07.016zbMath1187.68685WikidataQ55951225 ScholiaQ55951225MaRDI QIDQ732025

Thierry Lecroq, Martine Léonard, Laurent Mouchard, Mikaël Salson

Publication date: 9 October 2009

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

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

zbMATH Keywords

dynamic; compression; Burrows-Wheeler transform; suffix array; algorithm design; edit operations; self-index data structures

Mathematics Subject Classification ID

68P10: Searching and sorting

68W05: Nonnumerical algorithms

Related Items

Unnamed Item, On the number of elements to reorder when updating a suffix array, Binary block order Rouen transform, On suffix extensions in suffix trees, Dynamic extended suffix arrays, A survey of string orderings and their application to the Burrows-Wheeler transform, Sliding suffix tree, Computing the Burrows-Wheeler transform in place and in small space, Indeterminate string factorizations and degenerate text transformations, A bijective variant of the Burrows-Wheeler transform using \(V\)-order, Contracted Suffix Trees: A Simple and Dynamic Text Indexing Data Structure

Cites Work

• Unnamed Item
• A note on the Burrows-Wheeler transformation
• Fast BWT in small space by blockwise suffix sorting
• Compressed representations of sequences and full-text indexes
• Dynamic entropy-compressed sequences and full-text indexes
• Improved Dynamic Rank-Select Entropy-Bound Structures