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

String comparison in V-Order: New lexicographic properties & On-line applications

Alatabbi, A., Daykin, J.W., Rahman, M.S. and Smyth, W.F. (2015) String comparison in V-Order: New lexicographic properties & On-line applications. Unpublished Publication .

[img]
Preview
PDF (Pre-print)
Download (150kB)
Free to read: http://arxiv.org/abs/1507.07038
*No subscription required

Abstract

V-order is a global order on strings related to Unique Maximal Factorization Families (UMFFs), which are themselves generalizations of Lyndon words. V-order has recently been proposed as an alternative to lexicographical 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 present new and surprising results on V-order in strings, then go on to explore the algorithmic consequences.

Item Type: Others
Murdoch Affiliation(s): School of Engineering and Information Technology
Publisher: Cornell University Library
URI: http://researchrepository.murdoch.edu.au/id/eprint/28247
Item Control Page Item Control Page

Downloads

Downloads per month over past year