A bijective variant of the Burrows-Wheeler transform using \(V\)-order

DOI10.1016/j.tcs.2014.03.014zbMath1359.68332OpenAlexW2094270516WikidataQ114129173 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

zbMATH Keywords

complexitylexicographic ordertotal orderstringsuffix array\(V\)-order\(V\)-wordLyndon word\(V\)-transform\(V\)-BWTlex-extension orderbijective Burrows-Wheeler transform

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items

Indeterminate string factorizations and degenerate text transformations ⋮ \(V\)-order: new combinatorial properties \& a simple comparison algorithm ⋮ A survey of string orderings and their application to the Burrows-Wheeler transform ⋮ Binary block order Rouen transform ⋮ String Comparison and Lyndon-Like Factorization Using V-Order in Linear Time ⋮ Generic Algorithms for Factoring Strings ⋮ Inverse Lyndon words and inverse Lyndon factorizations of words ⋮ Computation of the suffix array, Burrows-Wheeler transform and FM-index in \(V\)-order

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