A survey of string orderings and their application to the Burrows-Wheeler transform
DOI10.1016/j.tcs.2017.02.021zbMath1386.68235MaRDI 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
algorithm; lexicographic order; inverse transform; Burrows-Wheeler transform; bijective; data clustering; suffix array; degenerate; \(V\)-order; Lyndon word; \(B\)-word; binary alphabet; block order; suffix-sorting; \(GB\)-word; \(T\)-order; generic alphabet; generic block order; indeterminate Lyndon word
68R15: Combinatorics on words
68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
68W32: Algorithms on strings
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
