کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430893 | 688224 | 2013 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Near real-time suffix tree construction via the fringe marked ancestor problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Near real-time suffix tree construction via the fringe marked ancestor problem Near real-time suffix tree construction via the fringe marked ancestor problem](/preview/png/430893.png)
چکیده انگلیسی
We contribute a further step towards the plausible real-time construction of suffix trees by presenting an on-line algorithm that spends only O(loglogn) time processing each input symbol and takes O(nloglogn) time in total, where n is the length of the input text. Our results improve on a previously published algorithm that takes O(logn) time per symbol and O(nlogn) time in total. The improvements are obtained by adapting Weinerʼs suffix tree construction algorithm to use a new data structure for the fringe marked ancestor problem, a special case of the nearest marked ancestor problem, which may be of independent interest.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 18, January 2013, Pages 32–48
Journal: Journal of Discrete Algorithms - Volume 18, January 2013, Pages 32–48
نویسندگان
Dany Breslauer, Giuseppe F. Italiano,