Catalog Home Page

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

Alatabbi, A., Daykin, J.W., Kärkkäinen, J., Sohel Rahman, M. and Smyth, W.F. (2016) V-Order: New combinatorial properties & a simple comparison algorithm. Discrete Applied Mathematics, 215 . pp. 41-46.

Link to Published Version: http://dx.doi.org/10.1016/j.dam.2016.07.006
*Subscription may be required

Abstract

V-order is a global order on strings related to Unique Maximal Factorization Families (UMFFs), themselves generalizations of Lyndon words. VV-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 VV-ordering of strings thus becomes a matter of considerable interest. In this paper we discover several new combinatorial properties of VV-order, then explore the computational consequences; in particular, a fast, simple on-line VV-order comparison algorithm that requires no auxiliary data structures.

Publication Type: Journal Article
Murdoch Affiliation: School of Engineering and Information Technology
Publisher: Elsevier BV
Copyright: © 2016 Elsevier B.V.
URI: http://researchrepository.murdoch.edu.au/id/eprint/34257
Item Control Page Item Control Page