King's College London

Research portal

V-Order: New combinatorial properties & a simple comparison algorithm

Research output: Contribution to journalArticlepeer-review

Ali Alatabbi, Jacqueline W. Daykin, Juha Kärkkäinen, M. Sohel Rahman, W.F. Smyth

Original languageEnglish
JournalDISCRETE APPLIED MATHEMATICS
Early online date5 Aug 2016
DOIs
Accepted/In press4 Jul 2016
E-pub ahead of print5 Aug 2016

King's Authors

Abstract

V -order is a global order on strings related to Unique Maximal Factorization Families (UMFFs), themselves generalizations of Lyndon words. V -order has recently been proposed as an alternative to lexicographic order in the computation of suffix arrays and in the suffix-sorting induced by the Burrows–Wheeler transform. Efficient V -ordering of strings thus becomes a matter of considerable interest. In this paper we discover several new combinatorial properties of V -order, then explore the computational consequences; in particular, a fast, simple on-line V -order comparison algorithm that requires no auxiliary data structures.

View graph of relations

© 2020 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454