Abstract
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, Border, which yields not one, but twin transforms: one based on Lyndon words, the other on a repetition of Lyndon words. These binary BBWT transforms are constructed here for Bwords, analogous structures to Lyndon words. A key computation in the transforms is the application of a lineartime suffixsorting technique, such as, to sort the cyclic rotations of a binary input string into their Border. Moreover, like the original lexicographic transform, we show that computing the BBWT inverses is also achieved in linear time by using straightforward combinatorial arguments.
Original language  English 

Pages (fromto)  118134 
Number of pages  17 
Journal  Theoretical Computer Science 
Volume  656 
Issue number  B 
Early online date  24 May 2016 
DOIs  
Publication status  Published  20 Dec 2016 
Externally published  Yes 
Keywords
 algorithm
 bijective
 binary alphabet
 block order
 BurrownWheeler Transofrm
 B word
 data clustering
 inverse transform
 lexicographic order
 linear
 Lyndon word
 string
 suffix array
 suffixsorting
 word
Fingerprint
Dive into the research topics of 'Binary block order Rouen Transform'. Together they form a unique fingerprint.Profiles

Jacqueline Daykin
 Faculty of Business and Physical Sciences, Department of Computer Science  Honorary Research Fellow
Person: Other