Applications of V-Order: Suffix Arrays, the Burrows-Wheeler Transform & the FM-index

Ali Alatabbi, Jacqueline W. Daykin, Neerja Mhaskar, M. Sohel Rahman, W. F. Smyth

Allbwn ymchwil: Pennod mewn Llyfr/Adroddiad/Trafodion CynhadleddTrafodion Cynhadledd (Nid-Cyfnodolyn fathau)

2 Dyfyniadau (Scopus)

Crynodeb

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.
Iaith wreiddiolSaesneg
TeitlWALCOM
Is-deitlAlgorithms and Computation - 13th International Conference, WALCOM 2019, Proceedings
GolygyddionShin-ichi Nakano, Krishnendu Mukhopadhyaya, Gautam K. Das, Partha S. Mandal
CyhoeddwrSpringer Nature
Tudalennau329-338
Nifer y tudalennau10
ISBN (Electronig)978-3-030-10564-8
ISBN (Argraffiad)978-3-030-10563-1
Dynodwyr Gwrthrych Digidol (DOIs)
StatwsCyhoeddwyd - 16 Chwef 2019

Cyfres gyhoeddiadau

EnwLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Cyfrol11355 LNCS
ISSN (Argraffiad)0302-9743
ISSN (Electronig)1611-3349

Ôl bys

Gweld gwybodaeth am bynciau ymchwil 'Applications of V-Order: Suffix Arrays, the Burrows-Wheeler Transform & the FM-index'. Gyda’i gilydd, maen nhw’n ffurfio ôl bys unigryw.

Dyfynnu hyn