Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

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.

Item Type: Journal Article
Murdoch Affiliation(s): 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