Applications of V-OrderSuffix Arrays, the Burrows-Wheeler Transform & the FM-index

Authors Organisations
  • Ali Alatabbi(Author)
    King's College London
  • Jacqueline Daykin(Author)
    King's College London
    Stellenbosch University
  • Neerja Mhaskar(Author)
    McMaster University
  • M. Sohel Rahman(Author)
    Bangladesh University of Engineering and Technology
  • W. F. Smyth(Author)
    King's College London
    McMaster University
    Murdoch University
Type Conference Proceeding (Non-Journal item)
Original languageEnglish
Title of host publicationWALCOM: Algorithms and Computation
Subtitle of host publication13th International Conference, WALCOM 2019, Guwahati, India, February 27 – March 2, 2019, Proceedings
EditorsGautam K. Das, Partha S. Mandal, Krishnendu Mukhopadhyaya, Shin-ichi Nakano
PublisherSpringer Nature
Pages329-338
Number of pages10
ISBN (Electronic)978-3-030-10564-8
ISBN (Print)978-3-030-10563-1
DOI
Publication statusPublished - 16 Feb 2019

Publication series

NameWALCOM: Algorithms and Computation
PublisherSpringer Nature
Number13
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349
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), a generalization of Lyndon words. The fundamental V-comparison of strings can be done in linear time and constant space. V-order has 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). In line with the recent interest in the connection between suffix arrays and the Lyndon factorization, we in this paper make a first attempt to obtain similar results for the V-order factorization. Indeed, we show that the results describing the connection between suffix arrays and the Lyndon factorization are matched by analogous V-order processing. We then apply the V-BWT to implement pattern matching in V-order after suitably modifying the FM-index.