When a dollar makes a BWT
From MaRDI portal
Publication:2220786
DOI10.1016/J.TCS.2021.01.008zbMATH Open1477.68554arXiv1908.09125OpenAlexW2969373670MaRDI QIDQ2220786FDOQ2220786
Authors: Sara Giuliani, Zsuzsanna Lipták, Francesco Masillo, Romeo Rizzi 
Publication date: 25 January 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Abstract: The Burrows-Wheeler-Transform (BWT) is a reversible string transformation which plays a central role in text compression and is fundamental in many modern bioinformatics applications. The BWT is a permutation of the characters, which is in general better compressible and allows to answer several different query types more efficiently than the original string. It is easy to see that not every string is a BWT image, and exact characterizations of BWT images are known. We investigate a related combinatorial question. In many applications, a sentinel character dollar is added to mark the end of the string, and thus the BWT of a string ending with dollar contains exactly one dollar-character. Given a string w, we ask in which positions, if any, the dollar-character can be inserted to turn w into the BWT image of a word ending with dollar. We show that this depends only on the standard permutation of w and present a O(n log n)-time algorithm for identifying all such positions, improving on the naive quadratic time algorithm. We also give a combinatorial characterization of such positions and develop bounds on their number and value. This is an extended version of [Giuliani et al. ICTCS 2019].
Full work available at URL: https://arxiv.org/abs/1908.09125
Recommendations
- Two combinatorial criteria for BWT images
- Average linear time and compressed space construction of the Burrows-Wheeler transform
- scientific article; zbMATH DE number 2051173
- The alternating BWT: an algorithmic perspective
- The Burrows-Wheeler transform between data compression and combinatorics on words
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Combinatorics on words (68R15) Algorithms on strings (68W32)
Cites Work
- Comparing DNA sequence collections by direct comparison of compressed text indexes
- Introduction to algorithms.
- An analysis of the Burrows-Wheeler transform
- Counting permutations with given cycle structure and descent set
- Combinatorics of permutations
- Self-adjusting binary search trees
- Reverse engineering prefix tables
- A note on the Burrows-Wheeler transformation
- Burrows-Wheeler transform and palindromic richness
- An extension of the Burrows-Wheeler transform
- A new combinatorial approach to sequence comparison
- Balancing and clustering of words in the Burrows-Wheeler transform
- From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization
- Reverse engineering of compact suffix trees and links: a novel algorithm
- Inferring strings from suffix trees and links on a binary alphabet
- Burrows-Wheeler transform and Sturmian words
- On the combinatorics of suffix arrays
- Mathematical Foundations of Computer Science 2003
- Counting suffix arrays and strings
- A categorization theorem on suffix arrays with applications to space efficient text indexes
- Computing the Burrows-Wheeler transform in place and in small space
- Burrows-Wheeler transform and LCP array construction in constant space
- Words with simple Burrows-Wheeler transforms
- A simpler analysis of Burrows-Wheeler-based compression
- Most Burrows-Wheeler Based Compressors Are Not Optimal
- Boosting textual compression in optimal linear time
- LZ77 computation based on the run-length encoded BWT
- Wheeler graphs: a framework for BWT-based data structures
- Clustering words and interval exchanges
- Reconstructing a string from its Lyndon arrays
- A survey of string orderings and their application to the Burrows-Wheeler transform
- The Burrows-Wheeler transform between data compression and combinatorics on words
- Sorting conjugates and suffixes of words in a multiset
- Two combinatorial criteria for BWT images
- On fixed points of the Burrows-Wheeler transform
- String inference from longest-common-prefix array
Cited In (4)
Uses Software
This page was built for publication: When a dollar makes a BWT
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2220786)
