V-Order: New combinatorial properties & a simple comparison algorithm

Ali Alatabbi, Jacqueline W. Daykin, Juha Kärkkäinen, M. Sohel Rahman, W.F. Smyth

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)


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.
Original languageEnglish
Early online date5 Aug 2016
Publication statusE-pub ahead of print - 5 Aug 2016


  • Combinatorics
  • Experiments
  • Lexorder
  • Linear
  • On-line algorithm
  • Optimal
  • String comparison
  • V -comparison
  • V -order


Dive into the research topics of 'V-Order: New combinatorial properties & a simple comparison algorithm'. Together they form a unique fingerprint.

Cite this