Author name cluster

Yannick Guesnet

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

TCS Journal 2018 Journal Article

A survey of string orderings and their application to the Burrows–Wheeler transform

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

For over 20 years the data clustering properties and applications of the efficient Burrows–Wheeler transform have been researched. Lexicographic suffix-sorting is induced during the transformation, and more recently a new direction has considered alternative ordering strategies for suffix arrays and thus the transforms. In this survey we look at these distinctly ordered bijective and linear transforms. For arbitrary alphabets we discuss the V-BWT derived from V-order and the D-BWT based on lex-extension order. The binary case yields a pair of transforms, the binary Rouen B-BWT, defined using binary block order. Lyndon words are relevant to implementing the original transform; the new transforms are defined for analogous structures: V-words, indeterminate Lyndon words, and B-words, respectively. There is plenty of scope for further non-lexicographic transforms as indicated in the conclusion.

Details DOI

TCS Journal 2016 Journal Article

Binary block order Rouen Transform

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

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.

Details DOI

TCS Journal 2003 Journal Article

On maximal synchronous codes

Yannick Guesnet

In this paper, we are interested in maximal synchronous codes. More precisely, we prove that we can embed any synchronous code in a maximal one. Moreover, we establish that, for synchronous codes, the notion of maximality in the family of synchronous codes is equivalent to the notion of maximality in the family of codes.

Details DOI

TCS Journal 2002 Journal Article

On maximal codes with a finite interpreting delay

Yannick Guesnet

The notion of codes with a finite interpreting delay (f. i. d.) was introduced in (Guesnet, Theoret. Inform. Appl. 34 (2000) 47–59). In this paper, we are interested in the notion of maximality for f. i. d. codes. We characterize the maximal f. i. d. codes in terms of completeness. We also present an embedding procedure keeping thinness, rationality and the delay.

Details DOI