Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949912 | Discrete Applied Mathematics | 2016 | 6 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ali Alatabbi, Jacqueline W. Daykin, Juha Kärkkäinen, M. Sohel Rahman, W.F. Smyth,