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 (SciVal)

Abstract

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
Pages (from-to)41-46
Number of pages6
JournalDiscrete Applied Mathematics
Volume215
Early online date05 Aug 2016
DOIs
Publication statusPublished - 31 Dec 2016
Externally publishedYes

Keywords

  • combinatorics
  • experiments
  • lexorder
  • linear
  • on-line algorithm
  • optimal
  • string comparison
  • V -comparison
  • V -order

Fingerprint

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

Cite this