V-OrderNew combinatorial properties & a simple comparison algorithm

Standard

V-Order : New combinatorial properties & a simple comparison algorithm. / Alatabbi, Ali; Daykin, Jacqueline W.; Kärkkäinen, Juha; Rahman, M. Sohel; Smyth, W. F.

In: Discrete Applied Mathematics, Vol. 215, 31.12.2016, p. 41-46.

Research output: Contribution to journalArticlepeer-review

Harvard

Alatabbi, A, Daykin, JW, Kärkkäinen, J, Rahman, MS & Smyth, WF 2016, 'V-Order: New combinatorial properties & a simple comparison algorithm', Discrete Applied Mathematics, vol. 215, pp. 41-46. https://doi.org/10.1016/j.dam.2016.07.006

APA

Alatabbi, A., Daykin, J. W., Kärkkäinen, J., Rahman, M. S., & Smyth, W. F. (2016). V-Order: New combinatorial properties & a simple comparison algorithm. Discrete Applied Mathematics, 215, 41-46. https://doi.org/10.1016/j.dam.2016.07.006

Vancouver

Alatabbi A, Daykin JW, Kärkkäinen J, Rahman MS, Smyth WF. V-Order: New combinatorial properties & a simple comparison algorithm. Discrete Applied Mathematics. 2016 Dec 31;215:41-46. https://doi.org/10.1016/j.dam.2016.07.006

Author

Alatabbi, Ali ; Daykin, Jacqueline W. ; Kärkkäinen, Juha ; Rahman, M. Sohel ; Smyth, W. F. / V-Order : New combinatorial properties & a simple comparison algorithm. In: Discrete Applied Mathematics. 2016 ; Vol. 215. pp. 41-46.

Bibtex - Download

@article{bf6d4c1b88eb4d1ebc3112bacd98df7c,
title = "V-Order: New combinatorial properties & a simple comparison algorithm",
abstract = "V-order is a global order on strings related to Unique Maximal Factorization Families (UMFFs), themselves generalizations of Lyndon words. V-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 V-ordering of strings thus becomes a matter of considerable interest. In this paper we discover several new combinatorial properties of V-order, then explore the computational consequences; in particular, a fast, simple on-line V-order comparison algorithm that requires no auxiliary data structures.",
keywords = "combinatorics, experiments, lexorder, linear, on-line algorithm, optimal, string comparison, V -comparison, V -order",
author = "Ali Alatabbi and Daykin, {Jacqueline W.} and Juha K{\"a}rkk{\"a}inen and Rahman, {M. Sohel} and Smyth, {W. F.}",
year = "2016",
month = dec,
day = "31",
doi = "10.1016/j.dam.2016.07.006",
language = "English",
volume = "215",
pages = "41--46",
journal = "Discrete Applied Mathematics",
publisher = "Elsevier",

}

RIS (suitable for import to EndNote) - Download

TY - JOUR

T1 - V-Order

T2 - New combinatorial properties & a simple comparison algorithm

AU - Alatabbi, Ali

AU - Daykin, Jacqueline W.

AU - Kärkkäinen, Juha

AU - Rahman, M. Sohel

AU - Smyth, W. F.

PY - 2016/12/31

Y1 - 2016/12/31

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

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

KW - combinatorics

KW - experiments

KW - lexorder

KW - linear

KW - on-line algorithm

KW - optimal

KW - string comparison

KW - V -comparison

KW - V -order

U2 - 10.1016/j.dam.2016.07.006

DO - 10.1016/j.dam.2016.07.006

M3 - Article

VL - 215

SP - 41

EP - 46

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

View graph of relations
Citation formats