Space efficient algorithms for the Burrows-Wheeler backtransformation

DOI10.1007/S00453-008-9269-9MaRDI QIDQ5961973zbMATHOpenAlexFDO

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

data compressionBurrows-Wheeler transformation

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 1047152 (Why is no real title available?)
• scientific article; zbMATH DE number 6472611 (Why is no real title available?)
• 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
• Suffix Arrays: A New Method for On-Line String Searches
• Universal data compression based on the Burrows-Wheeler transformation: theory and practice

Cited in

(4)

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

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)