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.