Journal article
Computation of the suffix array, Burrows-Wheeler transform and FM-index in V-order
Theoretical Computer Science, Vol.880, pp.82-96
2021
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.
Details
- Title
- Computation of the suffix array, Burrows-Wheeler transform and FM-index in V-order
- Authors/Creators
- J.W. Daykin (Author/Creator)N. Mhaskar (Author/Creator)W.F. Smyth (Author/Creator)
- Publication Details
- Theoretical Computer Science, Vol.880, pp.82-96
- Publisher
- Elsevier BV
- Identifiers
- 991005541404607891
- Copyright
- © 2021 Elsevier B.V.
- Murdoch Affiliation
- School of Engineering and Information Technology
- Language
- English
- Resource Type
- Journal article
Metrics
53 Record Views
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Collaboration types
- Domestic collaboration
- International collaboration
- Citation topics
- 4 Electrical Engineering, Electronics & Computer Science
- 4.182 Data Structures, Algorithms & Complexity
- 4.182.1103 Efficient Algorithms
- Web Of Science research areas
- Computer Science, Theory & Methods
- ESI research areas
- Computer Science