V-Order: New combinatorial properties & a simple comparison algorithm

Ali Alatabbi; Jacqueline W. Daykin; Juha Kärkkäinen; M. Sohel Rahman; W.F. Smyth

doi:10.1016/j.dam.2016.07.006

V-Order: New combinatorial properties & a simple comparison algorithm

Ali Alatabbi, Jacqueline W. Daykin, Juha Kärkkäinen, M. Sohel Rahman, W.F. Smyth

Research output: Contribution to journal › Article › peer-review

6 Citations (Scopus)

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.

Original language	English
Journal	DISCRETE APPLIED MATHEMATICS
Early online date	5 Aug 2016
DOIs	https://doi.org/10.1016/j.dam.2016.07.006
Publication status	E-pub ahead of print - 5 Aug 2016

Keywords

Combinatorics
Experiments
Lexorder
Linear
On-line algorithm
Optimal
String comparison
V -comparison
V -order

Access to Document

10.1016/j.dam.2016.07.006

Cite this

@article{7609ea16a9354cb99168cfb790ed0f17,

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 {Sohel Rahman}, M. and W.F. Smyth",

year = "2016",

month = aug,

day = "5",

doi = "10.1016/j.dam.2016.07.006",

language = "English",

journal = "DISCRETE APPLIED MATHEMATICS",

issn = "0166-218X",

publisher = "Elsevier",

}

TY - JOUR

T1 - V-Order: New combinatorial properties & a simple comparison algorithm

AU - Alatabbi, Ali

AU - Daykin, Jacqueline W.

AU - Kärkkäinen, Juha

AU - Sohel Rahman, M.

AU - Smyth, W.F.

PY - 2016/8/5

Y1 - 2016/8/5

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

SN - 0166-218X

JO - DISCRETE APPLIED MATHEMATICS

JF - DISCRETE APPLIED MATHEMATICS

ER -

V-Order: New combinatorial properties & a simple comparison algorithm

Abstract

Keywords

Access to Document

Fingerprint

Cite this