کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4952116 1442011 2017 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Inducing enhanced suffix arrays for string collections
ترجمه فارسی عنوان
ایجاد آرایههای پسوند افزایش یافته برای مجموعههای رشته
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Constructing the suffix array for a string collection is an important task that may be performed by sorting the concatenation of all strings. In this article we present algorithms gSAIS and gSACA-K, which extend SAIS (Nong et al., 2011) [8] and SACA-K (Nong, 2013) [10] to construct the suffix array for a string collection maintaining their theoretical bounds, respecting the order among all suffixes, and improving their practical performance. gSACA-K is an optimal suffix array construction algorithm for string collections from constant alphabets. Moreover, we show how to modify gSAIS and gSACA-K to also compute the longest common prefix array and the document array as a byproduct of suffix sorting, with the same theoretical bounds. We performed experiments that showed that our algorithms have an outstanding practical performance.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 678, 23 May 2017, Pages 22-39
نویسندگان
, , ,