A bijective variant of the Burrows-Wheeler transform using \(V\)-order
From MaRDI portal
Publication:2441784
DOI10.1016/j.tcs.2014.03.014zbMath1359.68332WikidataQ114129173 ScholiaQ114129173MaRDI QIDQ2441784
Jacqueline W. Daykin, W. F. Smyth
Publication date: 28 March 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2014.03.014
complexity; lexicographic order; total order; string; suffix array; \(V\)-order; \(V\)-word; Lyndon word; \(V\)-transform; \(V\)-BWT; lex-extension order; bijective Burrows-Wheeler transform
68W32: Algorithms on strings
Related Items
Generic Algorithms for Factoring Strings, \(V\)-order: new combinatorial properties \& a simple comparison algorithm, Binary block order Rouen transform, A survey of string orderings and their application to the Burrows-Wheeler transform, Inverse Lyndon words and inverse Lyndon factorizations of words, Computation of the suffix array, Burrows-Wheeler transform and FM-index in \(V\)-order, Indeterminate string factorizations and degenerate text transformations, String Comparison and Lyndon-Like Factorization Using V-Order in Linear Time
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A linear partitioning algorithm for hybrid Lyndons using \(V\)-order
- A four-stage algorithm for updating a Burrows-Wheeler transform
- Computation of words satisfying the ``rhythmic oddity property (after Simha Arom's works)
- Periodic musical sequences and Lyndon words
- A note on the Burrows-Wheeler transformation
- Lyndon-like and V-order factorizations of strings
- Fast BWT in small space by blockwise suffix sorting
- An extension of the Burrows-Wheeler transform
- String Comparison and Lyndon-Like Factorization Using V-Order in Linear Time
- Factorizing words over an ordered alphabet
- Combinatorics of Unique Maximal Factorization Families (UMFFs)
- Linear work suffix array construction
- PROPERTIES AND CONSTRUCTION OF UNIQUE MAXIMAL FACTORIZATION FAMILIES FOR STRINGS
- Space Efficient Linear Time Construction of Suffix Arrays
- Ordering Integer Vectors for Coordinate Deletions
- Generic Algorithms for Factoring Strings
- A Constant-Space Comparison-Based Algorithm for Computing the Burrows–Wheeler Transform
- Combinatorial Pattern Matching
- Simple Linear Comparison of Strings in V-Order
- Free differential calculus. IV: The quotient groups of the lower central series