A survey of string orderings and their application to the Burrows-Wheeler transform
DOI10.1016/J.TCS.2017.02.021zbMATH Open1386.68235OpenAlexW2593988474MaRDI QIDQ1698705FDOQ1698705
Jacqueline W. Daykin, Thierry Lecroq, Yannick Guesnet, Élise Prieur-Gaston, M. Léonard, Richard Groult, A. 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
Lyndon wordalgorithmdegeneratelexicographic order\(V\)-ordersuffix arrayBurrows-Wheeler transformdata clustering\(B\)-wordbinary alphabetblock orderinverse transformsuffix-sortingbijective\(GB\)-word\(T\)-ordergeneric alphabetgeneric block orderindeterminate Lyndon word
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Combinatorics on words (68R15) Algorithms on strings (68W32)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Factorizing words over an ordered alphabet
- Linear work suffix array construction
- On Burnside's Problem
- Combinatorial Pattern Matching
- Lyndon-like and V-order factorizations of strings
- A bijective variant of the Burrows-Wheeler transform using \(V\)-order
- Simple linear comparison of strings in \(V\)-order
- String Comparison and Lyndon-Like Factorization Using V-Order in Linear Time
- \(V\)-order: new combinatorial properties \& a simple comparison algorithm
- Space Efficient Linear Time Construction of Suffix Arrays
- A linear partitioning algorithm for hybrid Lyndons using \(V\)-order
- Suffix array and Lyndon factorization of a text
- A note on the Burrows-Wheeler transformation
- Linear Time Suffix Array Construction Using D-Critical Substrings
- Free differential calculus. IV: The quotient groups of the lower central series
- A Constant-Space Comparison-Based Algorithm for Computing the Burrows–Wheeler Transform
- A four-stage algorithm for updating a Burrows-Wheeler transform
- Computing the Burrows-Wheeler transform in place and in small space
- Lightweight LCP construction for very large collections of strings
- Lightweight LCP Construction for Next-Generation Sequencing Datasets
- Binary block order Rouen transform
- Ordering Integer Vectors for Coordinate Deletions
Cited In (6)
- When a dollar makes a BWT
- Computation of the suffix array, Burrows-Wheeler transform and FM-index in \(V\)-order
- On the number of equal-letter runs of the bijective Burrows-Wheeler transform
- Computing Burrows-Wheeler similarity distributions for string collections
- Computing the Burrows-Wheeler Transform of a String and Its Reverse
- A bijective variant of the Burrows-Wheeler transform using \(V\)-order
Uses Software
This page was built for publication: A survey of string orderings and their application to the Burrows-Wheeler transform
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1698705)
