Maxime Crochemore

Lucian Ilie ⋆⋆2

Costas S Iliopoulos

Marcin Kubica

Wojciech Rytter

Tomasz Waleń

LPF computation revisited ⋆

Keywords: longest previous factor, suffix array, Ziv-Lempel factorisation, text compression, detection of repetitions

We present efficient algorithms for storing past segments of a text. They are computed using two previously computed read-only arrays (SUF and LCP) composing the Suffix Array of the text. They compute the maximal length of the previous factor (subword) occurring at each position of the text in a table called LPF. This notion is central both in many conservative text compression techniques and in the most efficient algorithms for detecting motifs and repetitions occurring in a text. The main results are: a linear-time algorithm that computes explicitly the permutation that transforms the LCP table into the LPF table; a time-space optimal computation of the LPF table; and an O(n log n) strong in-place computation of the LPF table.

Longest Previous Factor

We consider a string y of length n on the alphabet A: y = y[0 . . n -1]. The problem is to compute the Longest Previous Factor table defined, for 0 ≤ i < n, by LPF[i] = max{k | y[i . . i + k -1] occurs at a position j < i}.

For example, the text y = abaabababbabbb has the following LPF table. The problem may be regarded as an extension of the Ziv-Lempel factorisation (LZ77) of a string as defined in [START_REF] Ziv | A universal algorithm for sequential data compression[END_REF]. A string y is decomposed into factors, called phrases, u 0 , u 1 , . . . , u k , for which y = u 0 u 1 • • • u k and defined informally by: u i = va where a is a letter and v is the longest segment of u 0 u 1 • • • u i occurring both at position |u 0 u 1 • • • u i-1 | and before it in y. The factorisation is used in several adaptive compression methods which encode carefully re-occurrences of phrases by pointers or integers (see [START_REF] Storer | Data compression via textual substitution[END_REF] or [START_REF] Witten | Managing Gigabytes[END_REF]). The factorisation yields more powerful compressors than the factorisation in [START_REF] Ziv | Compression of individual sequences via variable-rate coding[END_REF] (called LZ78) where a phrase is an extension by a single letter of a previous phrase. But the LZ77 factorisation is more difficult to compute.

It is clear that the LZ77 factorisation comes readily when the LPF table is available, which is a remarkable application of the table (see [START_REF] Crochemore | A simple algorithm for computing the Lempel-Ziv factorization[END_REF]). This implies a linear-time solution for LZ77 factorisation on integer alphabets. Previous solutions using a Suffix Tree [START_REF] Rodeh | Linear algorithm for data compression via string matching[END_REF] or a Suffix Automaton [START_REF] Crochemore | Transducers and repetitions[END_REF] of the text not only run in time O(|y| log |A|) but these data structures are more space-expensive than the Suffix Array.

A slight variant of string parsing, whose relation with the LZ77 factorisation is analysed in [START_REF] Berstel | Crochemore factorization of Sturmian and other infinite words[END_REF], plays an important role in String Algorithms. The intuitive reason is that, when processing a string on-line, the work done on an element of the factorisation can usually be skipped because already done on one of its previous occurrences. A typical application of this idea resides in algorithms to compute repetitions in strings (see [START_REF] Crochemore | Transducers and repetitions[END_REF][START_REF] Main | Detecting leftmost maximal periodicities[END_REF][START_REF] Kolpakov | Finding maximal repetitions in a word in linear time[END_REF]). For example, the algorithm in [START_REF] Kolpakov | Finding maximal repetitions in a word in linear time[END_REF] reports all maximal repetitions (called runs) occurring in a string in O(|y| log |A|) time. It runs in linear time if a Suffix Array is used instead of a Suffix Tree [START_REF] Crochemore | Computing Longest Previous Factor in linear time and applications[END_REF]. Indeed the technique seems to be the only technique that leads to linear-time algorithms independently of the alphabet size for this type of question.

Suffix Arrays provide an ideal data structure to solve many questions requiring an index on all the factors of a string. Introduced by Manber and Myers [START_REF] Manber | Suffix arrays: a new method for on-line string searches[END_REF] the structure can be built in linear-time by different methods [START_REF] Kärkkäinen | Simple linear work suffix array construction[END_REF][START_REF] Kim | Linear-time construction of suffix arrays[END_REF][START_REF] Ko | Space efficient linear time construction of suffix arrays[END_REF][START_REF] Nong | Linear Time Suffix Array Construction Using D-Critical Substrings[END_REF] for sorting the suffixes of the text possibly adding the method of [START_REF] Kasai | Linear-time longestcommon-prefix computation in suffix arrays and its applications[END_REF] to compute the Longest Common Prefix table. The result holds if the text is drawn from an integer alphabet, that is, if the alphabet of the text can be sorted in linear time (otherwise the Ω(n log n) lower bound for sorting applies).

The notion of Longest Previous Factor has been introduced by Franek et al. as part of their concept of a Quasi Suffix Array (their π array is the LPF table) in [START_REF] Franek | Computing quasi suffix arrays[END_REF], where the authors presented a direct computation running in O(n log n) average time. A naive computation of the LPF table, either on the text itself or on its Suffix Array, as done by the algorithm LPF-naive in Section 5, leads to quadratic effective running time on many inputs.

In this article we intensively use the Suffix Array of the text to be processed, and we consider only linear-time solutions. A graphical representation of the Suffix Array structure helps understand the design of the algorithms. The Longest Previous Factor is coined in [START_REF] Crochemore | Computing Longest Previous Factor in linear time and applications[END_REF], where a linear-time computation is described and applied to LZ77 factorisation. Another version running on-line on the Suffix Array of the text and requiring only O( √ n) extra memory space is shown in [START_REF] Crochemore | A simple algorithm for computing the Lempel-Ziv factorization[END_REF].

We improve on the previous results and show that the computation of the Longest Previous Factor table of a text from its Suffix Array can be implemented to run in linear time with only a constant amount of additional memory space. Thus, the method is time-space optimal.

The next section introduces the necessary material for the design of Longest Previous Factor computations. First, an algorithm similar to the one in [START_REF] Crochemore | Computing Longest Previous Factor in linear time and applications[END_REF] is described. The algorithm is regarded in Section 3 as using the Suffix Array like a sorting network. Section 4 shows how the computation can be done on-line on the Suffix Array and Section 5 describes the time-space optimal algorithm for constructing the table.

Using a Suffix Array

The Suffix Array of the text y is a data structure used for indexing its content. It comprises two tables that we denote SUF and LCP and that are defined as follows.

The table SUF stores the list of position on y associated with the sorted list of its suffixes in increasing lexicographic order. That is, the table is such that

y[SUF[0] . . n -1] < y[SUF[1] . . n -1] < • • • < y[SUF[n -1] . . n -1].
Thus, indices on SUF are ranks of the suffixes in their sorted list.

The second table LCP is also indexed by the ranks of suffixes and stores the longest common prefixes between consecutive suffixes in the sorted list. Let lcp(i, j) = longest common prefix of y[i . . n -1] and y[j . . n -1], for two positions i and j on y. Then, LCP[0] = 0 and, for 0 < r < n, we set The computation of the Suffix Array of y can be done in time O(n log n) in the comparison model [START_REF] Manber | Suffix arrays: a new method for on-line string searches[END_REF] (see [START_REF] Crochemore | Algorithms on Strings[END_REF][START_REF] Crochemore | Jewels of Stringology[END_REF][START_REF] Gusfield | Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology[END_REF]). If the text is on an alphabet of integers in the range [0, n c ] for some constant c, the Suffix Array can be built in time O(n) [START_REF] Kärkkäinen | Simple linear work suffix array construction[END_REF][START_REF] Kim | Linear-time construction of suffix arrays[END_REF][START_REF] Ko | Space efficient linear time construction of suffix arrays[END_REF][START_REF] Nong | Linear Time Suffix Array Construction Using D-Critical Substrings[END_REF]] (see also [START_REF] Crochemore | Algorithms on Strings[END_REF]).

LCP[r] = |lcp(SUF[r -1], SUF[r])|.

Graphic representation

The Suffix Array of the text y has a nice graphic representation that helps understand the algorithms computing the LPF table. The abscissae axis refers to ranks of suffixes and the ordinates axis refers to their positions. The sorted list of suffixes is plotted by their positions, and consecutive positions are linked by an edge whose label is the associated LCP value. Figure 1 shows the Suffix Array representation for the text of Example 1.

Simple algorithm

The LCP table satisfies a simple property consequence of the lexicographic order: the LCP value between two positions at ranks r and t, r < t, is the minimal value in

LCP[r + 1 . . t].
For a rank r, let us define prev[r] as the largest rank s, s < r, for which SUF[s] < SUF[r] if it exists, and as -1 otherwise. Let us also define the dual notion next[r] as the smallest rank t, r < t, for which SUF[t] < SUF[r] if it exists, and as n otherwise. The above property implies that to compute LPF[SUF [r]] there is no need to look at ranks smaller than prev[r] or greater than next[r], that is

LPF[SUF[r]] = max{ |lcp(SUF[r], SUF[prev[r]])|, |lcp(SUF[r], SUF[next[r]])| } (1)
where undefined LCP values are set to 0. In particular, if a position i is a "peak" at rank r in the graphic representation of the Suffix Array (SUF[r] = i) we get

