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

DOI10.1016/j.tcs.2009.07.016zbMath1187.68685OpenAlexW2165517897WikidataQ55951225 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

dynamiccompressionBurrows-Wheeler transformsuffix arrayalgorithm designedit operationsself-index data structures

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05)

Related Items

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

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