V-OrderNew combinatorial properties & a simple comparison algorithm

Authors Organisations
  • Ali Alatabbi(Author)
    King's College London
  • Jacqueline Daykin(Author)
    King's College London
    Royal Holloway, University of London
  • Juha Kärkkäinen(Author)
    University of Helsinki
  • M. Sohel Rahman(Author)
    Bangladesh University of Engineering and Technology
  • W. F. Smyth(Author)
    King's College London
    McMaster University
    Murdoch University
Type Article
Original languageEnglish
Pages (from-to)41-46
Number of pages6
JournalDiscrete Applied Mathematics
Volume215
Early online date05 Aug 2016
DOI
Publication statusPublished - 31 Dec 2016
Externally publishedYes
Permanent link
View graph of relations
Citation formats

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.

Keywords

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