Binary block order Rouen Transform

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

doi:10.1016/j.tcs.2016.05.028

Binary block order Rouen Transform

Standard

Binary block order Rouen Transform. / Daykin, Jacqueline W.; Groult, Richard; Guesnet, Yannick et al.

In: Theoretical Computer Science, Vol. 656, No. B, 20.12.2016, p. 118-134.

Research output: Contribution to journal › Article › peer-review

Harvard

Daykin, JW, Groult, R, Guesnet, Y, Lecroq, T, Lefebvre, A, Léonard, M & Prieur-Gaston, É 2016, 'Binary block order Rouen Transform', Theoretical Computer Science, vol. 656, no. B, pp. 118-134. https://doi.org/10.1016/j.tcs.2016.05.028

APA

Daykin, J. W., Groult, R., Guesnet, Y., Lecroq, T., Lefebvre, A., Léonard, M., & Prieur-Gaston, É. (2016). Binary block order Rouen Transform. Theoretical Computer Science, 656(B), 118-134. https://doi.org/10.1016/j.tcs.2016.05.028

Vancouver

Daykin JW, Groult R, Guesnet Y, Lecroq T, Lefebvre A, Léonard M et al. Binary block order Rouen Transform. Theoretical Computer Science. 2016 Dec 20;656(B):118-134. Epub 2016 May 24. doi: 10.1016/j.tcs.2016.05.028

Author

Daykin, Jacqueline W. ; Groult, Richard ; Guesnet, Yannick et al. / Binary block order Rouen Transform. In: Theoretical Computer Science. 2016 ; Vol. 656, No. B. pp. 118-134.

Bibtex - Download

@article{d66854c8b8dc42a79996affadb42c33c,

title = "Binary block order Rouen Transform",

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

author = "Daykin, {Jacqueline W.} and Richard Groult and Yannick Guesnet and Thierry Lecroq and Arnaud Lefebvre and Martine L{\'e}onard and {\'E}lise Prieur-Gaston",

year = "2016",

month = dec,

day = "20",

doi = "10.1016/j.tcs.2016.05.028",

language = "English",

volume = "656",

pages = "118--134",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "B",

}

RIS (suitable for import to EndNote) - Download

TY - JOUR

T1 - Binary block order Rouen Transform

AU - Daykin, Jacqueline W.

AU - Groult, Richard

AU - Guesnet, Yannick

AU - Lecroq, Thierry

AU - Lefebvre, Arnaud

AU - Léonard, Martine

AU - Prieur-Gaston, Élise

PY - 2016/12/20

Y1 - 2016/12/20

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

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

KW - algorithm

KW - bijective

KW - binary alphabet

KW - block order

KW - Burrown-Wheeler Transofrm

KW - B -word

KW - data clustering

KW - inverse transform

KW - lexicographic order

KW - linear

KW - Lyndon word

KW - string