The Burrows-Wheeler Transform between Data Compression and Combinatorics on Words

DOI10.1007/978-3-642-39053-1_42zbMath1370.68088MaRDI QIDQ5326383

Giovanna Rosone, Marinella Sciortino

Publication date: 5 August 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-39053-1_42

Mathematics Subject Classification ID

68R15: Combinatorics on words

68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)

Related Items

Computing the multi-string BWT and LCP array in external memory, Wheeler languages, When a dollar makes a BWT, The alternating BWT: an algorithmic perspective, An external-memory algorithm for string graph construction

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lightweight algorithms for constructing and inverting the BWT of string collections
• Balancing and clustering of words in the Burrows-Wheeler transform
• On optimally partitioning a text to improve its compression
• Burrows-Wheeler transform and Sturmian words
• Words with simple Burrows-Wheeler transforms
• Long cycles in \(abc\)-permutations
• Counting permutations with given cycle structure and descent set
• Some combinatorial properties of Sturmian words
• The Burrows-Wheeler similarity distribution between biological sequences based on Burrows-Wheeler transform
• A note on the Burrows-Wheeler transformation
• Characterisations of balanced words via orderings
• Distance measures for biological sequences: some recent approaches
• Burrows-Wheeler transform and palindromic richness
• Lightweight data indexing and compression in external memory
• A simpler analysis of Burrows-Wheeler-based compression
• An extension of the Burrows-Wheeler transform
• A new combinatorial approach to sequence comparison
• Efficient Algorithm for Circular Burrows-Wheeler Transform
• Two Combinatorial Criteria for BWT Images
• An analysis of the Burrows—Wheeler transform
• Most Burrows-Wheeler Based Compressors Are Not Optimal
• Boosting textual compression in optimal linear time
• Indexing compressed text
• Universal Entropy Estimation Via Block Sorting
• Optimal Partitions of Strings: A New Class of Burrows-Wheeler Compression Algorithms
• Fast Pattern Matching in Strings
• Universal lossless source coding with the Burrows Wheeler transform
• Comparing DNA Sequence Collections by Direct Comparison of Compressed Text Indexes
• Suffixes, Conjugates and Lyndon Words
• Combinatorial Pattern Matching
• Episturmian words and some constructions of de Luca and Rauzy