A note on the Burrows-Wheeler transformation

DOI10.1016/j.tcs.2004.11.014zbMath1070.68126WikidataQ61677938 ScholiaQ61677938MaRDI QIDQ1770410

Désarménien, Jacques, Maxime Crochemore, Dominique Perrin

Publication date: 6 April 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.11.014

zbMATH Keywords

Combinatorics on words; Text compression

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

Generic Algorithms for Factoring Strings, The Burrows-Wheeler Transform between Data Compression and Combinatorics on Words, A linear partitioning algorithm for hybrid Lyndons using \(V\)-order, A bijection between words and multisets of necklaces, A quick tour on suffix arrays and compressed suffix arrays, Burrows-Wheeler transformations and de Bruijn words, A four-stage algorithm for updating a Burrows-Wheeler transform, Counting suffix arrays and strings, An extension of the Burrows-Wheeler transform, A new combinatorial approach to sequence comparison, Two Combinatorial Criteria for BWT Images, String Comparison and Lyndon-Like Factorization Using V-Order in Linear Time, Sturmian and Episturmian Words

Cites Work

• Unnamed Item
• Unnamed Item
• Burrows-Wheeler transform and Sturmian words
• Counting permutations with given cycle structure and descent set
• An analysis of the Burrows—Wheeler transform
• Linear-Time Construction of Suffix Arrays
• Space Efficient Linear Time Construction of Suffix Arrays
• Words over an ordered alphabet and suffix permutations
• Mathematical Foundations of Computer Science 2003