A Faster V-order String Comparison Algorithm

Authors Organisations
  • Ali Alatabbi(Author)
    King's College London
  • Jacqueline Daykin(Author)
  • Neerja Mhaskar(Author)
    McMaster University
  • M. Sohel Rahman(Author)
    Bangladesh University of Engineering and Technology
    King's College London
  • William F. Smyth(Author)
    McMaster University
    University of Western Australia
    Murdoch University
    Bangladesh University of Engineering and Technology
Type Paper
Original languageEnglish
Pages38–49
Publication statusPublished - 2018
EventPrague Stringology Conference - Czech Technical University, Prague, Czech Republic
Duration: 27 Aug 201828 Aug 2018

Conference

ConferencePrague Stringology Conference
CountryCzech Republic
CityPrague
Period27 Aug 201828 Aug 2018
Links
Permanent link
View graph of relations
Citation formats

Abstract

V-order is a total order on strings that determines an instance of Unique Maximal Factorization Families (UMFFs) (Daykin and Daykin, JDA 2003, and others), a generalization of Lyndon words. V-order has also recently been proposed as an alternative to lexicographic order (lexorder) in the computation of suffix arrays and in the suffix-sorting induced by the Burrows-Wheeler Transform (BWT). The central problem of efficient V-ordering of strings was considered in (Daykin, Daykin and Smyth, TCS 2013, and others), culminating in a remarkably simple, linear time, constant space comparison algorithm (Alatabbi, Daykin, Kärkkäinen, Rahman and Smyth, DAM 2016). In this paper we improve on this result to achieve significant speed-up in almost all cases of interest