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

Applications of V-Order: Suffix arrays, the Burrows-Wheeler transform & the FM-index

Alatabbi, A., Daykin, J.W., Mhaskar, N., Rahman, M.S. and Smyth, W.F. (2018) Applications of V-Order: Suffix arrays, the Burrows-Wheeler transform & the FM-index. Lecture Notes in Computer Science, 11355 . pp. 329-338.

Link to Published Version: https://doi.org/10.1007/978-3-030-10564-8_26
*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 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.

Item Type: Journal Article
Murdoch Affiliation(s): School of Engineering and Information Technology
Publisher: Springer Verlag
Copyright: © 2019 Springer Nature Switzerland AG
URI: http://researchrepository.murdoch.edu.au/id/eprint/44374
Item Control Page Item Control Page