Journal article
Applications of V-Order: Suffix arrays, the Burrows-Wheeler transform & the FM-index
WALCOM: Algorithms and Computation, Vol.11355, pp.329-338
2018
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.
Details
- Title
- Applications of V-Order: Suffix arrays, the Burrows-Wheeler transform & the FM-index
- Authors/Creators
- A. Alatabbi (Author/Creator)J.W. Daykin (Author/Creator)N. Mhaskar (Author/Creator)M.S. Rahman (Author/Creator)W.F. Smyth (Author/Creator)
- Publication Details
- WALCOM: Algorithms and Computation, Vol.11355, pp.329-338
- Publisher
- Springer Verlag
- Identifiers
- 991005540683207891
- Copyright
- © 2019 Springer Nature Switzerland AG
- Murdoch Affiliation
- School of Engineering and Information Technology
- Language
- English
- Resource Type
- Journal article
Metrics
62 Record Views