We introduce bijective Burrows–Wheeler type transforms for binary strings. The original method by Burrows and Wheeler 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, 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.
|Number of pages||17|
|Journal||Theoretical Computer Science|
|Early online date||24 May 2016|
|Publication status||Published - 20 Dec 2016|
- binary alphabet
- block order
- Burrown-Wheeler Transofrm
- B -word
- data clustering
- inverse transform
- lexicographic order
- Lyndon word
- suffix array
FingerprintDive into the research topics of 'Binary block order Rouen Transform'. Together they form a unique fingerprint.
- Faculty of Business and Physcial Sciences, Department of Computer Science - Honorary Research Fellow