Binary block order Rouen Transform

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

Research output: Contribution to journalArticlepeer-review

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.
Original languageEnglish
Pages (from-to)118-134
Number of pages17
JournalTheoretical Computer Science
Volume656
Issue numberB
Early online date24 May 2016
DOIs
Publication statusPublished - 20 Dec 2016
Externally publishedYes

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

Fingerprint

Dive into the research topics of 'Binary block order Rouen Transform'. Together they form a unique fingerprint.

Cite this