Binary block order Rouen Transform

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.

Authors

• Jacqueline W. Daykin
• Richard Groult
• Yannick Guesnet
• Thierry Lecroq
• Arnaud Lefebvre
• Martine Léonard
• Élise Prieur-Gaston

Keywords

• Algorithm
• Bijective
• Binary alphabet
• Block order
• Burrows–Wheeler Transform
• B-word
• Data clustering
• Inverse transform
• Lexicographic order
• Linear
• Lyndon word
• String
• Suffix array
• Suffix-sorting
• Word