Computation of the suffix array, burrows-wheeler transform and FM-index in V-order

Authors Organisations
  • Jacqueline Daykin(Author)
    King's College London
    Stellenbosch University
    Normandie University
  • Neerja Mhaskar(Author)
    McMaster University
  • W. F. Smyth(Author)
    McMaster University
    King's College London
    Murdoch University
Type Article
Original languageEnglish
Pages (from-to)82-96
Number of pages15
JournalTheoretical Computer Science
Volume880
Early online date21 Jul 2021
DOI
Publication statusPublished - 03 Aug 2021
Links
Permanent link
Show download statistics
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 Lyndon factorization, in this paper we obtain similar results for the V-order factorization. Indeed, we show that the results describing the connection between suffix arrays and Lyndon factorization are matched by analogous V-order processing. We also describe a methodology for efficiently computing the FM-Index in V-order, as well as V-order substring pattern matching using backward search.

Keywords

  • Burrows-Wheeler transform, Combinatorics, FM-index, Lexorder, String comparison, Substring pattern matching, Suffix sorting, V-BWT, V-order

Documents