کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4949912 1440206 2016 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
V-Order: New combinatorial properties & a simple comparison algorithm
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
V-Order: New combinatorial properties & a simple comparison algorithm
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 215, 31 December 2016, Pages 41-46
نویسندگان
, , , , ,