Efficient algorithm for circular Burrows-Wheeler transform

DOI10.1007/978-3-642-31265-6_21MaRDI QIDQ2904499zbMATH OpenOpenAlexFDO

Authors Wing-Kai Hon, Tsung-Han Ku, Chen-Hua Lu, Rahul Shah, Sharma V. Thankachan

Publication date 14 August 2012

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-31265-6_21

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Algorithms on strings (68W32) Analysis of algorithms (68W40)

Recommendations

• Succinct indexes for circular patterns
• Fast circular dictionary-matching algorithm
• Space-efficient construction algorithm for the circular suffix tree
• Average linear time and compressed space construction of the Burrows-Wheeler transform
• Faster average case low memory semi-external construction of the Burrows-Wheeler transform

Cited in

(17)

• r-indexing the eBWT
• Computing the original eBWT faster, simpler, and with less memory
• Lightweight merging of compressed indices based on BWT variants
• Fast circular dictionary-matching algorithm
• Succinct indexes for circular patterns
• Space-efficient construction algorithm for the circular suffix tree
• The Burrows-Wheeler transform between data compression and combinatorics on words
• Indexing Circular Patterns
• A new class of string transformations for compressed text indexing
• Constructing and indexing the bijective and extended Burrows-Wheeler transform
• r-indexing the eBWT
• Sorting circular suffixes in linear time
• Generic non-recursive suffix array construction
• The ceBWT index: an index for circular Cartesian tree matching on multiple texts
• Simple linear time algorithm for sorting strings in omega-order with applications
• Improved circular dictionary matching
• Extending the Burrows-Wheeler transform for Cartesian tree matching and constructing it

This page was built for publication: Efficient algorithm for circular Burrows-Wheeler transform

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