Catalog Home Page

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.

Publication Type: Journal Article
Murdoch Affiliation: 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