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.
|Number of pages||6|
|Journal||Discrete Applied Mathematics|
|Early online date||05 Aug 2016|
|Publication status||Published - 31 Dec 2016|
- on-line algorithm
- string comparison
- V -comparison
- V -order
FingerprintDive into the research topics of 'V-Order: New combinatorial properties & a simple comparison algorithm'. Together they form a unique fingerprint.
- Faculty of Business and Physcial Sciences, Department of Computer Science - Honorary Research Fellow