Space efficient algorithms for the Burrows-Wheeler backtransformation

DOI10.1007/S00453-008-9269-9MaRDI QIDQ5961973zbMATH OpenOpenAlexFDO

Authors Ulrich Lauther, Tamás Lukovszki

Publication date 16 September 2010

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.65.3603

zbMATH Keywords

Burrows-Wheeler transformationdata compression

Mathematics Subject Classification ID

Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Source coding (94A29)

Recommendations

• Algorithms – ESA 2005
• scientific article; zbMATH DE number 1421005
• Average linear time and compressed space construction of the Burrows-Wheeler transform
• Computing the Burrows-Wheeler transform in place and in small space
• Fast BWT in small space by blockwise suffix sorting

Cites work

• An analysis of the Burrows-Wheeler transform
• An experimental study of an opportunistic index
• Combinatorial Pattern Matching
• Compressed representations of sequences and full-text indexes
• Compression boosting in optimal linear time using the Burrows-Wheeler transform
• Engineering a lightweight suffix array construction algorithm
• Fast lightweight suffix array construction and checking
• Faster suffix sorting
• scientific article; zbMATH DE number 1047152 (Why is no real title available?)
• scientific article; zbMATH DE number 6472611 (Why is no real title available?)
• Suffix Arrays: A New Method for On-Line String Searches
• Universal data compression based on the Burrows-Wheeler transformation: theory and practice

Cited in

(5)

• Computing the Burrows-Wheeler transform in place and in small space
• scientific article; zbMATH DE number 1421005 (Why is no real title available?)
• Local decodability of the Burrows-Wheeler transform
• Algorithms – ESA 2005
• Optimal-time queries on BWT-runs compressed indexes

Describes a project that uses

Uses Software

• Canterbury

This page was built for publication: Space efficient algorithms for the Burrows-Wheeler backtransformation

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