Linking BWT and XBW via Aho-Corasick automaton: applications to run-length encoding

DOI10.4230/LIPICS.CPM.2019.24MaRDI QIDQ5088915zbMATH OpenFDO

Authors Bastien Cazaux, Eric Rivals

Publication date 18 July 2022

Full work available at URL https://arxiv.org/abs/1805.10070

zbMATH Keywords

Aho-Corasick treealgorithmcompressiondata structureRLE

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• XBWT tricks
• Average linear time and compressed space construction of the Burrows-Wheeler transform
• The alternating BWT: an algorithmic perspective
• Linear-time string indexing and analysis in small space
• Lightweight algorithms for constructing and inverting the BWT of string collections

Cites work

• Compressing and indexing labeled trees, with applications
• Lightweight algorithms for constructing and inverting the BWT of string collections
• Rank and select revisited and extended
• Relationship between superstring and compression measures: new insights on the greedy conjecture
• Run-Length Compressed Indexes Are Superior for Highly Repetitive Sequence Collections
• Storage and Retrieval of Individual Genomes
• Succinct Dictionary Matching with No Slowdown
• Suffix Arrays: A New Method for On-Line String Searches
• Wheeler graphs: a framework for BWT-based data structures
• When indexing equals compression, experiments with compressing suffix arrays and applications

Cited in

(2)

• scientific article; zbMATH DE number 7651154 (Why is no real title available?)
• A new class of string transformations for compressed text indexing

This page was built for publication: Linking BWT and XBW via Aho-Corasick automaton: applications to run-length encoding

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