کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430892 | 688224 | 2013 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Computing the longest common prefix array based on the Burrows–Wheeler transform
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Computing the longest common prefix array based on the Burrows–Wheeler transform Computing the longest common prefix array based on the Burrows–Wheeler transform](/preview/png/430892.png)
چکیده انگلیسی
Many sequence analysis tasks can be accomplished with a suffix array, and several of them additionally need the longest common prefix array. In large scale applications, suffix arrays are being replaced with full-text indexes that are based on the Burrows–Wheeler transform. In this paper, we present the first algorithm that computes the longest common prefix array directly on the wavelet tree of the Burrows–Wheeler transformed string. It runs in linear time and a practical implementation requires approximately 2.2 bytes per character.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 18, January 2013, Pages 22–31
Journal: Journal of Discrete Algorithms - Volume 18, January 2013, Pages 22–31
نویسندگان
Timo Beller, Simon Gog, Enno Ohlebusch, Thomas Schnattinger,