Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

Computation of the suffix array, Burrows-Wheeler transform and FM-index in V-order

Daykin, J.W., Mhaskar, N. and Smyth, W.F. (2021) Computation of the suffix array, Burrows-Wheeler transform and FM-index in V-order. Theoretical Computer Science, 880 . pp. 82-96.

Link to Published Version: https://doi.org/10.1016/j.tcs.2021.06.004
*Subscription may be required

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.

Item Type: Journal Article
Murdoch Affiliation(s): School of Engineering and Information Technology
Publisher: Elsevier BV
Copyright: © 2021 Elsevier B.V.
URI: http://researchrepository.murdoch.edu.au/id/eprint/61614
Item Control Page Item Control Page