Thierry Lecroq

TCS Journal 2023 Journal Article

TCS special issue: Combinatorics on Words – WORDS 2021

• Thierry Lecroq
• Svetlana Puzynina

TCS Journal 2021 Journal Article

Fast algorithms for single and multiple pattern Cartesian tree matching

• Siwoo Song
• Geonmo Gu
• Cheol Ryu
• Simone Faro
• Thierry Lecroq
• Kunsoo Park

Cartesian tree matching is the problem of finding every substring of a given text which has the same Cartesian tree as that of a given pattern. In this paper we propose fast algorithms for single and multiple pattern Cartesian tree matching by introducing new representations and encodings. For single pattern Cartesian tree matching, we present the framework of a binary filtration method and an efficient verification technique. Any exact string matching algorithm can be used as a filtration for Cartesian tree matching in our framework. For multiple pattern Cartesian tree matching, we present two fingerprinting methods, i. e. , the parent-distance encoding and the binary encoding. By combining an efficient fingerprinting method and a conventional multiple string matching algorithm, we can efficiently solve multiple pattern Cartesian tree matching. By experiments we show that our matching algorithms provide good performances for both single and multiple pattern Cartesian tree matching.

TCS Journal 2020 Journal Article

Fast string matching for DNA sequences

• Cheol Ryu
• Thierry Lecroq
• Kunsoo Park

In this paper we propose the Maximal Average Shift (MAS) algorithm that finds a pattern scan order that maximizes the average shift length. We also present two extensions of MAS: one improves the scan speed of MAS by using the scan result of the previous window, and the other improves the running time of MAS by using q-grams. These algorithms show better average performances in scan speed than previous string matching algorithms for DNA sequences.

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.

TCS Journal 2018 Journal Article

FM-index of alignment with gaps

• Joong Chae Na
• Hyunjoon Kim
• Seunghwan Min
• Heejin Park
• Thierry Lecroq
• Martine Léonard
• Laurent Mouchard
• Kunsoo Park

Recently a compressed index for similar strings, called the FM-index of alignment (FMA), has been proposed with the functionalities of pattern search and random access. The FMA is quite efficient in space requirement and pattern search time, but it is applicable only for an alignment of strings without gaps. In this paper we propose the FM-index of alignment with gaps, a realistic index for similar strings, which allows gaps in their alignment. For this, we design a new version of the suffix array of alignment by using an alignment transformation and a new definition of the alignment-suffix. The new suffix array of alignment enables us to support the LF-mapping and backward search, the key functionalities of the FM-index, regardless of gap existence in the alignment. We experimentally compared our index with RLCSA due to Mäkinen et al. and related indexes GCSA due to Sirén et al. and GCSA2 due to Sirén on genome sequences from the 1000 Genomes Project. The index size of our index is smaller than those of other indexes.

TCS Journal 2016 Journal Article

Abelian powers and repetitions in Sturmian words

• Gabriele Fici
• Alessio Langiu
• Thierry Lecroq
• Arnaud Lefebvre
• Filippo Mignosi
• Jarkko Peltomäki
• Élise Prieur-Gaston

Richomme, Saari and Zamboni (2011) [39] proved that at every position of a Sturmian word starts an abelian power of exponent k for every k > 0. We improve on this result by studying the maximum exponents of abelian powers and abelian repetitions (an abelian repetition is an analogue of a fractional power) in Sturmian words. We give a formula for computing the maximum exponent of an abelian power of abelian period m starting at a given position in any Sturmian word of rotation angle α. By considering all possible abelian periods m, we recover the result of Richomme, Saari and Zamboni. As an analogue of the critical exponent, we introduce the abelian critical exponent A ( s α ) of a Sturmian word s α of angle α as the quantity A ( s α ) = lim sup k m / m = lim sup k m ′ / m, where k m (resp. k m ′ ) denotes the maximum exponent of an abelian power (resp. of an abelian repetition) of abelian period m (the superior limits coincide for Sturmian words). We show that A ( s α ) equals the Lagrange constant of the number α. This yields a formula for computing A ( s α ) in terms of the partial quotients of the continued fraction expansion of α. Using this formula, we prove that A ( s α ) ≥ 5 and that the equality holds for the Fibonacci word. We further prove that A ( s α ) is finite if and only if α has bounded partial quotients, that is, if and only if s α is β-power-free for some real number β. Concerning the infinite Fibonacci word, we prove that: i) The longest prefix that is an abelian repetition of period F j, j > 1, has length F j ( F j + 1 + F j − 1 + 1 ) − 2 if j is even or F j ( F j + 1 + F j − 1 ) − 2 if j is odd, where F j is the jth Fibonacci number; ii) The minimum abelian period of any factor is a Fibonacci number. Further, we derive a formula for the minimum abelian periods of the finite Fibonacci words: we prove that for j ≥ 3 the Fibonacci word f j, of length F j, has minimum abelian period equal to F ⌊ j / 2 ⌋ if j = 0, 1, 2 mod 4 or to F 1 + ⌊ j / 2 ⌋ if j = 3 mod 4.

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.

