کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952359 | 1364442 | 2016 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Tighter bounds for the sum of irreducible LCP values
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Tighter bounds for the sum of irreducible LCP values Tighter bounds for the sum of irreducible LCP values](/preview/png/4952359.png)
چکیده انگلیسی
The suffix array is frequently augmented with the longest-common-prefix (LCP) array that stores the lengths of the longest common prefixes between lexicographically adjacent suffixes of a text. While the sum of the values in the LCP array can be Ω(n2) for a text of length n, the sum of so-called irreducible LCP values was shown to be O(nlgâ¡n) a few years ago. In this paper, we improve the bound to O(nlgâ¡r), where râ¤n is the number of runs in the Burrows-Wheeler transform of the text. We also show that our bound is tight up to lower order terms (unlike the previous bound). Our results and the techniques used in proving them provide new insights into the combinatorics of text indexing and compression, and have immediate applications to LCP array construction algorithms.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 656, Part B, 20 December 2016, Pages 265-278
Journal: Theoretical Computer Science - Volume 656, Part B, 20 December 2016, Pages 265-278
نویسندگان
Juha Kärkkäinen, Dominik Kempa, Marcin Pia̧tkowski,