کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952346 | 1364442 | 2016 | 32 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Binary block order Rouen Transform
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We introduce bijective Burrows-Wheeler type transforms for binary strings.1 The original method by Burrows and Wheeler [4] is based on lexicographic order for general alphabets, and the transform is defined to be the last column of the ordered BWT matrix. This new approach applies binary block order, B-order, which yields not one, but twin transforms: one based on Lyndon words, the other on a repetition of Lyndon words. These binary B-BWT transforms are constructed here for B-words, analogous structures to Lyndon words. A key computation in the transforms is the application of a linear-time suffix-sorting technique, such as [18,21,22,27], to sort the cyclic rotations of a binary input string into their B-order. Moreover, like the original lexicographic transform, we show that computing the B-BWT inverses is also achieved in linear time by using straightforward combinatorial arguments.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 656, Part B, 20 December 2016, Pages 118-134
Journal: Theoretical Computer Science - Volume 656, Part B, 20 December 2016, Pages 118-134
نویسندگان
Jacqueline W. Daykin, Richard Groult, Yannick Guesnet, Thierry Lecroq, Arnaud Lefebvre, Martine Léonard, Ãlise Prieur-Gaston,