کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875901 | 1441991 | 2017 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Measuring the clustering effect of BWT via RLE
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Measuring the clustering effect of BWT via RLE Measuring the clustering effect of BWT via RLE](/preview/png/6875901.png)
چکیده انگلیسی
More in general we show that the application of BWT to any word at worst doubles the number of equal-letter runs. Moreover, we prove that this bound is tight by exhibiting some families of words where such upper bound is always reached. We also prove that for binary words the case in which the BWT produces the maximal number of clusters is related to the very well known Artin's conjecture on primitive roots. The study of some combinatorial properties underlying this transformation could be useful for improving indexing and compression strategies.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 698, 25 October 2017, Pages 79-87
Journal: Theoretical Computer Science - Volume 698, 25 October 2017, Pages 79-87
نویسندگان
Sabrina Mantaci, Antonio Restivo, Giovanna Rosone, Marinella Sciortino, Luca Versari,