Catalog Home Page

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.

Publication Type: Others
Murdoch Affiliation: 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