Journal article
V-Order: New combinatorial properties & a simple comparison algorithm
Discrete Applied Mathematics, Vol.215, pp.41-46
2016
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.
Details
- Title
- V-Order: New combinatorial properties & a simple comparison algorithm
- Authors/Creators
- A. Alatabbi (Author/Creator)J.W. Daykin (Author/Creator)J. Kärkkäinen (Author/Creator)M. Sohel Rahman (Author/Creator)W.F. Smyth (Author/Creator)
- Publication Details
- Discrete Applied Mathematics, Vol.215, pp.41-46
- Publisher
- Elsevier BV
- Identifiers
- 991005543788107891
- Copyright
- © 2016 Elsevier B.V.
- Murdoch Affiliation
- School of Engineering and Information Technology
- Language
- English
- Resource Type
- Journal article
Metrics
29 Record Views
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Collaboration types
- Domestic collaboration
- International collaboration
- Citation topics
- 4 Electrical Engineering, Electronics & Computer Science
- 4.182 Data Structures, Algorithms & Complexity
- 4.182.1103 Efficient Algorithms
- Web Of Science research areas
- Mathematics, Applied
- ESI research areas
- Engineering