Crynodeb
V-order is a global order on strings related to Unique Maximal Factorization Families (UMFFs), themselves generalizations of Lyndon words. V-order has recently been proposed as an alternative to lexicographic order in the computation of suffix arrays and in the suffix-sorting induced by the Burrows–Wheeler transform. Efficient V-ordering of strings thus becomes a matter of considerable interest. In this paper we discover several new combinatorial properties of V-order, then explore the computational consequences; in particular, a fast, simple on-line V-order comparison algorithm that requires no auxiliary data structures.
Iaith wreiddiol | Saesneg |
---|---|
Tudalennau (o-i) | 41-46 |
Nifer y tudalennau | 6 |
Cyfnodolyn | Discrete Applied Mathematics |
Cyfrol | 215 |
Dyddiad ar-lein cynnar | 05 Awst 2016 |
Dynodwyr Gwrthrych Digidol (DOIs) | |
Statws | Cyhoeddwyd - 31 Rhag 2016 |
Cyhoeddwyd yn allanol | Ie |