The alternating BWT: an algorithmic perspective
From MaRDI portal
Publication:2297865
Abstract: The Burrows-Wheeler Transform (BWT) is a word transformation introduced in 1994 for Data Compression. It has become a fundamental tool for designing self-indexing data structures, with important applications in several area in science and engineering. The Alternating Burrows-Wheeler Transform (ABWT) is another transformation recently introduced in [Gessel et al. 2012] and studied in the field of Combinatorics on Words. It is analogous to the BWT, except that it uses an alternating lexicographical order instead of the usual one. Building on results in [Giancarlo et al. 2018], where we have shown that BWT and ABWT are part of a larger class of reversible transformations, here we provide a combinatorial and algorithmic study of the novel transform ABWT. We establish a deep analogy between BWT and ABWT by proving they are the only ones in the above mentioned class to be rank-invertible, a novel notion guaranteeing efficient invertibility. In addition, we show that the backward-search procedure can be efficiently generalized to the ABWT; this result implies that also the ABWT can be used as a basis for efficient compressed full text indices. Finally, we prove that the ABWT can be efficiently computed by using a combination of the Difference Cover suffix sorting algorithm [K"{a}rkk"{a}inen et al., 2006] with a linear time algorithm for finding the minimal cyclic rotation of a word with respect to the alternating lexicographical order.
Recommendations
- Block sorting-based transformations on words: beyond the magic BWT
- The Burrows-Wheeler transform between data compression and combinatorics on words
- Average linear time and compressed space construction of the Burrows-Wheeler transform
- Medium-Space Algorithms for Inverse BWT
- From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization
Cites work
- A bijection between words and multisets of necklaces
- A new class of searchable and provably highly compressible string transformations
- A new combinatorial approach to sequence comparison
- A note on the Burrows-Wheeler transformation
- Algorithms on Strings, Trees and Sequences
- An analysis of the Burrows-Wheeler transform
- An extension of the Burrows-Wheeler transform
- Balancing and clustering of words in the Burrows-Wheeler transform
- Block sorting-based transformations on words: beyond the magic BWT
- Boosting textual compression in optimal linear time
- Burrows-Wheeler transform and palindromic richness
- Burrows-Wheeler transform and run-length enconding
- Burrows-Wheeler transform and Sturmian words
- Clustering words and interval exchanges
- Counting permutations with given cycle structure and descent set
- Distance measures for biological sequences: some recent approaches
- Engineering a lightweight suffix array construction algorithm
- External memory BWT and LCP computation for sequence collections with applications
- Factorizing words over an ordered alphabet
- Fast canonization of circular strings
- From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization
- Generalized Lyndon words
- scientific article; zbMATH DE number 2038766 (Why is no real title available?)
- scientific article; zbMATH DE number 2183071 (Why is no real title available?)
- Indexing compressed text
- Lexicographically least circular substrings
- Lightweight LCP construction for very large collections of strings
- Linear work suffix array construction
- Long cycles in \(abc\)-permutations
- Measuring the clustering effect of BWT via RLE
- On generalized Lyndon words
- On optimally partitioning a text to improve its compression
- Optimal lower and upper bounds for representing sequences
- Quorums from difference covers
- Sorting conjugates and suffixes of words in a multiset
- The Burrows-Wheeler similarity distribution between biological sequences based on Burrows-Wheeler transform
- The Burrows-Wheeler transform between data compression and combinatorics on words
- Wheeler graphs: a framework for BWT-based data structures
- Words with simple Burrows-Wheeler transforms
Cited in
(10)- Block sorting-based transformations on words: beyond the magic BWT
- When a dollar makes a BWT
- Medium-Space Algorithms for Inverse BWT
- Binary block order Rouen transform
- A new class of searchable and provably highly compressible string transformations
- Linking BWT and XBW via Aho-Corasick automaton: applications to run-length encoding
- A new class of string transformations for compressed text indexing
- Constructing and indexing the bijective and extended Burrows-Wheeler transform
- \(V\)-words, Lyndon words and substring circ-UMFFs
- Algorithms for Galois words: detection, factorization, and rotation
This page was built for publication: The alternating BWT: an algorithmic perspective
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2297865)