LPF[i] = max{LCP[r], LCP[r + 1]}.
And the minimum of the two values is the LCP between positions at ranks r -1 and r + 1 if defined. This gives the idea underlying the next algorithm.

Figure 2 illustrates a step of the algorithm when the input is the text of Example 1. The algorithm LPF-simple computes the two tables prev and next, which implement indeed a double-linked list of ranks. The algorithm runs in linear time but requires several extra arrays in addition to its input and output. Namely, the array ISU, inverse of SUF, that provides the rank of a position, and the two arrays prev and next. LPF-simple(SUF, LCP, n)

1 LCP-copy ← LCP 2 LCP-copy[n] ← 0 3 ISU ← inverse SUF 4 for r ← 0 to n -1 do 5 prev[r] ← r -1 6 next[r] ← r + 1 7 for i ← n -1 downto 0 do 8 r ← ISU[i] 9 LPF[i] ← max{LCP-copy[r], LCP-copy[next[r]]} 10 LCP-copy[next[r]] ← min{LCP-copy[r], LCP-copy[next[r]]} 11 if prev[r] ≥ 0 then 12 next[prev[r]] ← next[r] 13 if next[r] < n then 14 prev[next[r]] ← prev[r] 15 return LPF Proposition 1.
The algorithm LPF-simple computes the LPF array of a text of length n from its Suffix Array in linear time and space. It requires 3n + c integer cells in addition to its input and output.

The array next can alternatively be pre-computed by the following procedure whose linear-time behaviour is an interesting exercise left to the reader. The procedure also computes the array LPF > defined in [START_REF] Crochemore | Computing Longest Previous Factor in linear time and applications[END_REF] and that accounts for larger ranks only. It is defined, for r = 0, . . . , n -1, by

LPF > [r] = |lcp(SUF[r], SUF[next[r]])|. Next(SUF, LCP, n) 1 next[n -1] ← n 2 LPF > [n -1] ← 0 3 for r ← n -2 downto 0 do 4 t ← r + 1 5 ℓ ← LCP[t] 6 while t < n and SUF[t] > SUF[r] do 7 ℓ ← min{ℓ, LPF > [t]} 8 t ← next[t] 9 next[r] ← t 10 LPF > [r] ← ℓ 11 return next, LPF >
The computation of the dual prev and LPF < arrays is done symmetrically. When both arrays LPF < and LPF > are available, the computation of the LPF table is an application of identity 1 that rewrites, for position i at rank r, as

LPF[i] = max(LPF > [r], LPF < [r]).

Sorting network

It has been noticed in [START_REF] Crochemore | Computing Longest Previous Factor in linear time and applications[END_REF] that the content of the LPF table is the same as that of the LCP table up to some permutation. A question arises then: what permutation is it? Does it depend on the text, its Suffix Array or maybe just its LCP array? It turns out that, for fixed SUF and LCP arrays, it does not depend on the actual text. It is possible to construct such a sorting network, whose shape depends only on the Suffix Array, that transforms the LCP array into the LPF table. This observation leads to the algorithm LPF-sorting, producing LPF by permutating the elements of LCP.

In the algorithm LPF-sorting below we assume that the table next introduced in the previous section has been pre-computed by the procedure Next (in which instructions related to LPF > are useless and may be removed, as well as the parameter LCP). Table next is used to compute, for each position i, the next closest position nextp[i] in the Suffix Array that is smaller than i, that is,

nextp[SUF[r]] = SUF[min{t | t > r and SUF[t] < SUF[r]}].
Initially, the LPF table is a copy of the LCP array permuted according to the SUF table. The algorithm sorts the array by permuting its elements to get the LPF table.

LPF-sorting(SUF, LCP, n)

1

SUF[n] ← -1 2 for r ← 0 to n -1 do 3 LPF[SUF[r]] ← LCP[r] 4 nextp[SUF[r]] ← SUF[next[r]] 5 for i ← n -1 downto 0 do 6 if (nextp[i] ≥ 0) and (LPF[i] < LPF[nextp[i]]) then 7 Exchange(LPF[i], LPF[nextp[i]]) 8 return LPF
Note that the elements of LPF are exchanged (lines 6-7) only if they are not in increasing order. Which elements are compared, depends on values in nextp, and this in turn depends only on the Suffix Array. So, for a given Suffix Array, one can construct a sorting network implementing lines 5-7 of the algorithm LPF-sorting. Hence, the following proposition holds: Proposition 2. For a given Suffix Array of a text, there exists a sorting network processing a sequence of n numbers in such a way that it transforms the LCP table into the LPF table. Moreover, the shape of the sorting network depends only on the Suffix Array, but not on its LCP table nor on the actual text.

As it is done for any sorting procedure, instead of directly computing the LPF table, the algorithm LPF-sorting can equivalently produce explicitly the permutation π to transform the LCP array into the LPF table, that is, the permutation that satisfies

LPF[i] = LCP[π[i]].
The algorithm LPF-sorting uses only one integer array in addition to its input and output since the next table it uses is substituted for the nextp table. This yields the next statement. Proposition 3. The algorithm LPF-sorting computes the LPF table of a text of length n from its Suffix Array in linear time and space. It requires n+c integer cells in addition to its input and output.

On-line computation

Techniques of the previous sections to compute the LPF table are simple but space consuming. In this section and the next one we address this issue. We show that a computation on-line on the Suffix Array using a stack reduces the memory space to only O( √ n) for a text of length n.

The design of the on-line computation still relies on the property used for the algorithm of Section 2 and related to "peaks" (see lines 6-8 below). It relies additionally on another straightforward property that we describe now. Assume that a position SUF Note that lines 15 to 18 may be removed from the algorithm LPF-on-line if the Suffix Array can be extended to rank n and initialised to SUF[n] = -1 and LCP[n] = 0. But we prefer the present design that is compatible with the algorithm of the next section.

LPF-on-line(SUF, LCP, n)

1 EmptyStack(S)

2 for r ← 0 to n -1 do 3 r-lcp ← LCP[

Stack size

The extra memory space used by the algorithm LPF-on-line to compute the LPF table of a text is occupied by the stack and a constant number of integer variables. To evaluate the total size required by the algorithm it is then important to determine the maximal size of the stack for a text of length n. It is proved in [START_REF] Crochemore | A simple algorithm for computing the Lempel-Ziv factorization[END_REF]

that this quantity is O( √ n).
For most values of n there are plenty of texts for which the stack reaches its maximal size. But if n is of the form k(k + 1)/2, that is, if it is the sum of the first k positive integers, then there is a unique string on the alphabet {a, b} (with a < b) giving the maximal size stack. This word is aabab 2 • • • ab k-1 and the maximal stack size is k.

The next table shows maximal stack sizes for texts of lengths In this section we show that the computation of the LPF table of a text can be implemented with only constant memory space in addition to the Suffix Array of the text and its LPF table. The underlying property used for this purpose is the O( √ n) stack size reported in the previous section. The property allows an implementation of the stack inside the LPF table for a sufficiently large part of the text. The rest of the computation for the remaining positions is done in a more time-expensive manner but for a small part of the text. This preserves the linear running time of the whole computation.

LPF-optimal(SUF, LCP, n)

1 ⊲ it is assumed that n ≥ 8 2 K ← ⌊n -2 √ 2n⌋ 3 ⊲ next three procedures share the same LPF table 4 LPF-on-line(SUF, LCP, K) 5 LPF-naive(SUF, LCP, K, n) 6 LPF-anchored(SUF, LCP, K, n) 7 return LPF
It is rather clear that only constant extra memory space is required to implement the strategy retained by the algorithm LPF-optimal. The choice of the parameter K is a result of the previous section and is done to let enough space in the LPF array to implement the stack used by the algorithm LPF-on-line.

Although not done here, the choice of the parameter K can be dynamic and done during the algorithm LPF-on-line as n -2k -1, where k is the size of the stack just before executing line 15. This certainly reduces the actual running time but does not improve its asymptotic evaluation.

In the algorithm LPF-optimal, the stack of the procedure LPF-on-line is implemented in the LPF table. Access to the table is done via the SUF array. Doing so, the stack is treated like a continuous space LPF[SUF[K . . n -1]]. Elements are stored sequentially so that the elementary stack operations (empty, top, push, pop) are all executed in constant time. Therefore, the running time of the first step is O(n) (indeed O(K)) as for the algorithm LPF-on-line.

]] of the table stores the content of the stack: ((1, 0), (4, 2), (5, 3)). Row (ii) shows that values have already been computed for positions at ranks 0 to 6. The content of the stack is ((7, 0), (8, 2)). On this example, K could have been set dynamically to 5.

Naive computation

The second step of the algorithm LPF-optimal processes the Suffix Array from rank K. For each rank r, the values prev[r], next[r] and the corresponding LCP values are computed starting from r and going backward and forward, respectively. The code is given below for the sake of completeness but it contains no algorithmic high value.

