کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10331852 | 686805 | 2014 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Faster semi-external suffix sorting
ترجمه فارسی عنوان
مرتب سازی پسوند سریع تر نیمه خارجی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Suffix array (SA) construction is a time-and-memory bottleneck in many string processing applications. In this paper we improve the runtime of a small-space - semi-external - SA construction algorithm by Kärkkäinen (TCS, 2007) [5]. We achieve a speedup in practice of 2-4 times, without increasing memory usage. Our main contribution is a way to implement the “pointer copying” heuristic, used in less space-efficient SA construction algorithms, in a memory-efficient way.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 114, Issue 4, April 2014, Pages 174-178
Journal: Information Processing Letters - Volume 114, Issue 4, April 2014, Pages 174-178
نویسندگان
Jasbir Dhaliwal,