Computing the inverse sort transform in linear time

DOI10.1145/1921659.1921673MaRDI QIDQ3189009zbMATH OpenOpenAlexFDO

Authors Ge Nong, Sen Zhang, W. H. Chan

Publication date 9 September 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1921659.1921673

zbMATH Keywords

Burrows-Wheeler transforminverse transformlimited order contextlinear time

Mathematics Subject Classification ID

Searching and sorting (68P10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Recommendations

• Computing Inverse ST in Linear Complexity
• Medium-Space Algorithms for Inverse BWT
• A constant-space comparison-based algorithm for computing the Burrows-Wheeler transform
• Average linear time and compressed space construction of the Burrows-Wheeler transform
• Computing the Burrows-Wheeler transform in place and in small space

Cited in

(1)

• Computing Inverse ST in Linear Complexity

This page was built for publication: Computing the inverse sort transform in linear time

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