The process takes O(n -K) time per rank, and hence the total running time of the step is O(

(n -K) 2 ), which is O(n) since K = n -2 √ 2n. LPF-naive(SUF, LCP, K, n) 1 LCP[n] ← 0 2 for r ← K to n -1 do 3 left ← LCP[r] 4 s ← r -1 5 while s ≥ K and SUF[s] > SUF[r] do 6 left ← min{left , LCP[s]} 7 s ← s -1 8 if s = K -1 then 9 left ← 0 10 t ← r + 1 11 right ← LCP[t] 12 while t < n and SUF[t] > SUF[r] do 13 t ← t + 1 14 right ← min{right , LCP[t]} 15 LPF[SUF[r]] ← max{left, right } 16 return LPF
Completing the computation The first two steps of the algorithm LPF-optimal process independently two segments of the Suffix Array. The last step consists in joining their results, which requires updating some LPF values. Indeed, for a rank r, r < K, next[r] can be in [K, n-1], which implies that the computation of LPF[SUF[r]] might not be achieved. The same phenomenon happens for a rank in the second part, whose associated prev rank is smaller than K.

The next algorithm updates all LPF values and completes the whole computation. It assumes that the LPF calculation has been done independently on parts LPF[SUF[0 . . K -1]] and LPF[SUF[K . . n-1]] of the array, which is realised by the first two steps on the algorithm LPF-optimal.

The running time of this last step LPF-anchored is obviously linear, O(n), as are the other steps of the algorithm LPF-optimal.

The first conclusion of the section is the following statement. The algorithm LPF-optimal uses the Suffix Array of the input text in a read-only manner but does not use the LPF table in a write-only manner. If this last condition is to be satisfied, the question remains of whether there exists a linear-time LPF table construction running with constant extra space. We get this feature if the algorithm LPF-anchored is applied recursively by dividing the Suffix Array into two equal parts. The running time becomes O(n log n) in the model of computation allowing priority writes.

Theorem 2. The Longest Previous Factor table of a text of length n on an integer alphabet can be built from its read-only Suffix Array in time O(n log n) (independently of the alphabet size) with a constant amount of extra memory space and with a write-only output.

Despite the use of the output as auxiliary storage in the ultimate linear-time algorithm, the series of algorithms described in the article provide a large range of efficient solutions that meet many practical needs.

(Example 1 .

 1 The actual Suffix Array contains indeed about n additional LCP values used for binary searching the suffixes.) For the text y = abaabababbabbb we get the Suffix Array:

Fig. 1 .

 1 Fig. 1. Graph of the permutation of positions on abaabababbabbb (Example 1) in the lexicographic order of its suffixes. Labels of edges are Longest Common Prefix lengths between consecutive suffixes.

Fig. 2 .

 2 Fig.2. Illustration of the run of the algorithm LPF-simple on the text abaabababbabbb (see Figure1) after processing positions 13, 12, 11, 10. Gray positions and gray edges are no longer considered. The next step is to process position 9 at rank 10. According to the weights of edges pending from 9, we have LPF[START_REF] Gusfield | Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology[END_REF] = max{4, 1} = 4. Positions 6 and 8 will be linked, through the prev and next arrays on their ranks, with an edge of weight min{4, 1} = 1, which is indeed LPF[START_REF] Nong | Linear Time Suffix Array Construction Using D-Critical Substrings[END_REF].

  [r] at rank r satisfies LCP[r] ≥ LCP[r + 1]. Then, no position after it in the list can provide a larger LCP value and therefore we get LPF[SUF[r]] = LCP[r]. This is implemented in lines 10-11 of the algorithm LPF-on-line.

Proposition 4 .

 4 The algorithm LPF-on-line computes the LPF array of a text of length n from its Suffix Array in linear time and O( √ n) space. It requires less than 2 √ 2n + c integer cells in addition to its input and output.