TCS Journal 2016 Journal Article

Fast computation of abelian runs

• Gabriele Fici
• Tomasz Kociumaka
• Thierry Lecroq
• Arnaud Lefebvre
• Élise Prieur-Gaston

Given a word w and a Parikh vector P, an abelian run of period P in w is a maximal occurrence of a substring of w having abelian period P. Our main result is an online algorithm that, given a word w of length n over an alphabet of cardinality σ and a Parikh vector P, returns all the abelian runs of period P in w in time O ( n ) and space O ( σ + p ), where p is the norm of P, i. e. , the sum of its components. We also present an online algorithm that computes all the abelian runs with periods of norm p in w in time O ( n p ), for any given norm p. Finally, we give an O ( n 2 ) -time offline randomized algorithm for computing all the abelian runs of w. Its deterministic counterpart runs in O ( n 2 log ⁡ σ ) time.

TCS Journal 2016 Journal Article

FM-index of alignment: A compressed index for similar strings

• Joong Chae Na
• Hyunjoon Kim
• Heejin Park
• Thierry Lecroq
• Martine Léonard
• Laurent Mouchard
• Kunsoo Park

In this paper we propose the FM-index of alignment, a compressed index for similar strings with the functionalities of pattern search and random access. For this, we first design a new and improved version of the suffix array of alignment. The FM-index of alignment is an FM-index of this suffix array of alignment. The FM-index of alignment supports the LF-mapping and backward search, the key functionalities of the FM-index, but the LF-mapping and backward search of our index is significantly more involved than the original FM-index. We implemented the FM-index of alignment and did experiments on 100 genome sequences from the 1000 Genomes Project. The index size of the FM-index of alignment is about a half of that of RLCSA due to Mäkinen et al.

TCS Journal 2008 Journal Article

On-line construction of compact suffix vectors and maximal repeats

• Élise Prieur
• Thierry Lecroq

A suffix vector of a string is an index data structure equivalent to a suffix tree. It was first introduced by Monostori et al. in 2001 [K. Monostori, Efficient computational approach to identifying overlapping documents in large digital collections, Ph. D. Thesis, Monash University, 2002; K. Monostori, A. Zaslavsky, H. Schmidt, Suffix vector: Space-and-time-efficient alternative to suffix trees, in: CRPITS’02: Proceedings of the 25th Australasian Computer Science Conference, vol. 4, Darlinghurst, Australia, 2002, Australian Computer Society, Inc. pp 157–166; K. Monostori, A. Zaslavsky, I. Vajk, Suffix vector: A space-efficient suffix tree representation, in: P. Eades, T. Takaoka (Eds.), Proceedings of the 12th International Symposium on Algorithms and Computation, in: Lecture Notes in Computer Science, vol. 2223, Springer-Verlag, Berlin, 2001, pp. 707–718. Christchurch, New Zealand]. They proposed a linear construction algorithm of an extended suffix vector, then another linear algorithm to transform an extended suffix vector into a more space-economical compact suffix vector. We propose an on-line linear algorithm for directly constructing a compact suffix vector. Not only do we show that it is possible to directly build a compact suffix vector but we will also show that this on-line construction can be faster than the construction of the extended suffix vector. Then we formalize the relation between suffix vectors and compact suffix automata which leads to an efficient method for computing maximal repeats using suffix vectors.

TCS Journal 2004 Journal Article

Linear-time computation of local periods

• Jean-Pierre Duval
• Roman Kolpakov
• Gregory Kucherov
• Thierry Lecroq
• Arnaud Lefebvre

We present a linear-time algorithm for computing all local periods of a given word. This subsumes (but is substantially more powerful than) the computation of the (global) period of the word and on the other hand, the computation of a critical factorization, implied by the Critical Factorization Theorem.

MFCS Conference 2003 Conference Paper

Linear-Time Computation of Local Periods

• Jean-Pierre Duval
• Roman Kolpakov
• Gregory Kucherov
• Thierry Lecroq
• Arnaud Lefebvre

Abstract We present a linear-time algorithm for computing all local periods of a given word. This subsumes (but is substantially more powerful than) the computation of the (global) period of the word and on the other hand, the computation of a critical factorization, implied by the Critical Factorization Theorem.

TCS Journal 1992 Journal Article

A variation on the Boyer-Moore algorithm

• Thierry Lecroq