Binary block order Rouen Transform

Authors Organisations
  • Jacqueline Daykin(Author)
    Royal Holloway, University of London
    King's College London
    Normandy University
  • Richard Groult(Author)
    University of Picardie Jules Verne
    Normandy University
  • Yannick Guesnet(Author)
    Normandy University
  • Thierry Lecroq(Author)
    Normandy University
  • Arnaud Lefebvre(Author)
    Normandy University
  • Martine Léonard(Author)
    Normandy University
  • Élise Prieur-Gaston(Author)
    Normandy University
Type Article
Original languageEnglish
Pages (from-to)118-134
Number of pages17
JournalTheoretical Computer Science
Volume656
Issue numberB
Early online date24 May 2016
DOI
Publication statusPublished - 20 Dec 2016
Externally publishedYes
Permanent link
View graph of relations
Citation formats

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, 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.

Keywords

  • algorithm, bijective, binary alphabet, block order, Burrown-Wheeler Transofrm, B -word, data clustering, inverse transform, lexicographic order, linear, Lyndon word, string, suffix array, suffix-sorting, word