Example 2 .

 2 The next table shows the content of the LPF array at two stages of the run of the procedure LPF-on-line on Example 1: (i) immediately after processing rank 5 and (ii) at the end of the first step. shows that LPF values of positions 2, 3, 5 at respective ranks 0, 2, 3 have already been computed. The part LPF[SUF[8 . .

  Theorem 1. The Longest Previous Factor table of a text of length n on an integer alphabet can be built from its Suffix Array in time O(n) (independently of the alphabet size) with a constant amount of extra memory space.

	LPF-anchored(SUF, LCP, K, n)
	1 s ← K -1 2 t ← K 3 ℓ ← LCP[K] 4 while (s ≥ 0) and (t < n) do 5 ⊲ invariant: ℓ = min LCP[s + 1, . . . , r]
	6	if SUF[s] < SUF[t] then
	7 8 9 10 11 12 13 return LPF LPF[SUF[t]] ← max{LPF[SUF[t]], ℓ} t ← t + 1 ℓ ← min{ℓ, LCP[t]} else LPF[SUF[s]] ← max{LPF[SUF[s]], ℓ} ℓ ← min{ℓ, LCP[s]} s ← s -1

Acknowledgements

Authors warmly thank German Tischler for his careful inspection of the algorithms described in the article.

⋆ Research supported in part by the Royal Society, UK. ⋆⋆ Research supported in part by NSERC. ⋆ ⋆ ⋆ Supported by grant N206 004 32/0806 of the Polish Ministry of Science and Higher Education.


Maxime Crochemore
email: maxime.crochemore@kcl.ac.uk

Lucian Ilie
email: ilie@csd.uwo.ca

Wojciech Rytter
email: rytter@mimuw.edu.pl

Repetitions in strings: algorithms and combinatorics

Keywords: Repetitions, squares, cubes, runs, consecutive repeats, tandem repeats, compression, factorisation, algorithms

The article is an overview of basic issues related to repetitions in strings, concentrating on algorithmic and combinatorial aspects. This area is important both from theoretical and practical point of view. Repetitions are highly periodic factors (substrings) in strings and are related to periodicities, regularities, and compression. The repetitive structure of strings leads to higher compression rates, and conversely, some compression techniques are at the core of fast algorithms for detecting repetitions. There are several types of repetitions in strings: squares, cubes, and maximal repetitions also called runs. For these repetitions, we distinguish between the factors (sometimes qualified as distinct) and their occurrences (also called positioned factors). The combinatorics of repetitions is a very intricate area, full of open problems. For example we know that the number of (distinct) primitively-rooted squares in a string of length n is no more than 2n -Θ(log n), conjecture to be n, and that their number of occurrences can be Θ(n log n). Similarly we know that there are at most 1.029 n and at least 0.944 n maximal repetitions and the conjecture is again that the exact bound is n. We know almost everything about the repetitions in Sturmian words, but despite the simplicity of these words, the results are nontrivial. One of the main motivations for writing this text is the development during the last couple of years of new techniques and results about repetitions. We report both the progress which has been achieved and which we expect to happen.

Introduction

Repetitions and periods in strings constitute one of the most fundamental areas of string combinatorics. They have been studied already in the papers of Axel Thue [START_REF] Thue | Über unendliche Zeichenreihen[END_REF], considered as having founded stringology. While Thue was interested in finding long sequences with few repetitions, in recent times a lot of attention has been devoted to the algorithmic side of the problem.

Periods are ubiquitous in string and pattern matching algorithms. Knuth-Morris-Pratt string-matching algorithm uses the border table of the pattern, which is equivalent to using the periods of all its prefixes. Periods are implicitly computed when preprocessing the pattern in the as well famous Boyer-Moore algorithm (see [START_REF] Crochemore | Algorithms on Strings[END_REF][START_REF] Gusfield | Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology[END_REF]). The basic reason why periods show up in this question is that stuttering is likely to slow down any string-matching algorithm. The analysis of periods is even more important in constant-space optimal pattern matching algorithms because the only information on the patterns that is precomputed and stored is related to global and local periods of the pattern: perfect factorisation [START_REF] Galil | Time-space-optimal string matching[END_REF], critical factorisation [START_REF] Crochemore | Two-way string matching[END_REF], or sampling method [START_REF] Gasieniec | Constant-space string matching with smaller number of comparisons: sequential sampling[END_REF]. By the way, the difficulties in extending string-matching techniques to image pattern matching methods are essentially due to different and more complex structures of 2D-periodicities.

Periodicities and repetitions in strings have been extensively studied and are important both in theory and practice. The strings of the type ww and www, where w is a nonempty string, are called squares and cubes, respectively. They are well investigated objects in combinatorics of strings [START_REF] Lothaire | Algebraic Combinatorics on words[END_REF] and in stringmatching with small memory [START_REF] Crochemore | Squares, cubes, and time-space efficient string searching[END_REF].

Detecting repetitions in strings is an important element of several questions: pattern matching, text compression, and computational biology to quote a few. Pattern matching algorithms have to cope with repetitions to be efficient as these are likely to slow down the process; the large family of dictionarybased text compression methods (see [START_REF] Witten | Managing Gigabytes[END_REF]) use a weaker notion of repeats (like the software gzip); repetitions in genomes, called satellites or Simple Sequence Repeats, are intensively studied because, for example, some overrepeated short segments are related to genetic diseases [START_REF] Macdonald | A novel gene containing a trinucleotide repeat that is expanded and unstable on Huntington's disease chromosomes[END_REF]; some satellites are also used in forensic crime investigations.

In this survey, we recall some of the most significant achievements in the area over the past three decades or so, as well as point out several central open questions. We focus on algorithms for finding repetitions and, as a key component, on counting various types of repetitions. The main results concern fast if not optimal algorithms for computing squares occurrences and runs, as well as combinatorial estimation on the number of the corresponding objects. Section 2 is devoted to properties of squares, Section 3 to that of runs, and finally the last two sections investigates repetitions in Fibonacci words and in Sturmian words.

Squares

Let A be an alphabet of size a and A * the set of all finite strings over A. We denote by |w| the length of a string or word w, its ith letter by w[i], and its factor (substring)

w[i]w[i + 1] . . . w[j] by w[i . . j]. Note that w = w[1 . . |w|]. We say that w has period p if w[i] = w[i + p], for all i, 1 ≤ i ≤ |w| -p.
The period of w is its smallest period and is denoted by period(w). The ratio between the length and the period of w is called the exponent of w. The string u is said to be periodic if period(u

) ≤ |u|/2. A repetition in w is an interval [i . . j] ⊆ [1 .
. |w|] for which the associated factor w[i . . j] is periodic. It is an occurrence of a periodic string w[i . . j], sometimes called a positioned repetition in the literature. A string can contain many repetitions, see Figure 3.

In the following, we analyse squares in a string x of length n.

The simplest but most investigated type of repetition is the square. A square is a string of the form ww, where w is nonempty. Indeed, to avoid counting redundant elements, the root w of the square is assumed to be primitive, that is, it is not itself the power of another string. This is equivalent to say that the exponent of ww is 2. Note that the same square may appear several times in the same string and then we talk about square occurrences or equivalently positioned squares. As we shall see, counting distinct squares, i.e. squares that are distinct strings, or squares occurrences gives very different results.

Square occurrences

Initially people investigated mostly squares occurrences, but their number can be as high as Θ(n log n) [START_REF] Crochemore | An optimal algorithm for computing the repetitions in a string[END_REF], hence algorithms computing all of them cannot run in linear time, due to the potential size of the output. Indeed the same result holds for any type of repetition having an integer exponent greater than 1 [START_REF] Crochemore | Bounds on powers in strings[END_REF]. The optimal algorithms reporting all positioned squares or just a single In this case none of the strings u, v, w is primitive.

square were designed in [START_REF] Crochemore | An optimal algorithm for computing the repetitions in a string[END_REF][START_REF] Apostolico | Optimal off-line detection of repetitions in a string[END_REF][START_REF] Main | An O(n log n) algorithm for finding all repetitions in a string[END_REF][START_REF] Crochemore | Transducers and repetitions[END_REF].

Theorem 1 (Crochemore [START_REF] Crochemore | An optimal algorithm for computing the repetitions in a string[END_REF], Apostolico-Preparata [START_REF] Apostolico | Optimal off-line detection of repetitions in a string[END_REF], Main-Lorentz [START_REF] Main | An O(n log n) algorithm for finding all repetitions in a string[END_REF])

There exists an O(n log n) worst-case time algorithm for computing all the occurrences of primitively-rooted squares in a string of length n.

Techniques used to design the algorithms are based on partitioning, suffix trees, and naming segments, respectively. A similar result has been obtained by Franek, Smyth, and Tang using suffix arrays [START_REF] Franek | Computing all repeats using suffix arrays[END_REF]. The key component of the algorithm of Theorem 3 is the function described in the following lemma. We say that an occurrence of a square ww in uv is centred in

u (resp. v) if its position i satisfies i + |w| < |u| (resp. i + |w| ≥ |u|).
Lemma 2 (Main-Lorentz [START_REF] Main | An O(n log n) algorithm for finding all repetitions in a string[END_REF]) Given two square-free strings u and v, reporting if uv contains a square centred in u can be done in worst-case time O(|u|).

Using suffix trees or suffix automata together with the function derived from the lemma, the following fact has been shown.

Theorem 3 (Crochemore [START_REF] Crochemore | Transducers and repetitions[END_REF], Main-Lorentz [START_REF] Main | An O(n log n) algorithm for finding all repetitions in a string[END_REF]) Testing if a string of length n is square-free can be done in worst-case time O(n log a), where a is the size of the alphabet of the string.

Another interesting result concerning periodicities is the following lemma and its fairly immediate corollary.

Lemma 4 (Three Square Prefixes, Crochemore-Rytter [START_REF] Crochemore | Squares, cubes, and time-space efficient string searching[END_REF]) If u, v, and w are three strings such that u is primitive, uu is a proper prefix of vv, and vv is a proper prefix of ww, then |u| + |v| ≤ |w|.

A couple of proofs of this important lemma, different from the original, were given. A short one appears in [33, page 281]. A very simple proof of a slightly weaker result, where 2|u| < |w|, is given in [34, page 433]. We recall here the simplest such proof, due to Ilie [START_REF] Ilie | A simple proof that a string of length n has at most 2n distinct squares[END_REF], which yields two results: a weaker version of Lemma 4 (2|u| < |w| if any of the three strings is assumed primitive) and Corollary 2 below. For the former, assume 2|u| ≥ |w|; see Figure 1 where

u i = u, 1 ≤ i ≤ 3. Set u -1 v = x p with x primitive.
The overlap between u 1 and u 2 gives that u = x r x ′ , for a prefix x ′ of x. Synchronisation of primitive powers of x in u 3 with those in u 2 and the suffix x p of v implies that x ′ is empty and hence none of u, v, and w is primitive, a contradiction.

A fairly immediate consequence of Lemma 4 is the next corollary.

Corollary 1 Any nonempty string of length n possesses less than log Φ n prefixes that are squares, where Φ is the golden mean (1 + √ 5)/2.

Distinct squares

Unlike their number of occurrences discussed above, it is known that only O(n) (distinct) squares can appear in a string of length n [START_REF] Fraenkel | How many squares can a string contain?[END_REF].

In the configuration of Lemma 4, a second consequence is that uu is a prefix of w. Therefore, a position in a string x cannot be the largest (rightmost) position of more than two squares, which yields the next corollary. As mentioned earlier, a simple proof of it, bypassing Lemma 4 and due to Ilie [START_REF] Ilie | A simple proof that a string of length n has at most 2n distinct squares[END_REF], is illustrated by Figure 1. If three squares u 2 , v 2 , and w 2 start at the same position, then the shortest of those, u 2 appears again later. Indeed, this is obvious if 2|u| ≤ |w|.

Otherwise, u 2 appears again |x| positions later. Therefore, at most two squares can have their last (rightmost) occurrences starting at the same position. The claim follows.

Corollary 2 (Fraenkel and Simpson [START_REF] Fraenkel | How many squares can a string contain?[END_REF]) Any string of length n contains at most 2n (distinct) squares.

The structure of all squares and of unpositioned runs has been also computed within the running time O(n log a) in [START_REF] Main | Detecting leftmost maximal periodicities[END_REF] and [START_REF] Gusfield | Linear time algorithms for finding and representing all the tandem repeats in a string[END_REF].

Based on numerical evidence, it has been conjectured that the number of (distinct) squares in a string of length n is at most n. The best bound to date, 2n -Θ(log n), was given in [START_REF] Ilie | A note on the number of squares in a string[END_REF].

Proving the conjecture is probably difficult due to the following example from [START_REF] Fraenkel | How many squares can a string contain?[END_REF]. Consider the family of strings w m = m i=1 0 i+1 10 i 10 i+1 1, for all m ≥ 1 ( denotes the concatenation). Then, the length of w m is |w m | = 3 2 m 2 + 13 2 m and the number of squares it contains is very close to it:

3 2 m 2 + 4m -3 + odd(m) 2 , that is, |w m | -o(|w m |).
Figure 2 displays w 4 and the last occurrences of all its squares. It is interesting to note that, although the string has many squares, this bottom sequence contains very few 2's. 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 1

Runs

The concept of maximal repetitions, called runs in [START_REF] Iliopoulos | A characterization of the squares in a Fibonacci string[END_REF], has been introduced to represent all repetitions in a succinct manner. The crucial property of runs is that there are only O(n) many of them in a string of length n [START_REF] Kolpakov | Finding maximal repetitions in a string in linear time[END_REF][START_REF] Rytter | The Number of Runs in a String: Improved Analysis of the Linear Upper Bound[END_REF][START_REF] Crochemore | Analysis of maximal repetitions in strings[END_REF][START_REF] Puglisi | How many runs can a string contain?[END_REF].

A run in a string w is an interval [i . . j] such that both the associated string w[i . . j] has period p ≤ (j -i + 1)/2, and the periodicity cannot be extended to the right nor to the left:

w[i -1] = w[x + p -1] and w[j -p + 1] = w[j + 1]
when these elements are defined. When the period p of a run is known, we call it a p-run. An example is displayed in Figure 3.

As a consequence of the algorithms and of the estimation on the number of squares, the most important result related to repetitions in strings can be formulated as follows.

Theorem 5 , Rytter [START_REF] Rytter | The Number of Runs in a String: Improved Analysis of the Linear Upper Bound[END_REF], Crochemore-Ilie [START_REF] Crochemore | Analysis of maximal repetitions in strings[END_REF]) (i) All runs in a string of length n over an alphabet of size a can be computed in time O(n log a). (ii) The number of all runs is linear in the length of the string.

The point (ii) is very intricate and of purely combinatorial nature. The algorithm for (i) executes in time proportional to the number of runs (on a fixed-size alphabet) which, by (ii), is linear. Indeed, with an reasonable hypothesis on the alphabet, the running time of (i) can be reduced to O(n) as stated in Theorem 6 below.

Let ρ(n) be the maximal number of runs in a string of length n. By item (ii) we have ρ(n) < cn for some constant c. Based on the results in Table 1, Kolpakov and Kucherov [START_REF] Kolpakov | Finding maximal repetitions in a string in linear time[END_REF] conjectured that c = 1 for binary alphabets. A stronger conjecture was proposed in [START_REF] Franek | An asymptotic Lower Bound for the Maximal Number of Runs in a String[END_REF] where a family of strings is given with the number of runs equal to 3 2Φ = 0.927 . . . (Φ is the golden ratio), thus proving c ≥ 0.927 . . .. The authors of [START_REF] Franek | An asymptotic Lower Bound for the Maximal Number of Runs in a String[END_REF] conjectured that this bound is optimal, but the best known lower bound for c has been shown to be 0.944 more recently by Matsubara et al. [START_REF] Matsubara | New Lower Bounds for the Maximum Number of Runs in a string[END_REF]. Some reasons which might indicate that the optimal bound may be less than n are discussed in Section 6.

Computing runs

Next, we sketch shortly the basic components of the proof of the point (i) of Theorem 5. The main idea is to use, as for the previous Theorem 3, the f-factorisation of the input string 4 (see [START_REF] Crochemore | Transducers and repetitions[END_REF]): a string w is decomposed into factors u 1 , u 2 , . . . , u k , where u i is the longest segment which appears before its position in w, i.e. in u 1 u 2 . . . u i A -1 , possibly with overlapping the present occurrence of u i ; if the segment is empty u i is a single letter (see Figure 4).

The runs which fit in a single factor of the f-factorisation are called internal runs, other runs are called here overlapping runs. Figure 4 shows the f-factorisation and the internal runs of an example string.

There are three crucial facts:

• all overlapping runs can be computed in linear time,

• each internal run is a copy of an earlier overlapping run,

• the f-factorisation can be computed in linear time under some hypothesis on the alphabet of the string (see Theorem 6 below).

It follows easily from the definition of the f-factorisation that if a run overlaps two (consecutive) factors u k-1 and u k then its size is at most twice the total size of these two factors.

p u k-1 u k p Fig. 5. If an overlapping run with period p starts in u k-1 , ends in u k , and its part in u k-1 is of size at least p, then it is easily detectable by computing continuations of the period p in the two directions, left and right.

Figure 5 shows the basic idea for computing runs that overlap u k-1 and

u k in time O(|u k-1 | + |u k |).
Using similar tables as in the Morris-Pratt algorithm (border and prefix tables, see [START_REF] Crochemore | Algorithms on Strings[END_REF][START_REF] Crochemore | Jewels of stringology[END_REF]) we can test the continuation of a period p, to the left and to the right. The corresponding tables can be constructed in linear time in a preprocessing phase.

After computing all overlapping runs the internal runs can be copied from their earlier occurrences by processing the string from left to right. Recall that, by (ii), there are only linearly many.

The above process is offline and computing all runs in linear time online, i.e. sequentially while reading the input string, is an open question. This might be of great interest when processing streams of data.

The f-factorisation of a string is commonly computed with the suffix tree or the suffix automaton of the string. When the alphabet of the string has a fixed size thanks to the efficient algorithms for building these data structures, the whole process can be carried on in linear time. Two recent algorithms, due to [START_REF] Crochemore | Computing longest previous factors in linear time and applications[END_REF] and [START_REF] Chen | Fast and practical algorithms for computing all runs in a string[END_REF] (see also [START_REF] Crochemore | A simple algorithm for computing the Lempel-Ziv factorization[END_REF]), use the suffix array of the string to provide linear-time algorithms for integer alphabets. The hypothesis means that the alphabet of the string of length n is in the interval [0, n d ], for some constant d, which implies that letters can be sorted in linear time.

Theorem 6 (Crochemore-Ilie [START_REF] Crochemore | Computing longest previous factors in linear time and applications[END_REF], Chen-Puglisi-Smyth [START_REF] Chen | Fast and practical algorithms for computing all runs in a string[END_REF]) On an integer alphabet, the f-factorisation of a string and its runs can be computed in linear time.

Counting runs

The most intriguing question remains the asymptotically tight bound for the maximum number of runs ρ(n) in a string of length n. The first proof (by painful induction) was quite difficult and has not produced any concrete constant coefficient in the O(n) notation. This subject has been studied in [START_REF] Franek | An asymptotic Lower Bound for the Maximal Number of Runs in a String[END_REF][START_REF] Fraenkel | The Exact Number of Squares in Fibonacci strings[END_REF][START_REF] Smyth | Repetitive perhaps, but certainly not boring[END_REF][START_REF] Smyth | Computing patterns in strings[END_REF]. The exact number of runs has been considered for special types of strings (see Sections mian strings [START_REF] Franek | Repetitions in Sturmian strings[END_REF][START_REF] Iliopoulos | A characterization of the squares in a Fibonacci string[END_REF][START_REF] Rytter | The Number of Runs in a String: Improved Analysis of the Linear Upper Bound[END_REF]. The best-known lower bound of approximately 0.944 n is from [START_REF] Matsubara | New Lower Bounds for the Maximum Number of Runs in a string[END_REF]. 5 Figure 6 gives a sample of string containing many runs.

The first explicit upper bound for general strings was given by Rytter [START_REF] Rytter | The Number of Runs in a String: Improved Analysis of the Linear Upper Bound[END_REF], that is, ρ(n) ≤ 5n, and improved in a structural and intricate manner in [START_REF] Rytter | The number of runs in a string[END_REF], ρ(n) ≤ 3.44 n, by introducing a sparse-neighbour technique. Another improvement of the ideas of [START_REF] Rytter | The Number of Runs in a String: Improved Analysis of the Linear Upper Bound[END_REF] was done in [START_REF] Puglisi | How many runs can a string contain?[END_REF] where the bound 3.48 n is obtained. The neighbours are runs for which both the distance between their starting positions is small and the difference between their periods is also proportionally small according to some fixed coefficient of proportionality. The occurrences of neighbours satisfy certain sparsity properties which imply the linear upper bound. Several variations for the definitions of neighbours and sparsity are possible. Considering runs having close centres (the beginning position of the second period) the bound has been lowered to 1.6 n in [START_REF] Crochemore | Analysis of maximal repetitions in strings[END_REF][START_REF] Crochemore | Maximal repetitions in strings[END_REF], improved to 1.52 n in [START_REF] Giraud | Not so many runs in strings[END_REF], and further to 1.029 n as a result of computations (see [START_REF] Crochemore | Towards a solution to the "runs" conjecture[END_REF]). 6It is interesting to note that the approach of [START_REF] Crochemore | Analysis of maximal repetitions in strings[END_REF][START_REF] Crochemore | Maximal repetitions in strings[END_REF] is somewhat counterintuitive. On the one hand, Corollary 1 states that there can be only logarithmically many runs starting at the same position and this is how they are counted in [START_REF] Rytter | The Number of Runs in a String: Improved Analysis of the Linear Upper Bound[END_REF]; see Figure 7 for an example. On the other hand, there can be linearly many runs with the same centre, see the example in Figure 8, and still counting them this way in [START_REF] Crochemore | Analysis of maximal repetitions in strings[END_REF][START_REF] Crochemore | Maximal repetitions in strings[END_REF] yields a better bound. This is essentially due to the fact that many runs with the same centre implies strong local periodicities in the string, thus eliminating many other potential runs.

The structure of runs in Fibonacci words

The structure of runs is well understood for the class of Fibonacci words. Let us denote by f n the n-th Fibonacci word (f 0 is the empty word, f 1 = b, f 2 = a, and Property (i) shows in particular that the asymptotic ratio of runs in Fibonacci words is (Φ is the golden mean

f n = f n-1 f n-2 for n > 2), by F n = |f n | the nth
(1 + √ 5)/2) lim n→∞ 2 F n-2 -3 |f n | = 2 1 + Φ ≈ 0.76.
In fact we can compute the number of p-runs for a specific period p. We say that the p-run w is short if |w| < 3p, and long otherwise. Let also g n be the n-th Fibonacci word f n with the last two letters removed. We have:

Lemma 8 Every run of F ∞ with a period larger than two is of one of the two types: either a short β-run, i.e. of the form

β k = f 2 k-1 g k-2
, or a long α-run, i.e. of the form α k = f 3 k-2 g k-3 , for some integer k.

An immediate corollary follows from the structure of runs.

Corollary 3 (Karhumäki [START_REF] Karhumäki | On strongly cube-free ω-words generated by binary morphisms[END_REF]) There is no nonempty factor of the form w 4 in the infinite Fibonacci word F ∞ .

Indeed, it appears that maximal-exponent repetitions in F ∞ correspond to long α-runs. Their exponent, for a given k, is then:

|α k | period(α k ) = |f 3 k-2 g k-3 | |f k-2 | = 3F k-2 + F k-3 -2 F k-2 = F k-1 -2 F k-2 + 2 ,
whose limit is:

lim k→∞ F k-1 -2 F k-2 + 2 = Φ + 2 .
Therefore, if we define the repetition order of the (finite or infinite) string x, we get the stronger following corollary (see [START_REF] Lothaire | Algebraic Combinatorics on words[END_REF]Chapter 8]).

Corollary 4 (Mignosi-Pirillo [START_REF] Mignosi | Repetitions in the Fibonacci infinite word[END_REF]) The repetition order of the infinite Fibonacci word

F ∞ is rep(F ∞ ) = Φ + 2.
Counting runs occurring in Fibonacci words by their period yields the next result illustrated by Figure 9. This provides an alternative proof for the number of all runs in Fibonacci words.

Theorem 9 (Rytter [START_REF] Rytter | The structure of subword graphs and suffix trees of Fibonacci words[END_REF]) The Fibonacci word f n , n ≥ 6, contains F n-3 1-runs, F n-4 -1 2-runs, and F n-k F k -runs for any k satisfying 4 ≤ k ≤ n -2.

Maximal repetitions in Sturmian words

The standard Sturmian words are generalization of Fibonacci words and similarly as Fibonacci words are described by recurrences. We denote by S the class of standard Sturmian words.

The recurrence for a standard word is related to its so-called directive sequence: an integer sequence of the form γ = (γ 0 , γ 1 , . . . , γ n ), where γ 0 ≥ 0 and γ i > 0 for 0 < i ≤ n. The standard word corresponding to γ, denoted by S(γ) = x n+1 , is defined by the recurrence relations:

x -1 = b, x 0 = a, x 1 = x γ 0 0 x -1 , x 2 = x γ 1 1 x 0 , x 3 = x γ 2 2 x 1 , . . . , x n = x γ n-1
n-1 x n-2 , x n+1 = x γn n x n-1 For example, a Fibonacci word is generated by a directive sequence of the form (1, 1, . . . , 1).

The number N = |x n+1 | is the (real) length of the word, while n can be thought as its compressed size. It happens that N can be exponential with respect to n, and computations on the word in time O(n) are often rather nontrivial.

To state the next result, we introduce a zero-one function, called unary, for testing if its argument equals 1: if x = 1 then unary(x) = 1 else unary(x) = 0.

We also denote by |x| a the number of occurrences of letter a in the word u. The next statement gives a precise count of the number of runs in a Sturmian word.

Theorem 10 (Baturo-Piatkowski-Rytter [START_REF] Baturo | The number of runs in Sturmian words[END_REF]) Let γ = (γ 0 , . . . , γ n ) be the directive sequence and n ≥ 3. Then the number of runs in S(γ) equals:

ρ(S(γ)) =                    2 A + 2 B + ∆(γ) -1 if γ 0 = γ 1 = 1 (γ 1 + 2) A + B + ∆(γ) -odd(n) if γ 0 = 1; γ 1 > 1 2A + 3B + ∆(γ) -even(n) if γ 0 > 1; γ 1 = 1 (2 γ 1 + 1) A + 2 B + ∆(γ) Otherwise where A = |S(γ 2 , γ 3 . . . , γ n )| a , B = |S(γ 3 , γ 4 . . . , γ n )| a ∆(γ) = n -1 -(γ 1 + . . . + γ n ) -unary(γ n ).
The theorem yields the two next corollaries by the same authors.

Corollary 6

Counting the number of runs in the standard Sturmian word S(γ 0 , . . . , γ n ) can be achieved in time O(n).

Conclusion and further research

One of the main motivations for writing this text was the development during the last couple of years of new techniques and results about repetitions. In this survey, we reported both the progress which has been achieved and which we expect to happen. We recalled some of the most significant achievements, as well as pointed out several central open questions, like the conjectures on the maximal number of (distinct) squares occurring in a string and the maximal number of runs. We focused on algorithms for finding repetitions and, as a key component, on counting various types of repetitions.

Although the Kolpakov and Kucherov's conjecture on the maximum number of runs in a string is still unsolved, from the practical point of view of the analysis of algorithms depending on this number, its very tight approximation is largely sufficient. A possible research track to attack the question is to study the compressibility of run-rich strings in addition to their combinatorial properties.

Aside from the above-mentioned open questions, we discuss here several other related problems.

Distinct runs. Inspired by the square problem, we may look at the strings associate with runs and count only the number of runs associated with different strings. Notice that the number of nonequivalent runs and that of squares do not seem to be obviously related to each other. The same run may contain several distinct squares (e.g., ababa contains the squares abab and baba) but we can have also distinct runs corresponding to a single square (e.g., aa and aaa are distinct runs but only the square aa is involved).

(2 + ε) + -repetitions. A way to weaken the conjecture on the number of squares is to increase the exponent of the repetition. Given a non-negative ε, one could count only the number of repetitions of exponent 2+ε or higher. We need first to make it precise what we are talking about. We count primitivelyrooted repetitions of exponent at least 2 + ε and having distinct roots. That is, x α and y β , x and y primitive, α ≥ 2 + ε, β ≥ 2 + ε, are different if and only if x = y.

This conjecture might be easier to prove. At least for 2 + ε = 1 + Φ (where Φ is the golden ratio) we can prove it immediately. We count each square at the position where its rightmost occurrence starts and show that no two distinct squares can have the same rightmost starting position. Assume x 1+Φ is a prefix of y 1+Φ and denote |x| = p < q = |y|. Then necessarily |x 1+Φ | = (1 + Φ)p > Φq = |y Φ | as otherwise x 1+Φ would have another occurrence to the right. That means Φ 2 p = (1 + Φ)p > Φq, or Φp > q. Therefore, the overlap between the two runs has the length |x 1+Φ | = (1 + Φ)p = p + Φp > p + q. By Fine and Wilf's lemma, this means x and y are powers of the same string and therefore not primitive, a contradiction.

(2 -ε) + -repetitions. This is similar to the previous problem except that now we consider repetitions of exponent 2 -ε or higher. Is the number of such maximal repetitions still linear? If this is false for any ε > 0, then 2 is the optimal threshold. Otherwise, the optimal threshold needs to be found.

Fig. 1 .

 1 Fig.1. Three squares that are prefixes of each other: u 2 < v 2 < w 2 with |w| ≤ 2|u|. In this case none of the strings u, v, w is primitive.

Fig. 2 .Fig. 3 .

 23 Fig.2. The string w 4 = 0 2 10 1 10 2 1 0 3 10 2 10 3 1 0 4 10 3 10 4 1 0 5 10 4 10 5 1 contains many squares. The rightmost occurrence of each square is displayed. The numbers in the bottom sequence give the number of squares whose rightmost occurrence starts at that position.

a b b a b a a b a b b a b a a b a b a a b aFig. 4 .

 4 Fig. 4. The f-factorisation of the string baababaababbabaababaab of Figure 3 and the set of its internal runs; all other runs overlap factorisation points.

Fig. 6 .Fig. 7 .Fig. 8 .

 678 Fig. 6. This string of length 116 contains 99 runs (99/116 > 0.85). It has 27 1-runs, 26 2-runs, 27 3-runs, 6 5-runs, 5 8-runs, 6 13-runs, 1 21-run, and the whole string is a 55-run. b a a b a a b a a b a b a a b a a b a b a a b a b a a b a a b a a

  Fibonacci number, and by F ∞ the infinite Fibonacci word. Kolpakov and Kucherov (see [34, Chapter 8]) have shown the following two properties of runs occurring in Fibonacci words. Theorem 7 (Kolpakov-Kucherov [34]) (i) There are exactly 2F n-2 -3 runs in the n-th Fibonacci word f n . (ii) The sum of exponents of runs in Fibonacci words is hF n + o(n), where 1.922 ≤ h ≤ 1.926.

Fig. 9 .

 9 Fig. 9. The structure of runs in the Fibonacci word F 11 . The arrows show endpoints of its prefixes which are the Fibonacci words f 4 , f 5 , . . . , f 11 . The string contains 65 runs. There are 21 = F 8 1-runs (occurrences of aa), 12 = F 7 -1 2-runs, 13 = F 7 3-runs, 8 = F 6 5-runs, 5 = F 5 8-runs, 3 = F 4 13-runs, 2 = F 3 21-runs, and 1 = F 2 34-run. denoted by rep(x), as rep(x) = sup{|w|/period(w) | w is a finite factor of x},

  ρ(w) ≤ 4 5 |w| for each w ∈ S (b) Let w k = S(1, 2, k, k). Then lim k→∞ ρ(w k ) |w k | = 4 5 .

Table 1

 1 Maximum number of runs in binary strings of length n, 5 ≤ n ≤ 31 (from[START_REF] Kolpakov | Finding maximal repetitions in a string in linear time[END_REF]).

	n	5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
	runs 2 3 4 5 5 6 7 8 8 10 10 11 12 13 14 15 15 16 17 18 19 20 21 22 23 24 25

This factorisation plays an important role in data compression algorithms and has many other applications. Its combinatorial properties have been investigated in[START_REF] Berstel | Crochemore factorization of Sturmian and other infinite strings[END_REF] and[START_REF] Constantinescu | The Lempel-Ziv complexity of fixed points of morphisms[END_REF]; see the latter for a number of open problems.

See the Web page http://www.shino.ecei.tohoku.ac.jp/runs/.

See the Web page http://www.csd.uwo.ca/∼ilie/runs.html for the results of latest computations.

 [START_REF] Apostolico | Optimal off-line detection of repetitions in a string[END_REF]Research partially supported by CNRS. 2 Research partially supported by NSERC. 3 Research partially supported by the grant of the Polish Ministry of Science Higher Education N206 004 32/0806.


Vincent Bismuth
email: vincent.bismuth@med.ge.com

Hugues Talbot

Régis Vaillant

Laurent Najman

Curvilinear structure enhancement with the polygonal path image -Application to

Keywords: pdfcreator=HAL, pdfproducer=PDFLaTeX, pdfsubject=Computer Science [cs]/Signal and Image Processing, Engineering Sciences [physics]/Signal and Image processing, Computer Science [cs]/Medical Imaging curvilinear structures, image segmentation, shortest path

come

,

Introduction

Curvilinear structures appear naturally in the human body and thus in medical images. Their segmentation is a specific but extensively studied topic that covers a wide variety of naturally elongated biological structures and medical tools: vascular and cerebral structures and interventional tools like catheters, guide-wires, etc. In this paper, we propose a locally shortest path technique for the processing of curvilinear structures. The proposed technique associates a generalization of several state of the art techniques, an intuitive parameterization, and an efficient computational scheme. We illustrate its performance for the difficult task of guide-wire segmentation in X-ray fluoroscopy. We propose quantified results on clinical data and comparison with other state of the art techniques.

Background

2.1 Guide-wire detection in X-ray fluoroscopy Interventional radiology/cardiology therapies imply inserting guide-wires into the vascular system of patients under the monitoring of X-ray video, called fluoroscopy. Such procedures are minimally invasive and have been used increasingly often in recent years, in areas ranging from coronary angioplasty to tumor embolization. Over the past years, guide-wire detection in fluoroscopic images has gained interest and maturity among the image processing community [START_REF] Franken | Detection of electrophysiology catheters in noisy fluoroscopy images[END_REF][START_REF] Bismuth | A comparison of line enhancement techniques: applications to guide-wire detection and respiratory motion tracking[END_REF][START_REF] Barbu | Hierarchical learning of curves application to guidewire localization in fluoroscopy[END_REF][START_REF] Honnorat | Guide-wire extraction through perceptual organization of local segments in fluoroscopic images[END_REF]. A large number of applications rely upon its characteristics, such as visualization enhancement, 3D guide-wire reconstruction and respiratory motion tracking. In X-ray images, guide-wires appear as thin, dark curves (see Fig. 1 (a)). The challenge in their detection arises from their low contrast to noise ratio and the superposition with disturbing clutter and anatomical structures.

State of the art

Curvilinear structure segmentation techniques and particularly guide-wire detection in X-ray fluoroscopy is often presented as a 3-step pipeline: [START_REF] Franken | Detection of electrophysiology catheters in noisy fluoroscopy images[END_REF] The local building of a feature map representing the probability of presence of an elongated structure at each pixel [START_REF] Bismuth | A comparison of line enhancement techniques: applications to guide-wire detection and respiratory motion tracking[END_REF][START_REF] Barbu | Hierarchical learning of curves application to guidewire localization in fluoroscopy[END_REF][START_REF] Honnorat | Guide-wire extraction through perceptual organization of local segments in fluoroscopic images[END_REF][START_REF] Frangi | Multiscale vessel enhancement filtering[END_REF][START_REF] Meijering | Design and validation of a tool for neurite tracing and analysis in fluorescence microscopy images[END_REF]. Its computation often involves considering the neighborhood of each pixel, on which structures are assumed to be straight. (2) A semi-local feature map reinforcement, typically enhancing responses aligned along a pattern -e.g. 2 nd order, circle or parabola [START_REF] Franken | Detection of electrophysiology catheters in noisy fluoroscopy images[END_REF], or tensor voting and coherence enhancing diffusion. (3) A global structure segmentation. At this stage, simple operators like thresholding are generally not sufficient, and a higher level process is invoked to segment the feature map. It may involve grouping [START_REF] Barbu | Hierarchical learning of curves application to guidewire localization in fluoroscopy[END_REF][START_REF] Honnorat | Guide-wire extraction through perceptual organization of local segments in fluoroscopic images[END_REF] or tracking [START_REF] Meijering | Design and validation of a tool for neurite tracing and analysis in fluorescence microscopy images[END_REF]. However some techniques, like locally shortest paths [START_REF] Vincent | Minimal path algorithms for the robust detection of linear features in gray images[END_REF] and geodesic path voting [START_REF] Rouchdy | Image segmentation by geodesic voting. application to the extraction of tree structures from confocal microscope images[END_REF] are exceptions to this framework. They discard complex curve models (linear, 2 nd order etc.) instead relying on the concept of path. Locally shortest paths associate a locally optimal path to every pixel and use the cost of such paths for segmentation. Geodesic path voting relies on a starting point on the structure to segment from which a set of shortest paths are computed to a large number of automatically determined endpoints in the image. The geodesic density (number of paths passing through a pixel) is used to enhance lines.

Method

The polygonal path image

Presentation: As noted above, most line enhancement techniques select at each pixel a curve that best fits locally following a model: line segment, 2 nd order model or "arbitrary" smooth curves. We propose a single tunable model that generalizes these steps. Our local curve model is a path, that is characterized by length, and smoothness. Our aim is still to select at each pixel a best-fitting curve of given smoothness and length. However, instead of assigning to each pixel a measure associated to a local curve fitting, we propose to use the whole set of locally fitted curves over the image to derive more comprehensive line enhancement techniques. The smoothness of the paths is controlled by considering regular polygonal paths defined by two parameters: a total arclength L and a length l of every line segment. These two parameters have a simple intuitive meaning and are set according to the properties of the structure to enhance. The polygonal constraint is a generalization of the classical local path approach [START_REF] Vincent | Minimal path algorithms for the robust detection of linear features in gray images[END_REF] (for l = 1) enabling the encoding of the a-priori tortuosity of the structures to detect. From a higher level perspective, L is equivalent to the steps of the previous section. Indeed a single segment in the polygon is equivalent to the local step (i.e. segment matching). Considering a few segments is like semi-local processing, reinforcing the aligned responses of the local step. Finally a large number of segments takes into account long paths as in the global step.

Definition of P:

We consider a potential image I of strictly positive values, with structures of interest exhibiting lower values. For each pixel p ∈ I, Φ p is a set of admissible paths. We assign to each such path P ∈ Φ p a cost J(P) that is the sum of the values of I along P (Eq. 1). The path yielding the lowest cost in Φ p is denoted the locally optimal path P * p at pixel p (Eq. 2). The set of admissible paths is defined by some constraints: Paths shall be regular polygonal lines of given length L, and shall have controlled curvature: at each pixel the path shall be included inside a cone of given orientation and aperture [START_REF] Vincent | Minimal path algorithms for the robust detection of linear features in gray images[END_REF]. These constraints enforce locality, the smoothness that is often expected in medical images, and basically defines a search range around each pixel. We call the "polygonal path image" (noted P) the structure that contains a path and its cost for each pixel.

J(P) = p∈I I(p).1 P (p) (1) P * p = argmin P∈Φ L p J(P) (2)
Complexity: The computation of P with a brute force approach has exponential complexity with regard to L: O(Lk L ). Computing all the locally optimal paths in the image for n polygonal segments before considering the optimal paths of n + 1 segments, allows us to achieve linear complexity O(L) by adapting the original algorithm of Vincent [START_REF] Vincent | Minimal path algorithms for the robust detection of linear features in gray images[END_REF]. This makes it possible to consider P with long paths (e.g. one hundred pixels). For example, it takes approximately 10s to process a 512 2 image with such long paths. In terms of memory, we require the initial image times the number of polygon segments to store the paths.

Structure of the path image

Some paths originating from random locations on a clinical image are shown on Fig. 1 (b). We note that paths tend to converge into bundles around the main linear structures, where the cost in the potential image is lower. Those originating outside of the linear structures take the shortest possible way to reach them. Those that start directly on linear structures stay on them until the end or until paths constraints are exceeded. High path density is thus characteristic of the linear structures. Also, the set of paths intersecting at a pixel convey some local geometry information on the linear structures. Fig. 1 (c) illustrates paths intersecting at a point on the guide-wire. We observe (i) a high number of paths crossing at this point -nearly 11 000 in this case (ii) that they are aligned with the guide-wire in a small neighborhood around the considered pixel.

Image processing with P

Path voting: We observed that paths form bundles around the main linear structures. Therefore we propose that each minimal path vote for all the pixels it passes through, to reinforce path overlapping. This approach is similar to that of Carlotto [START_REF] Carlotto | Enhancement of low-contrast curvilinear features in imagery[END_REF] and to geodesic voting [START_REF] Rouchdy | Image segmentation by geodesic voting. application to the extraction of tree structures from confocal microscope images[END_REF], which also perform voting on sets of paths. Several voting schemes are possible: e.g. each vote can count the same, which is equivalent to counting the number of paths intersecting at one pixel (we note the resulting image ϑ(P) -Eq. 3), or each vote can be weighted (with a value denoted ϑ w (P) -Eq. 4). We can also restrict voting to the paths that meet some a priori criteria, e.g. preventing very tortuous paths from voting. Such paths occur in parts of the image were there is little relevant linear structure and close to high contrast objects. To this end, we define a tortuosity metric τ to penalize abrupt changes in direction, i.e. 0 for a path with a change of π/2 rad and 1 for a perfectly straight path. τ (P) is given by Eq. 5 (where V(k) is the vector formed by two consecutive vertexes of P). The operation of voting with a path smoothness constraint is denoted ϑ τmin (P). Its result is illustrated in Fig. 2 (b). Pruning in P: Another way exploiting the structure of the path image is to prune paths so as to select only a small set of relevant and non-redundant locally optimal paths. To do so, we define a neighborhood relationship between paths based on the partial Hausdorff distance. Then, we select the path of minimal cost in P and prune all the neighboring paths. We iterate this process in a greedy fashion, selecting the path of minimal cost again and pruning its neighbors, until there is no more path in P or some stopping criterion is reached. The remaining set of paths (typically less than 100) describes the linear features in the image (see Fig. 2 (c)).

ϑ(P) = p∈I 1 Pp (3) ϑ w (P) = - p∈I w(p)1 Pp (4) τ (P) = 1 l 2(n-2) n-2 k=1 V(k).V(k + 1) (5) ϑ τmin (P) = p∈I τ (Pp)>τmin 1 Pp ( 6
) (a) (b) (c) (d) (e)

Estimating local orientation:

We have illustrated in Fig. 1 that, when they reach a linear structure, paths tend to follow and align with it. Therefore the set of paths intersecting at a pixel on a curvilinear structure can be used to derive its orientation (an angle in [0, π[). Outside of the curvilinear structures the paths follow the shortest path leading to a linear structure. Their direction thus indicates the shortest path to line-like structures. To estimate it, let us consider at a given pixel p, the set of the paths {P i } intersecting at p. For each of these paths, we compute the tangent unit vector at point p: {t i }. Then we find the unit vector v p yielding the maximal sum of scalar products with the {t i }. This method is illustrated in Fig. 2 (d,e).

Evaluating and comparing line enhancement methods

To quantify the performance of our line enhancement techniques, we use ROC analysis to characterize their ability to assign larger values to the pixels of the structure of interest rather than to the background pixels. The Area Under the ROC Curve (AUC) is an estimate of the probability that a classifier will rank a randomly chosen pixel of the structure higher than a randomly chosen pixel of the background. When the number of background pixels far exceeds the number of pixels of the structure of interest, the computation of the AUC can be restricted to the low false positive rate range, in our case [0, 5%]. We normalize the AUC by the range, i.e. 5% here. In this context a random guess would yield a performance of only 2.5% and a perfect detector 100%. This metric is denoted the "partial AUC". In order to illustrate further the performance of the method we compute the false positive rate for a fixed true positive rate of 90%. Obviously, the better the method, the lower this metric. To compute these metrics, a trained operator manually defined ground truth T for each image, representing the centerline of the structure. We denote by D the set of points detected in an image for a given threshold. In order to take into account the real width of the curvilinear structure, we define true positives as the pixels of T that lie closer to D than a pre-defined distance d (typically the radius of the guide-wire). False positives are defined as the detected pixels that lie further from T than d. To make our results unbiased w.r.t. the line-width parameter of the line enhancement techniques, we skeletonize the detected pixels before computing the detection rates. Finally, in order not to corrupt our assessment of line enhancement techniques with the presence of other interventional tools or similar curvilinear structures we also compute the metrics associated to false positives in an ROI around the marked truth.

Results

Our clinical case database consists of 12 clinical sequences of 9 images each, for a total of 108 images. These images depict angioplasty exams with the injection catheter, the guide-wire, the angioplasty balloon, the anatomical background, and occasionally, stents and sternal wires. We compared our technique to two state of the art line enhancement techniques : Frangi's Vesselness [START_REF] Frangi | Multiscale vessel enhancement filtering[END_REF] and Rotated Filter Bank (RFB) [START_REF] Bismuth | A comparison of line enhancement techniques: applications to guide-wire detection and respiratory motion tracking[END_REF]. They were found in several recent publications [START_REF] Bismuth | A comparison of line enhancement techniques: applications to guide-wire detection and respiratory motion tracking[END_REF][START_REF] Tankyevych | Filtering of thin objects: applications to vascular image analysis[END_REF] to constitute the current state of the art for methods that compute in each pixel the probability to lie in a linear structure. Note that we are aware of dedicated methods for guide-wire segmentation that return a high level object describing the guide-wire [START_REF] Barbu | Hierarchical learning of curves application to guidewire localization in fluoroscopy[END_REF][START_REF] Honnorat | Guide-wire extraction through perceptual organization of local segments in fluoroscopic images[END_REF]. However, these methods typically rely on low-level descriptors, and so can benefit from the type of work we present here. We hand-optimized the set of parameters for each technique independently. Regarding Vesselness, we set α and β to the values proposed in Frangi's article [START_REF] Frangi | Multiscale vessel enhancement filtering[END_REF]. The scale factor σ was set to 2 pixel: the approximate guide-wire radius. For the RFB we relied on a study [START_REF] Tankyevych | Filtering of thin objects: applications to vascular image analysis[END_REF] that concluded that a length of 61 and a width of 3 pixels was optimal for this application. For ϑ(P) and ϑ τmin (P), we set : l = 21, L = 210, τ min = 0.6. The potential image on which the path costs are computed was obtained with a simple morphological dark top-hat. We computed the mean (AUC µ ) and standard deviation (AUC σ ) of the AUC over the database and the FPR for a given TPR of 90%. We report them graphically in Fig. 3. We observe that the line enhancement techniques derived from P performed significantly better. This is exemplified by greater AUR values and lower FPR. The local descriptors RFB and Vesselness performed similarly, within a few percents whereas P achieves more than twice their performance.

In order to illustrate the performance of the different techniques, we selected an optimal threshold that minimizes the sum of the missed detection rate and the false detection rate. We illustrate the thresholded images obtained with the four methods in Fig. 3. The outcomes are well aligned with the conclusions driven from the partial AUC: P based methods perform significantly better. We observe that the results are generally speaking quite satisfactory: most of the guide-wire is segmented, and only a few false positives remain in the background. We can observe how the smoothness constraints in ϑ τmin (P) removes some anatomical false positives that yield tortuous paths. However two problems remain: Over the whole database, the guide-wire tip, which is very contrasted attracts too many paths (creating false positives in its vicinity) and is too tortuous to be accurately fitted by our detector with the same setting as the guide-wire body -It must be detected separately. Secondly, some linear structures are detected in the background that are not guide-wires. Since they satisfy all the properties that we selected for guide-wires, a higher level processing, based on other criteria can handle them. For instance the presence of a tip is very characteristic of the guide-wire, as well as the motion that animates it. We have presented a new curvilinear structure processing scheme, the polygonal path image. We have demonstrated its suitability for the task of guide-wire detection in X-ray fluoroscopy. We showed that P has several interesting properties: (i) the ability to control the smoothness and length of the structures to be analyzed, (ii) a unification of local, semi local, and global curvilinear structure analysis in a single framework and (iii) an efficient computational scheme. This structure is a rich descriptor of the curvilinear structures present in images from which we derived several tools: line enhancement, segmentation and direction field computation techniques. We have demonstrated the relevance of polygonal path voting schemes for guide-wire segmentation quantitatively in the ROC analysis formalism and compared it to state of the art techniques. Future work may include some natural extensions of the usage/construction of P, including enhancement and segmentation operators on the path image and the quantitative evaluation of the direction fields and of path pruning. Regarding guide-wire segmentation, P is a new approach to the problem that yields significant improvement over state of the art methods. We plan to study in the near future the incorporation of P into a complete guide-wire segmentation algorithm.

Fig. 1 .

 1 Fig. 1. (a) X-ray fluoroscopy image from an angioplasty exam illustrating a guide-wire, with a long smooth curve appearance and low contrast to noise ratio. (b): 500 locally optimal paths originating from random locations. Observe their tendency to converge to the linear structures of the image and especially to the guide-wire. (c,d) The set of paths intersecting at one given point (belonging to the guide-wire, in (c), and to the background in (d), in this case the point is indicated by the dark spot).

Fig. 2 .

 2 Fig. 2. (a) Dark top-hat of Fig. 1 (a), used as potential image. (b) Result of ϑτ min =0.6. Despite a low CNR the guide-wire is significantly enhanced. (c) Path pruning with x = 50% and τmin = 0.75. Observe how the conjunction of pruning and constrained path smoothness help segment the guide-wire. (d) Close-up on a guide-wire segment in Fig. 1 (a) overlaid with the directions extracted from P. They indicate the direction of the closest curvilinear structure. On the structure itself the direction of the arrow is not relevant, but the orientation is accurate. (e) Same direction field overlaid on ϑτ min .

Fig. 3 .

 3 Fig. 3. Top : Performance of the four line enhancement techniques over our database.From left to right: AUC results, the height of the columns is AUCµ and the error bars represent mean AUCµ ± AUCσ. FPR for TPR= 90%. In both graphs the red series is computed over the whole image and the blue one only inside the ROI. The ROI used for FP is a band around the ground truth (see right image). Bottom rows: 2 result examples for optimal thresholds. From left to right : input image, ground truth, Vesselness, RFB, ϑ(P) and ϑτ min (P). Observe that traditional methods enhance a large amount of non relevant structures in the background and fail to enhance some parts of the guide-wire. These problems are not present with ϑτ min (P). Note these are the exact results of the techniques, no pruning has been performed for the P based methods.