A survey of string orderings and their application to the Burrows-Wheeler transform
DOI10.1016/j.tcs.2017.02.021zbMath1386.68235OpenAlexW2593988474MaRDI QIDQ1698705
Jacqueline W. Daykin, Thierry Lecroq, Yannick Guesnet, Élise Prieur-Gaston, Martine Léonard, Richard Groult, Arnaud Lefebvre
Publication date: 16 February 2018
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2017.02.021
algorithmlexicographic orderinverse transformBurrows-Wheeler transformbijectivedata clusteringsuffix arraydegenerate\(V\)-orderLyndon word\(B\)-wordbinary alphabetblock ordersuffix-sorting\(GB\)-word\(T\)-ordergeneric alphabetgeneric block orderindeterminate Lyndon word
Combinatorics on words (68R15) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)
Related Items (1)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(V\)-order: new combinatorial properties \& a simple comparison algorithm
- A linear partitioning algorithm for hybrid Lyndons using \(V\)-order
- Suffix array and Lyndon factorization of a text
- Binary block order Rouen transform
- A four-stage algorithm for updating a Burrows-Wheeler transform
- A note on the Burrows-Wheeler transformation
- Lyndon-like and V-order factorizations of strings
- Computing the Burrows-Wheeler transform in place and in small space
- A bijective variant of the Burrows-Wheeler transform using \(V\)-order
- Lightweight LCP construction for very large collections of strings
- Simple Linear Comparison of Strings in V-order*
- String Comparison and Lyndon-Like Factorization Using V-Order in Linear Time
- Factorizing words over an ordered alphabet
- Linear work suffix array construction
- Space Efficient Linear Time Construction of Suffix Arrays
- Linear Time Suffix Array Construction Using D-Critical Substrings
- Ordering Integer Vectors for Coordinate Deletions
- Lightweight LCP Construction for Next-Generation Sequencing Datasets
- A Constant-Space Comparison-Based Algorithm for Computing the Burrows–Wheeler Transform
- Combinatorial Pattern Matching
- On Burnside's Problem
- Free differential calculus. IV: The quotient groups of the lower central series
This page was built for publication: A survey of string orderings and their application to the Burrows-Wheeler transform
