@article{DAYKIN2016118,
title = {Binary block order Rouen Transform},
journal = {Theoretical Computer Science},
volume = {656},
pages = {118-134},
year = {2016},
note = {Stringology: In Celebration of Bill Smyth’s 80th Birthday},
issn = {0304-3975},
doi = {https://doi.org/10.1016/j.tcs.2016.05.028},
url = {https://www.sciencedirect.com/science/article/pii/S0304397516301645},
author = {Jacqueline W. Daykin and Richard Groult and Yannick Guesnet and Thierry Lecroq and Arnaud Lefebvre and Martine Léonard and Élise Prieur-Gaston},
keywords = {Algorithm, Bijective, Binary alphabet, Block order, Burrows–Wheeler Transform, -word, Data clustering, Inverse transform, Lexicographic order, Linear, Lyndon word, String, Suffix array, Suffix-sorting, Word},
abstract = {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.}
}