Applications of V-OrderSuffix Arrays, the Burrows-Wheeler Transform & the FM-index
Authors
Organisations
Type | Conference Proceeding (Non-Journal item) |
---|
Original language | English |
---|---|
Title of host publication | WALCOM: Algorithms and Computation |
Subtitle of host publication | 13th International Conference, WALCOM 2019, Guwahati, India, February 27 – March 2, 2019, Proceedings |
Editors | Gautam K. Das, Partha S. Mandal, Krishnendu Mukhopadhyaya, Shin-ichi Nakano |
Publisher | Springer Nature |
Pages | 329-338 |
Number of pages | 10 |
ISBN (Electronic) | 978-3-030-10564-8 |
ISBN (Print) | 978-3-030-10563-1 |
DOI | |
Publication status | Published - 16 Feb 2019 |
Publication series
Name | WALCOM: Algorithms and Computation |
---|---|
Publisher | Springer Nature |
Number | 13 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Permanent link | Permanent link |
---|
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.