Nadia El-Mabrouk

Maxime Crochemore

Boyer-Moore strategy to e cient approximate string matching

We propose a simple but e cient algorithm for searching all occurrences of a pattern or a class of patterns (length m) in a text (length n) with at most k mismatches. This algorithm relies on the Shift-Add algorithm of Baeza-Yates and Gonnet 6], which involves representing by a bit number the current state of the search and uses the ability of programming languages to handle bit words. State representation should not, therefore, exceeds the word size !, that is, m(dlog 2 (k + 1)e + 1) !. This algorithm consists in a preprocessing step and a searching step. It is linear and performs 3n operations during the searching step. Notions of shift and character skip found in the Boyer-Moore (BM) 9] approach, are introduced in this algorithm. Provided that the considered alphabet is large enough (compared to the Pattern length), the average number of operations performed by our algorithm during the searching step becomes n(2 + k+4 m k ).

Introduction

Our purpose is approximate matching of a pattern or a class of patterns in a text, all sequences of characters or classes of characters from a nite alphabet . Errors considered here are mismatches. A class of patterns, is a set of patterns with don't care symbols, patterns containing the complementary of a character or any other class of characters. Such a problem has a lot of applications, in particular in molecular biology for predicting potential nuclear gene-coding sequences in genomic DNA sequences. In fact, exact string matching is not su cient since gene-coding sequences are in general only partially and approximately speci ed.

Concerning exact string matching, algorithms based on the Boyer-Moore (BM) [START_REF] Boyer | A fast string searching algorithm[END_REF][START_REF] Knuth | Fast pattern matching in strings[END_REF] approach are the fastest in practice. Such algorithms are linear and may even have a sublinear behaviour, in the sense that every character in the text need not be checked. In certain cases, text characters can be \skipped" without missing a pattern occurrence. The larger the alphabet and the longer the pattern, the faster the algorithm works.

Various algorithms have been developed for searching with k mismatches all occurrences of a pattern (length m) in a text (length n), both de ned over an alphabet (length c). Running times have ranged from O(mn) for the naive algorithm, to O(kn) [START_REF] Landau | E cient string matching with k mismatches[END_REF][START_REF] Galil | Improved string matching with k mismatches[END_REF] or O(n log m) 12]. The rst two algorithms consist in a preprocessing step and a searching step. Grossi and Luccio algorithm 12] uses the su x tree. Other algorithms have used the BM approach in approximate string matching [START_REF] Baeza-Yates | Fast string matching with k mismatches[END_REF][START_REF] Tarhio | Boyer-moore approach to approximate string matching[END_REF]. Running times are O(kn) for Baeza-Yates and Gonnet 4] and O(kn( 1 m k + k c )) for Tarhio and Ukkonen 18]. The problem of approximate matching of a class of patterns was also studied 2, 1, 5], especially in the case of patterns with don't care symbols [START_REF] Fischer | String-matching and other products[END_REF][START_REF] Pinter | E cient string matching whith don't-care patterns[END_REF][START_REF] Manber | An algorithm for string matching with a sequence of don't cares[END_REF][START_REF] Akutsu | Approximate string matching with don't care characters[END_REF][START_REF] Bertossiand | Parallel string matching with variable length don't cares[END_REF][START_REF] Kucherov | Matching a set of strings with variable length don't cares[END_REF]. Fisher et Paterson 10] developed an O(n log c log 2 m log log m) time algorithm based on the linear product. Abrahamson 1] extended this method for generalized string pattern. Pinter 17] has used the Aho and Corasick automaton 2] for searching a set of patterns. Other algorithms have considered the problem of exact matching of patterns with variable length don't cares [START_REF] Manber | An algorithm for string matching with a sequence of don't cares[END_REF][START_REF] Bertossiand | Parallel string matching with variable length don't cares[END_REF][START_REF] Kucherov | Matching a set of strings with variable length don't cares[END_REF]. As for Akutsu 3], he developed an O( p km n log c log 2 m k log log m k ) time algorithm for searching a pattern with don't cares in a text with don't cares.

In 1992, several new algorithms for approximate string matching were published [START_REF] Baeza-Yates | A new approach to text searching[END_REF][START_REF] Wu | Fast text searching allowing errors[END_REF][START_REF] Baeza-Yates | Fast and practical approximate string matching[END_REF]. They combine both speed and programming practicality, in contrast with older results, most of which being mainly of theoretical interest. Moreover, they are exible enough to allow searching for a class of patterns. These algorithms consist in a pattern preprocessing step and a searching step. They are all based on the same approach, consisting in nding, at a given position in the text, all approximate pattern pre xes ending at this position. Speed is increased by representing the state of the search as a bit number 6, 19] or an array 7], and by using the ability of programming languages to handle bit words.

Nevertheless, these algorithms are based on a naive approach and process each character of the text. Our goal is to speed up searching by using a BM strategy and including notions of shift and character skip.

We have chosen to consider such an improvement in the case of the Shift-Add algorithm of Baeza-Yates and Gonnet 6]. The main idea of Shift-Add is to represent the state of the search as a bit number, and perform a few simple arithmetic and logical operations. Provided that representations don't exceed the word size !, that is m(dlog 2 (k + 1)e + 1) !, each search step does exactly a shift, a test and an addition. Therefore, this algorithm runs in O(n) time and the searching step does 3n operations. We developed an algorithm combining the practicality of the Shift-Add method and the speed of the BM approach. Provided that the considered alphabet is large enough compared to m, our new algorithm performs on average n 2 + k+4 m k operations during the searching step.

The paper is organized as follows. Section 2 summarises the algorithm Shift-Add, in the case of exact or approximate matching of a pattern or a class of patterns. Section 3 develops the adaptation of the BM approach to the Shift-Add method. An improvement of this last algorithm is given in Section 4. Finally, section 5 gives experimental results obtained with both algorithms.

2 Shift-Add Algorithm Let P = p 1 p m be a pattern and t = t 1 t n be a text over a nite alphabet . The problem is to nd in t all occurrences of P with at most k mismatches (0 k m). In other words, the distance between two patterns of the same length will be de ned as the number of their mismatching characters (the Hamming distance). An equivalent problem is then to nd in t all substrings of length m such that the Hamming distance between these substrings and P is at most k, that is to nd all j positions in the text such that, for 1 i m, p i = t j m+i , except for at most k indices.

The main idea is to represent the state of the search as a vector of size m. Thus, S j denotes the state vector given a current position j in the text. S j contains individual states of the search between each pre x of P and the corresponding substring of t. Namely, for 1 i m, S j i] is the number of mismatches between p 1 p i and t j i+1 t j .

P matches at j if and only if S j m] < k + 1. When t j+1 is read, the number of mismatches for each pre x of P needs to be completed. Values of boolean expressions t j+1 = p i , for 1 i m, can be computed during a preprocessing step. For each character a in , a vector T a of size m is constructed such that :

For i, 1 i m, T a i] = 0 if a = p i 1 otherwise

(1)

(it is su cient to construct the T arrays only for characters appearing in the pattern).

Finally, S j+1 i] = S j i 1] + T tj+1 i].

In order to obtain S j+1 from S j by simple arithmetic and logical operations, vectors are considered as numbers and represented in base 2 b , where b is the bit number needed to represent each vector component.

Thus, S j = m X i=1 S j i]2 (i 1)b and T a = m X i=1 T a i]2 (i 1)b . Representations should not exceed the word size !, namely, mb !. It is easy now to verify that the transition from S j to S j+1 amounts to no more than a left shift (denoted by <<) of b bits and an addition : S j+1 = (S j << b) + T tj+1 (2) Initial state is S 0 = 0. P matches at j if and only if S j < (k + 1)2 (m 1)b . Possible values of the vector state components are 1; ; m. Thus, to represent each component, b = dlog 2 (m + 1)e bits are required. However, since we need only to compare the number of mismatches with k, it is enough to represent values from 1 to k. In this case, one more bit is needed for carrying over additions. The improved algorithm uses b = dlog 2 (k + 1)e + 1 bits. At each position j in the text, the over ow bits are recorded in an over ow state R j and the over ow bits of S j are reset.

The Shift-Add algorithm works in O(n) time, and the searching step (disregarding the over ow state) performs 3n operations. In fact, at each step, that is for each position j, three operations are performed: one shift, one addition and one test to determine whether P matches at position j.

Exact string matching

In the case of exact string matching, it is only necessary to know whether a given pre x of P matches exactly the considered substring of t. We de ne S j as follows:

For 1 i m, S j i] = 0 if p 1 p i = t j i+1 t j 1 otherwise When t j+1 is read, we need to determine whether t j+1 can extend any of the partial matches. Thus, in order to have a match of p 1 p i at position j + 1, both S j i 1] = 0 and t j+1 = p i should be satis ed. Here, b = 1, and in formula [START_REF] Aho | E cient string matching: an aid to bibliographic search[END_REF] the + symbol should be replaced by an OR operation. The algorithm based on this new formula is called Shift-Or.

Extensions

Flexibility is one of the principal advantages of the Shift-Add method. It can be easily adapted to a class of patterns. A class of patterns is a set of patterns, de ned by a string in which each position is a set of characters. A set of characters is for example a subset of or the complementary of a subset of . A pattern class de ned by a string in which each position is either a single character or the whole alphabet is called pattern with don't care symbols.

To take into account such classes, only the de nition of the T array needs changing: for a position i in P and a character a in , T a i] will contain 0 if a belongs to the set of characters corresponding to that position in P, and 1 otherwise. Thus, the T array computed during the preprocessing step contains all needed information about the pattern. Then, the searching step is not modi ed. [START_REF] Akutsu | Approximate string matching with don't care characters[END_REF] Boyer-Moore Approach to Shift-Add method Here, we consider the problem of searching all occurrences of a pattern string P = p 1 p m in a text string t = t 1 t n with at most k mismatches, 1 k m.

The problem of exact string matching can be solved by substituting the OR operation to the add operation. In the case of string matching with classes, the T array is modi ed as in section (2.2).

For some position j, the state S j is a bit number (represented in base 2 b ) de ned as previously: each individual state S j i], for 1 i m, contains the number of mismatches between p 1 p i and t j m+1 t j . Here, the introduction of the over ow state is ignored.

Shift

Our goal is to avoid processing each character of the text, in other words, avoid computing S j for every position j. It is easy to see that if for some pre x of length i of P, S j i] > k, then since S j+(m i) m] S j i], P will not occur at position j + (m i). The following proposition can be deduced: Proposition 1. For some position j in t, let l be the largest index i, 1 i m 1, such that S j i] k, if such an index exists and 0 otherwise. Let d = m l.

Then, the next position after j where P is likely to occur is j next = j + d. In other words, S j 0 m] > k, for every j 0 such that j < j 0 < j next .

d is the next shift and 1 d m k.

Consider now the transition between S j and S j+d .

The number of mismatches between the pre x p 1 p i of P, for d+1 i m, and the substring t j+d i+1 t j+d of t, i.e. S j+d i], is the sum of the number of mismatches between p 1 p i d and t j+d i+1 t j , i.e. S j i d], and the number of mismatches between p i d+1 p i and t j+1 t j+d .

The T array de ned in [START_REF] Abrahamson | Generalized string matching[END_REF] contains the information about the occurrence of a given character a at a given position in the pattern. Consequently:

S j+d i] = 8 > > > > < > > > > : S j i d] + d 1 X r=0 T t j+d r i r] if d < i m i 1 X r=0 T t j+d r i r] otherwise (3)
In order to obtain S j+d as a sum of numbers in base 2 b , the next de nition is needed: De nition 2. D denotes the j j m matrix such that, element D a] m r] for each a 2 and 0 r m 1, is denoted by D a;m r and de ned as follows:

D a;m r = m X i=r+1 T a i r]2 (i 1)b :
Intuitively, D a;m r denotes positions in p 1 p m r containing character a. For a xed r, D a;m r is obtained by a left shift of T a of rb positions.

S j+d can then be represented as follows:

S j+d = (S j << bd) + Practically, in order to determine the shift d, S j is shifted b bits at a time, until the obtained number is below k2 (m 1)b . S j will have nally been shifted d times to obtain S j << bd. Therefore, shifts are not grouped.

Character skip

The Boyer-Moore (BM) algorithm is an e cient exact string matching algorithm.

It is fast since it is possible, in certain conditions, to skip substrings of the text, that is not process them, without loss of information. At each step, characters of the text are processed from right to left.

In this section, we try to nd conditions in which parts of the text can be avoided without missing occurrences of the pattern.

Assume j is the last position scanned in the text and d is the next shift.

The substring of the text still to be scanned at this step of the search is then t j+1 t j+d . This substring is processed from right to left, that is beginning with t j+d , and the processing stops when t j+1 is reached, or when the information for all pre xes of P ending at position j + d is obtained.

Practically, in order to compute state S j+d , S j should rst be shifted on the left of bd bits. Let S j+d;0 = S j << bd be the obtained number. Then, each of the d characters t j+d r+1 , with 1 r d, should be processed. Let S j+d;r be the partial state obtained after processing characters t j+d ; ; t j+d r+1 of t. Then, S j+d;r = S j+d;r 1 + D t j+d r+1 ;m r+1 and we have S j+d = S j+d;d .

For given indexes r, 1 r d, and i, 1 i m:

(a) If S j+d;r i] > k, then without processing the remaining characters t j+d r ; ; t j+1 , we know that the pre x of length i of P does not occur at position j + d.

(b) If S j+d;r i] k and no more comparisons have to be performed for the pre x of length i of P, then this pre x matches at position j + d.

Therefore, instead of computing the number of mismatches with the corresponding substring of t, for each pre x of P, i.e. the terminal state, the computation stops at the rst partial state giving enough information for further processing. Let S 0 j be this partial state. Di erences between S j and S 0 j are located only in individual states exceeding k + 1.

Algorithm We suppose that the D matrix has been computed during a preprocessing step. For a given position j in the text, an index r and a prex of length i of P, State denotes the bit number consisting in individual states of partial state S j;r for pre xes with length from 1 to i. More precisely, State = S j;r i] S j;r 1]0 0. (2) Else : (2.2) Else : 12.

(2.2.1) If i = m then 13.

\Occurrence of P at position j";

PROOF :

Step [START_REF] Abrahamson | Generalized string matching[END_REF] of the algorithm corresponds to situation (a), that is when the partial number S j;r i] of mismatches found at this step of the search for the pre x i of P, exceeds k+1. In this case, this pre x is ignored and the next pre x i 1 of P is considered.

Step (2.1) corresponds to the situation where there is not enough information to stop comparing. In fact, for the pre x i of P, the number S j;r i] of mismatches obtained at this step of the search is less than k+1, but a number of comparisons remain to be done for this pre x.

Step (2.2) corresponds to situation (b), that is when S j;r i] < k + 1 for the pre x i, no more comparisons have to be performed for this pre x. In this case, if i = m, then position j matches and the search for the next shift goes on. If i < m, then the next shift is equal to m i. In fact, i corresponds to the length of the longest pre x of P matching the corresponding substring of t Example 2: Let , P, t and k be those de ned in example 1. Shifts are the same as for example1 and only state S 5 is not the terminal state. Recall that the scanning of t by the Shift-Add algorithm needs 3n operations, since each search step does exactly a shift, an addition and a test. It is not di cult to see that our algorithm does the same number of shifts (n) and less additions.

In fact, one addition is performed for each character processed in the text, and not all characters are examined. However, the number of tests increases, since in addition to those considered by the Shift-Add algorithm, those which make transitions between partial states should be considered.

Let t be a random text and j j = c. The probability of a given character to occur at a given position in the text is then 1 c .

Let X be a random variable denoting the length of the shift in Algorithm1 when searching pattern P in the random text t with at most k mismatches. The following lemma gives the average shift d m , that is the expected value < X > of the random variable X.

Lemma 1 Provided c is large enough compared to m, the average shift d m obtained by Algorithm1 exceeds d 0 m , with:

d 0 m m k 1 + 1 1 c k+1 ! 1 1 c
Now, we analyze the average number M k of characters processed at a given position j + d m of the text, where j is the last position scanned in the text. This number of characters is the length of the smallest substring of t ending at position j + d m and mismatching all substrings of P which are not pre xes. The maximum number of characters to be processed at this step is d m .

From the last remarks, we can deduce the following lemma: Lemma 2 Provided c is large enough compared to m, M k k + 2.

We are able now to evaluate the complexity of Algorithm1. Proposition 4. The average number OP k of operations performed by Algorithm1 is n 2 + 3M k +2 dm . When the considered alphabet is large enough, this number becomes OP k n 2 + 3k+8 m k .

PROOF :

Let OP dm;k be the average number of operations performed by Algorithm1 at each step of the search. Thus, OP k = n dm OP dm;k . At each step of the search, operations performed by Algorithm1 are: M k additions (one addition per character), d m shifts (lines 5. and 14. of the algorithm) and at most d m +2+2M k tests. In fact, note rst that condition 4 (State lim, step (1)) is true at most d m times and in that case we do not proceed to step [START_REF] Aho | E cient string matching: an aid to bibliographic search[END_REF]. Thus exactly d m tests are performed in these cases. Moreover, in order to know the next shift, we should go once through step (2.2.2) and then do tests 4. and 8. (test 12. could be avoided by changing the algorithm such that case i = m is examined at a previous step). Finally, since there are exactly M k additions, we should go through line 10. exactly M k times and at each time do tests 4. and 8. The average number of tests is therefore T

dm;k = d m + 2 + 2M k . So, OP dm;k = 2d m + 2 + 3M k and OP k = n 2 + 3M k +2
dm . The case of a large alphabet is deduced from lemmas 1 and 2

Improvement

In order to speed up the algorithm, it is obvious that a way should be found to perform less tests. Our idea is to process a certain number of characters at each step of the search, that is, do a certain number of additions before beginning tests.

Algorithm2

Let j be the current position in the text and d be the last shift obtained. We denote by C d the following number: C d = min (d; k + 2).

C d is the average number M k (lemma 2) of characters processed at each step by Algorithm1, provided this number does not exceed the maximum number of characters to be processed at this step, that is d.

Thus, before going through steps ( 1)-( 2), our improved algorithm (Algo-rithm2) will process rst the C d characters t j C d +1 t j and compute the partial state S j;C d , that is do C d additions.

Algorithm2 is hence obtained by adding a preliminary step (0') before step (0) in Algorithm1.

Exact string matching

In this case, the considered algorithm is Shift-Or (2.1). Baeza-Yates and Gonnet have introduced the following improvement: if at a given position j in t, S j = 1 mb 1 mb 1 1, that is all pre xes of P mismatch at position j, then the next character processed in the text is p 1 (if such a character exists). In fact, the state remains the same for all other characters.

We improve Algorithm2 as well: at a given step of the search, characters are processed until the partial state is equal to 1 mb 1 mb 1 1 (Algorithm3).

We have experimented algorithms Shift-Or and Algorithm3 on a 4,000,000 character text (the french version of the Bible). Figure1 shows the execution time while searching 100 random patterns from the Bible. The rst column of the table shows the lengths of the considered patterns.

We can see that the longest the pattern, the fastest Algorithm3 works. Moreover, for patterns of lengths up to 3, Algorithm3 is faster than Shift-Or.

Approximate string matching

Figure2 shows experimental results for Algorithm2 and Shift-Add, while searching 100 random patterns in the Bible (5MO) with at most 1 or 2 mismatches.

When m is large enough compared to k, Algorithm2 is faster than Shift-Add: for k = 1, m should be larger than 7 and for k = 2 larger than 9. Since mb should not exceed the word size !, large values of m cannot be considered. For ! = 32, the e ciency of Algorithm2 is then limited to k 2.

For longer patterns, we need to use more than a word per number. It is not di cult to extend the algorithm for this case. Baeza-Yates and Gonnet have noticed that Shift-Add is still a good practical algorithm for string matching with mismatches and classes, provided the number of words per number is small.

Figure3 shows results in the case of two bit words per number. Notice that they extend the results in Figure2.

Conclusion

We have developed an algorithm combining both the programming practicality of the Shift-Add method and the speed of the BM approach. Flexibility is another advantage of this algorithm . In fact, it can be easily adapted to classes of patterns.

Nevertheless, as for the BM algorithm, the larger the alphabet and the longer the pattern, the faster our algorithm works. For a large alphabet (ASCII code), the searching step does on average n(2 + k+4 m k ) operations. In some cases, it is necessary to consider small alphabets. In particular, in molecular biology when detecting potential gene-coding sequences in genomic DNA sequences. fA; C; G; Tg. For such alphabets, our algorithm does n(2 + ) operations, with < 1, provided that the length m of the pattern is very large compared to k.

In order to consider large patterns, one solution is to use more than a bit word per number. Moreover, Baeza-Yates and Perleberg (BYP) 7] have developed an algorithm for approximate string matching, based on the same naive method than for the Shift-Add algorithm, but using arrays instead of numbers.

In this case, there is no condition on the length of the searched pattern, however the algorithm is slower. The main di erence is that BYP considers the number of matches instead of the number of mismatches. The BYP algorithm can be adapted from BM in the same way the Shift-Add was and it is then possible to consider long patterns.

  r ;m r : Initial values are S 0 = 0 and d = m.

Example 1 :

 1 Let = fa; b; c; dg, P = abbac and k = 1shifts when searching P in t with at most k mismatches: of shifts does not improve the complexity of the Shift-Add algorithm . It only has the e ect of grouping additions and tests. However, shifts are essential to introduce the notion of characters skip which will nally speed up the algorithm.

Algorithm1:

  BM approach to approximate string matching 0. j := m; d := m; State := 0; 1. lim := (k + 1) << (m 1); 2. While j n do 3.(0) i := m; r := 0

  State + D tj r ;m r ; Go to (1).11.

19 .

 19 End of While. Proposition 3. Algorithm1 nds all occurrences of the pattern P in the text t with at most k mismatches.

Complexity

  Our goal is to evaluate the average number of operations performed by Algorithm1. Operations are of three kinds: shifts, additions and tests.

  l ;m l ; r := r + C d ; Obviously, Algorithm2 nds the same results, the same shifts and so the same average shift d m that Algorithm1. Proposition 5. Provided the alphabet is large enough, the average number of operations performed by Algorithm2 is OP k n 2 + k+4 m k . PROOF : Our goal is to evaluate the average number OP dm;k of operations performed by Algorithm2 at any search step. First, M k characters are processed and M k additions are performed. Two cases are then encountered: 1. The partial state holds enough information, so no more characters are processed at this step. In this case, d m + 2 tests and d m shifts are performed. 2. The partial state does not hold enough information. In this case, the maximum number of characters still to be performed is d m M k . The number of shifts is the same as that of the previous state and there are 2(d m M k ) more tests. Let P k be the probability of the second case. Then, OP dm;k = M k + 2d m + 2 + P k (3 (d m M k )) and OP k = n 2 + M k + 2 + 3P k (d m M k ) d m When the considered alphabet is large enough, d m m k (Lemma1), M k k + 2 (Lemma2) and we can prove that P k 0. Thus, OP k n 2 + k+4 m k 5 Experiments Our goal is to nd out under which conditions Algorithm2 is fastest than algorithm Shift-Add. Algorithm3: Exact string matching 0. j := m; d := m; State := 0; 1. lim:= (k + 1) << (m 1); initial:=1 mb 1 mb 1 State OR D tj r ;m r ;

Figure 3 :

 3 Figure 3: Complementary results when mb > 32. Two bit words per number are used.

  The considered alphabet consists in the four nucleotides Experimental results (in seconds) for searching 100 random patterns in the Bible with at most 1 or 2 mismatches. For k = 2 and m > 10, more than one word per number is needed.

	k = 1 m Shift-Add Algorithm2 Shift-Add Algorithm2 k = 2 6 157.56 178.05 157.24 215.77 7 155.83 161.88 156.25 195.68 8 156.01 154.05 155.64 175.67 9 155.57 148.13 156.33 161.02 10 155.10 145.85 150.72 155.63 11 141.67 155.76 12 135.80 154.66 13 129.40 155.02 14 125.28 155.45 15 121.08 154.94 16 155.73 117.21
	Figure 2: k = 1 m Shift-Add Algorithme2 Shift-Add Algorithme2 Shift-Add Algorithme2 k = 2 k = 3 12 281.56 275.96 282.38 308.53 14 281.27 266.48 278.75 281.75 16 281.17 250.82 265.46 281.25 18 280.54 219.24 280.78 238.18 256.98 281.12 20 282.25 211.78 281.85 227.57 246.60 281.65 205.70 22 280.48 198.13 26 281.38 194.20 28 280.85 32 280.93 188.52


Marie-Pierre Béal
email: beal@univ-mlv.fr

Maxime Crochemore

Minimizing local automata

We design an algorithm that minimizes irreducible deterministic local automata by a sequence of state mergings. Two states can be merged if they have exactly the same outputs. The running time of the algorithm is O(min(m(nr + 1), m log n)), where m is the number of edges, n the number of states of the automaton, and r the number of states of the minimized automaton. In particular, the algorithm is linear when the automaton is already minimal and contrary to Hopcroft's minimisation algorithm that has a O(kn log n) running time in this case, where k is the size of the alphabet, and that applies only to complete automata. (Note that kn ≥ m.) While Hopcroft's algorithm relies on a "negative strategy", starting from a partition with a single class of all states, and partitioning classes when it is discovered that two states cannot belong to the sam class, our algorithm relies on a "positive strategy", starting from the trivial partition for which each class is a singleton. Two classes are then merged when their leaders have the same outputs.

The algorithm applies to irreducible deterministic local automata, where all states are considered both initial and final. These automata, also called covers, recognize symbolic dynamical shifts of finite type. They serve to present a large class of constrained channels, the class of finite memory systems, used for channel coding purposes. The algorithm also applies to irreducible deterministic automata that are left-closing and have a synchronizing word. These automata present shifts that are called almost of finite type. Almost-of-finite-type shifts make a meaningful class of shifts, intermediate between finite type shifts and sofic shifts.

I. INTRODUCTION

Local automata, also called definite automata or definite covers [START_REF] Perles | The theory of definite automata[END_REF], present a large class of systems: the class of finite memory systems used in coding for constrained channels [START_REF] Adler | Algorithms for sliding block codes[END_REF]. These channels have a canonical minimal deterministic presentation, called the Fischer cover, which can be computed from an n-state local deterministic presentation using Hopcroft's minimisation algorithm that runs in time O(kn log n) [START_REF] Hopcroft | An n log n algorithm for minimizing states in a finite automaton[END_REF],

where k is the alphabet size.

Hopcroft's algorithm computes the Nerode partition of the set of states with a "negative strategy". It starts from a partition with a single class of all states, and partitions classes when it is discovered that two states cannot belong to a same class. It applies to any complete finite-state automaton. For local automata, as well as also for almost of finite type (AFT) automata, the minimal presentation can be obtained with a sequence of state mergings.

In this paper we design an algorithm to compute the minimal automaton of a deterministic local automaton that relies on a "positive strategy". We start from the trivial partition for which each class is a singleton. Two classes are then merged when their leaders have the same outputs. The running time of this algorithm is O(min(m(nr + 1), m log n)), where m is the number of edges of the automaton. In particular, it is linear when the automaton is already minimal contrary to Hopcroft's algorithm that has an O(kn log n) complexity in this case, and that requires a complete automaton. Hence, it is faster than Hopcroft's algorithm when few states are to be merged, which is a frequent situation. The algorithm consists first in building a digital tree, called the signature trie, which stores the lexicographically-sorted outputs of states. This technique, called multiset discrimination in [START_REF] Paige | Three partition refinement algorithms[END_REF], [START_REF] Cai | Using multiset discrimination to solve language processing problems without hashing[END_REF] is used to avoid hashing and to produce deterministic algorithms. In the second step the tree is updated after each state merging.

Our algorithm applies to the class of almost-of-finite-type automata, which includes finite memory automata. These are deterministic irreducible automata that are also left-closing (or co-deterministic with a finite delay), and synchronizing. The automata present channels called almost of finite type (AFT). They were introduced by Marcus [START_REF] Marcus | Sofic systems and encoding data[END_REF] for coding purposes. Indeed, the theory of modulation codes provides many natural AFT examples. The AFT sofic shifts is a meaningful class, intermediate between shifts of finite type and sofic shifts from the point of view of symbolic dynamics. Indeed, it was shown by Boyle, Kitchens and Marcus in [START_REF] Boyle | A note on minimal covers for sofic shifts[END_REF] that the class of AFT shifts is the unique class of shifts having a minimal cover in the sense of symbolic dynamics. It is possible to encode an unconstrained source into an AFT constrained channel having a capacity not less that the entropy of the source with a sliding block decoder [START_REF] Kohavi | Sliding-block coding for inputrestricted channels[END_REF], while it is not possible to build such a code for a general finite-state constrained channel in the case of equality of the capacity and entropy.

From the algorithmic point of view, our method is a solution to multiset discrimination with updates.

Below we first introduce the type of automata considered in the paper and then describe their minimisation algorithm.

II. LOCAL AND ALMOST-OF-FINITE-TYPE AUTOMATA

In this article, an automaton (or cover) is a pair A = (Q, E), where Q is a finite set of states, and E is a finite set of edges labeled by letters of a finite alphabet A. (Edges are triples of the form (p, a, q), p, q ∈ Q, a ∈ A.) No initial nor final states are specified in this notation. Actually, all states have to be considered as both initial and final states. We say that an automaton is irreducible if it has a strongly connected graph. The set of bi-infinite words labeling a bi-infinite path in A is called the sofic shift presented by A.

The automaton is deterministic if two edges with the same origin carry different labels.

The word w is said to be a synchronizing word of A if there are nonnegative integers m and a such that whenever two paths ((p i , a i , p i+1 )) 0≤i<(m+a) and ((p ′ i , a i , p ′ i+1 )) 0≤i<(m+a) of length m + a have the same label w, then p m = p ′ m (m stands for memory, and a for anticipation). An automaton is synchronizing if it has at least one synchronizing word.

Let m and a be nonnegative integers. We say that the automaton is (m, a)-local (or (m, a)-definite) if whenever two paths ((p i , a i , p i+1 )) 0≤i<(m+a) and ((p ′ i , a i , p ′ i+1 )) 0≤i<(m+a) of length m + a have the same label, then p m = p ′ m . We say that an automaton is local (or definite, or has finite memory) if it is (m, a)-local for some integers m and a. An irreducible automaton has finite-memory if and only two distinct cycles carry different labels. Note that a deterministic and local automaton is always (m, 0)-local for some integer m. A sofic shift that can be presented by a local automaton is said to be a shift of finite type.

Let m be a nonnegative integer. We say that an automaton is m-right-closing if whenever two paths ((p i , a i , p i+1 )) 0≤i<m and ((p ′ i , a i , p ′ i+1 )) 0≤i<m of length m have the same label and the same origin then they share the same first edge. The notion of an a-left-closing automaton is defined similarly when a is a nonnegative integer. Note that a deterministic automaton is 1-right-closing.

We say that an automaton is almost of finite type (AFT) if it is an irreducible and synchronizing automaton that is m-rightclosing and a-left-closing for some integers m and a. Note that any irreducible local automaton is AFT. A deterministic automaton is AFT if and only if it is left-closing and has a synchronizing word. A sofic shift that can be presented by an AFT automaton is said to be almost of finite type.

Examples of a local automaton and of a non-AFT automaton are given in Figure 1 and Figure 2.

III. MINIMISATION OF DETERMINISTIC AFT AUTOMATA A. Minimisation by a sequence of state mergings

Let A = (Q, E) be a deterministic automaton. It is known that, when A is irreducible, the shift presented by A has a minimal deterministic irreducible automaton called the right Fischer cover of the shift (see for instance [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF], [START_REF] Kitchens | Symbolic Dynamics: one-sided, two-sided and countable state Markov shifts[END_REF], [START_REF] Perrin | Symbolic dynamics and finite automata[END_REF]). It is unique up to a renumbering of its states. It can be obtained from A by computing the Nerode partition of the states: two states p, q belong to the same class of this partition if and only if they have the same future, i.e., F (p) = F (q), where F (s) = {u ∈ A * | there is a path from s labeled by u in A}.

We say that two states p and q of A can be merged if (p, a, r) ∈ E is equivalent to (q, a, r) ∈ E. A state merging identifies two mergeable states.

In general, it is not true that a deterministic non-minimal automaton has mergeable states (see the automaton of Figure 2). However, this property is true for the class of deterministic AFT automata. As a consequence, it is possible to minimize such automata by a sequence of state mergings.

The following lemma from [3, p.41] provides a efficient characterization of a left-closing automata. Efficient characterizations of AFT shifts where obtained by Boyle, Kitchens, and Marcus [START_REF] Boyle | A note on minimal covers for sofic shifts[END_REF] and by Nasu [START_REF] Nasu | An invariant for bounded-to-one factor maps between transitive sofic subshifts, Ergodic Theory Dynam[END_REF].

The lemma uses the notion of product of two automata defined as follows. The product of the automaton A by itself is the automaton

A 2 = A × A = (Q × Q, F
) where ((p, q), a, (r, s)) ∈ F if and only if both (p, a, r) ∈ E and (q, a, s) ∈ E.

Lemma 1: The automaton A is left-closing if and only if the automaton A 2 has no cycle going through a state (p, q), p = q, which is co-accessible from a state of the form (r, r).

The following proposition already appeared in [3, Proposition 2.16 p.60].

Proposition 2: If a deterministic AFT automaton A is not minimal, then at least two of its states can be merged.

Proof: Assume that no two states of A can be merged, and let p and q be two distinct states having the same future.

Let C be the set of states of A 2 accessible from (p, q). Since p and q have the same future, any states r, s such that (r, s) is in C also have the same future. We construct an infinite sequence (p i , q i ) i≥0 (p i = q i ) of states in C defined as follows. We choose (p 0 , q 0 ) = (p, q). Hence p 0 = q 0 . For i ≥ 1, since p i and q i cannot be merged, for some letter a i , (p i-1 , a i , r) and (q i-1 , a i , s) are edges with r = s. We choose (p i , q i ) = (r, s). Hence C contains a cycle of states (r, s) with r = s. Let (r, s) be a state on this cycle.

Since A is irreducible and synchronizing, there is a path starting at r labeled by w, where w is a synchronizing word. Since F (r) = F (s), there is a path in A 2 starting from (r, s) and labeled by w. This path ends in a state (t, t) since w is synchronizing. This contradicts the fact that A is left-closing by Lemma 1, which ends the proof.

B. First step of the algorithm: building a tree

We describe below a minimisation algorithm that applies to deterministic AFT automata, and hence to irreducible deterministic local automata. The parameters of the algorithm are the number n of states of the automaton A = (Q, E), its number m of edges, the size k of the underlying alphabet, and the number r of states of the minimal automaton. Of course, m ≤ kn since the automaton is deterministic.

We assume that A = {a 1 , a 2 , . . , a k } are that the letters are ordered: a 1 < a 2 < • • • < a k . We associate with each state p ∈ Q = {1, 2 . . , n} its signature σ(p) = a 1 p 1 a 2 p 2 . . a l p l , where (p, a 1 , p 1 ), . . , (p, a l , p l ) are the edges starting from p in lexicographic order. A partial signature of state p is a prefix a 1 p 1 a 2 p 2 . . a r p r of its signature.

In the first step of the algorithm we build a tree representing the set of all signatures. Is is called the signature trie. Denoted by T , it is defined as follows. Each node represents the set of states whose partial signature is a 1 p 1 a 2 p 2 . . a r p r . The root of the tree represents the set of all states. An arc labeled by a r+1 p r+1 links the node associated with the partial signature a 1 p 1 a 2 p 2 . . a r p r to the node associated with the partial signature a 1 p 1 a 2 p 2 . . a r+1 p r+1 . The leaves of the trie are the nodes associated with a complete signature. Each leaf contains the set of states having this signature.

The trie can be constructed after a lexicographical sort of the signatures. This technique is analogue to the multiset discrimination described in [START_REF] Paige | Three partition refinement algorithms[END_REF], [START_REF] Cai | Using multiset discrimination to solve language processing problems without hashing[END_REF], which avoids using hashing. It is used in [START_REF] Revuz | Minimisation of acyclic deterministic automata in linear time[END_REF] to minimize acyclic automata.

The structure of a node x of the trie is the following. It contains the (non-sorted) list succ(x) of the arcs leaving x. The list is indexed by all (a, p) for which ap is the label of some arc of the trie. We denote by succ(x)(a, p) the arc labeled by ap originated from x. It contains the address of its target node. The size of a node of the trie is the number of states contained in the leaves of the subtree rooted at this node.

In addition to the trie T , we also maintain a non-sorted list arc, indexed by all (a, p) such that ap is the label of some arc of the trie, and such that arc(a, p) is the list of all arcs labeled by ap contained in some list succ(x) 1 . We also assume that each arc from x labeled by ap contains the address of the element in arc(a, p) pointing to it. We denote by size(a, p) the size of the list arc(a, p). It is defined as the sum of sizes of all the target nodes of arcs labeled by ap. Hence it is the number of states of the automaton with an outgoing edge labeled by a and ending in p. The implementation of the lists succ(x), arc, and arc(a, p) is described in Section III-D. A sparse list implementation is used for the lists succ(x) and arc. All the data structures lead to an efficient update of the trie T after two states are merged, as described in the next section.

An example of a deterministic AFT-automaton A is given in Figure 3. Its minimal automaton is displayed in Figure 4 and its initial signature trie is shown in Figure 5.

C. Second step of the algorithm: updating the tree

The second step of the algorithm can be shortly described as follows. The signature trie allows one to detect easily a pair (x, y) of states with the same signature (i.e. , with the same outputs). Indeed, x and y belong to a same leaf in this case. Then the states x and y are merged. Hence the signatures 1 Actually, in the implementation, arc(a, p) is the list of addresses of all nodes x such that succ(x) contains an arc labeled by ap. containing x or y have to be updated inside the trie. This update is the delicate point of the algorithm.

For each letter a ∈ A, we denote by Im(a) the set of states of A ending edges labeled by a. For each letter a, we maintain the partition of Im(a) for which two states of Im(a) having already been merged belong to a same class. Each class has a leader. Assume that the states x and y have to be merged and both belong to Im(a). Let p (resp. q) be the leader of the class of x (resp. y). We keep q as the new leader of the union class when the number of edges labeled by a and ending in p is smaller than the number of edges labeled by a and ending in q. This smaller-half strategy, applied for each letter, will guarantee the overall running time of the algorithm. The edges labeled by a and ending in p are then changed into edges labeled by a and ending in q.

We update the edges ending in p for each letter a i in the decreasing order of the a i . Once this update is done, the same process is iterated until no more pair of states with the same outputs is detected.

In order to change all edges labeled by a and ending in p into edges labeled by a and ending in q, the procedure MERGE(a, p, q) updates the nodes x having an outgoing arc e labeled by ap. Two cases may appear according to whether x has no arc labeled by aq or it has an arc f labeled by aq. In the former case, its arc e becomes an arc labeled by aq and the lists arc(a, p), arc(a, q) are changed accordingly. In the latter case, the procedure FUSION(x 1 , x 2 ), where x 1 (resp.

x 2 ) is the target of e (resp. f ), makes a fusion of the subtrees rooted at x 1 and x 2 by inserting x 1 into x 2 . The procedures MERGE and FUSION are described below.

The main procedure is the procedure MINIMISATION-AFT-AUTOMATON which starts with the initial trie construction and sets up the lists arc. The leaves of the trie are then scanned. For each leaf of size greater than one containing states q 1 , . . . , q l , each pair (q i , q i+1 ), 1 ≤ i ≤ l -1, is pushed onto a stack denoted toMerge. This stack contains pairs of states to be merged. MERGE (a, p, q)

1. for each arc e in arc(a, p) do 2. let x be the node origin of e 3.

if x has no arc labeled by aq then 4.

change the label of e into aq 5.

transfer it from arc(a, p) to arc(a, q) 6.

else (x has an arc f labeled by aq) 7.

let x1 be the target of e and x2 be the target of f 8.

remove the arc e from succ(x) and from arc(a, p) FUSION(y1, y2)

In the minimisation procedure described below, CLASS(a, x) denotes a call to the procedure computing the leader of the class of x for the letter a.

MINIMISATION-AFT-AUTOMATON (

A = (Q, E), A = {a1, . . , a k })
1. build the signature trie T and the lists arc 2. for each leaf (p1, p2, . . , p l ) of T do 3. push (pi, pi+1) onto the stack toMerge for 1 ≤ i ≤ l -1 4. compute size(a, p) the size of each list arc(a, p) 5. while the stack toMerge is non-empty do 6.

remove a pair (x, y) from toMerge 7.

for i from k downto 1 do 8.

if x and y belong to Im(ai) then 9.

let (p, q) ←(CLASS(ai, x),CLASS(ai, y)) 10.

if size(ai, p) ≤size(ai, q) then 11.

q becomes the leader of the union 12.

of the classes of p and q for the letter ai 13.

MERGE(ai, p, q) 14. else 15.

p becomes the leader of the union 16.

of the classes of p and q for the letter ai 17.

MERGE(ai, q, p) 18. return T

D. Complexity of the algorithm

We analyze the complexity of the algorithm. The initial signature trie and the lists arc are built in time O(m) using radix sort for sorting the list whose elements belong to the integer interval [1, 2, . . . , n]. The implementation of lists arc and succ(x) for all nodes x is done with a sparse list implementation (see [START_REF] Aho | The Design and Analysis of Computer Algorithms[END_REF] Exercise 2.12 p. 71 and [START_REF] Crochemore | Algorithmique du texte[END_REF] Exercise 1.14 "Implantation de fonctions partielles" Chapter 1). These lists are indexed by (a, p) where ap is the label of some arc of the trie. As a consequence, it is possible to find, add, or remove an arc in a list succ(x) or in a list arc in time O(1). Initialization is done in constant time too. The space required for the implementation is O(kn 2 ).

It remains to evaluate the time complexity of all updates. Assume that the states x and y in Im(a) have to be merged. Classes of the partition of Im(a) are implemented as trees where the leader of the class is at the root of the tree. A sequence of m Union-Find operations with path compression [START_REF] Cormen | Introduction to algorithms[END_REF] is performed in time O(m min{α(m), log n}), where α is the inverse of the Ackermann function. Let us denote by p (resp. q) the leader of the class of x (resp. the class of y). Assume that the number of edges labeled by a and ending in p is smaller than the number of edges labeled by a and ending in q. Then q becomes the leader of the union of the two classes. The arcs of the trie labeled by ap are changed into arcs labeled by aq through the procedure MERGE(a, p, q). The time complexity of this call is proportional to the size of the subtrees rooted at the targets of all arcs of the trie labeled by ap. Up to a multiplicative constant, it is at most the number of leaves of these subtrees, that is, size(a, p), which is equal to the number of edges labeled by a and ending in p in the automaton. Since size(a, p) is no more than size(a, q) before the merging operation, size(a, q) after the merging has at least twice the size of size(a, p) before the merging. Hence each edge labeled by a is changed at most log n times. Furthermore, if nr is the number of pairs of states being merged, each edge can be changed also at most nr times. Hence the cost of all these updates for all letters is O(min(m log n, m(n + 1r))). As a consequence, we get the following proposition.

Proposition 3: The overall running time of the procedure MINIMISATION is O(min(m log n, m(n + 1r))), where r is the number of states of the minimal automaton.

The execution of the algorithm on the automaton of

Fig. 1 .

 1 Fig. 1. A (0, 1)-local automaton.

Fig. 2 .

 2 Fig. 2. A non-AFT automaton. It is both right-closing and left-closing but it is not synchronizing.

Fig. 3 .

 3 Fig. 3. A deterministic AFT automaton.

Fig. 4 .

 4 Fig. 4. The minimal automaton corresponding to the automaton of Figure 3.

Fig. 5 .

 5 Fig. 5. The initial signature trie of the automaton of Figure 3. It is rooted at the node 1. Only one leaf contains more than one state, namely states 2, 4. They have the same signature a6b2c5.

Figure 3 is described in Figure 6 .

 6 The forests F a , F b , F c , and F d corresponding to the partitions of Im(a), Im(b), Im(c), and Im(d) respectively, are represented in Figure8. The lists arc are described in Figure7.

Fig. 6 .Fig. 7 .

 67 Fig. 6. Updates of the signature trie of Figure 5. The initial trie is given in Figure 5. (a) After updating arcs labeled by b. (b) After updating arcs labeled by a. This is the result of merging 2 and 4. (c) Result of merging 1 and 3: update of the arcs labeled by d. The merging of states 5 and 6 does not change the trie. The leaves of the trie correspond to the states of the minimal automaton of Figure 4.

F d F c F b F a 3 Fig. 8 .

 38 Fig. 8. The forests Fa, F b , Fc and F d correspond to the partitions of Im(a), Im(b), Im(c), and Im(d) respectively at the end of the execution.


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

Costas S Iliopoulos

M Sohel
email: sohel@dcs.kcl.ac.uk

Finding Patterns In Given Intervals

In this paper, we study the pattern matching problem in given intervals. Depending on whether the intervals are given a priori for pre-processing, or during the query along with the pattern or, even in both cases, we develop solutions for different variants of this problem. In particular, we present efficient indexing schemes for each of the above variants of the problem.

Introduction

The classical pattern matching problem is to find all the occurrences of a given pattern P = P [1..m] of length m in a text T = T [1..n] of length n, both being sequences of characters drawn from a finite character set Σ. This problem is interesting as a fundamental computer science problem and is a basic need of many applications, such as text retrieval, music retrieval, computational biology, data mining, network security, to name a few. Several of these applications require, however, more sophisticated forms of searching. As a result, most recent works in pattern matching has considered 'inexact matching'. Many types of differences have been defined and studied in the literature, namely, errors (Hamming distance, LCS [START_REF] Cole | Dictionary matching and indexing with errors and don't cares[END_REF][START_REF] Hirschberg | Algorithms for the longest common subsequence problem[END_REF], edit distance [START_REF] Cole | Dictionary matching and indexing with errors and don't cares[END_REF]20]), wild cards or don't cares [START_REF] Cole | Dictionary matching and indexing with errors and don't cares[END_REF][START_REF] Cole | Verifying candidate matches in sparse and wildcard matching[END_REF][START_REF] Fischer | String matching and other products[END_REF][START_REF] Rahman | Finding patterns with variable length gaps or don't cares[END_REF], rotations [START_REF] Amir | Twodimensional pattern matching with rotations[END_REF][START_REF] Amir | Faster two dimensional pattern matching with rotations[END_REF], scaling [START_REF] Amir | Real scaled matching[END_REF][START_REF] Amir | Faster two dimensional scaled matching[END_REF], permutations [START_REF] Butman | Scaled and permuted string matching[END_REF] among others.

Contemporary research on pattern matching has taken many other different and interesting directions ranging from position restricted pattern matching [START_REF] Mäkinen | Position-restricted substring searching[END_REF] to pattern matching with address error [START_REF] Amir | Pattern matching with address errors: rearrangement distances[END_REF] and property matching [START_REF] Amir | Property matching and weighted matching[END_REF]. In this paper, we are interested in pattern matching in given intervals and focus on building an index data structure to handle this problem efficiently. This particular variant of the classic pattern matching problem is motivated by practical applications depending on different settings. For example, in many text search situations one may want to search only a part of the text collection, e.g. restricting the search to a subset of dynamically chosen documents in a document database, restricting the search to only parts of a long DNA sequence, and so on. In these cases we need to find a pattern in a text interval where the intervals are given with the query pattern. On the other hand, in a different setting, the interval or a set thereof may be supplied with the text for preprocessing. For example, in molecular biology, it has long been a practice to consider special genome areas by their structure. Examples are repetitive genomic structures [START_REF] Jurka | Human repetitive elements[END_REF] such as tandem repeats, LINEs (Long Interspersed Nuclear Sequences) and SINEs (Short Interspersed Nuclear Sequences) [START_REF] Jurka | The impact of short interspersed elements (SINEs) on the host genome. 20. V. Levenshtein. Binary codes capable of correcting, deletions, insertions and reversals[END_REF]. In this setting, the task may be to find occurrences of a given pattern in a genome, provided it appears in a SINE, or LINE. Finally a combination of these two settings is also of particular interest: find occurrences of a given pattern in a particular part of a genome, provided it appears in a SINE, or LINE.

Note that, if we consider the 'normal' (non-indexing) pattern matching scenario, the pattern matching in given intervals become straightforward to solve: we solve the classic pattern matching problem and then output only those that belong to the given intervals. However, the indexing version of the problem seems to be much more complex. Depending on whether the intervals are given a priori for pre-processing (Problem PMGI), or during the query along with the pattern (Problem PMQI) or, even in both the cases (Problem PMI), we develop solutions for different variants of this problem. A slightly different variant of Problem PMGI was studied in [START_REF] Amir | Property matching and weighted matching[END_REF], whereas Problem PMQI was introduced and handled in [START_REF] Mäkinen | Position-restricted substring searching[END_REF] (See Section 2 for details).

The contribution of this paper is as follows. We first handle the more general problem PMI (Section 3) and present an efficient data structure requiring O(n log 3 n) time and O(n log 2 n) space with a query time of O(m+log log n+K) per query, where K is the size of the output. We then solve Problem PMGI (Section 4) optimally (O(m + K) query time on a data structure with O(n) time and O(n log n)-bit space complexity). Finally, we improve the query time of [START_REF] Mäkinen | Position-restricted substring searching[END_REF] for Problem PMQI (Section 5) to optimal i.e. O(m + K) per query. The corresponding data structure, however, requires O(n 2 ) time due to a costly preprocessing of an intermediate problem, which remains as the bottleneck in the overall running time.

The rest of the paper is organized as follows. In Section 2, we present the preliminary concepts. The contributions of this paper are presented in Section 3 to 5. We conclude briefly in Section 6.

Preliminaries

A text, also called a string, is a sequence of zero or more symbols from an alphabet

Σ. A text T of length n is denoted by T [1..n] = T 1 T 2 . . . T n , where T i ∈ Σ for 1 ≤ i ≤ n. The length of T is denoted by |T | = n.
A string w is a factor or substring of T if T = uwv for u, v ∈ Σ * ; in this case, the string w occurs at position |u| + 1 in T . The factor w is denoted by

T [|u| + 1..|u| + |w|]. A prefix (suffix ) of T is a factor T [x..y] such that x = 1 (y = n), 1 ≤ y ≤ n (1 ≤ x ≤ n).
In traditional pattern matching problem, we want to find the occurrences of a given pattern P [1..m Problem PMQI was studied extensively in [START_REF] Mäkinen | Position-restricted substring searching[END_REF]. The authors in [START_REF] Mäkinen | Position-restricted substring searching[END_REF] presented a number of algorithms depending on different trade-offs between the time and space complexities. The best query time they achieved was O(m + log log n + |Occ P T [ℓ..r] |) against a data structure exhibiting O(n log 1+ǫ n) space and time complexity, where 0 ≤ ǫ ≤ 1. A slightly different version of Problem PMGI was studied in [START_REF] Amir | Property matching and weighted matching[END_REF] 5 . In particular, the difference lies in the fact that the problem handled in [START_REF] Amir | Property matching and weighted matching[END_REF], looks for the occurrences of the given pattern completely confined in the given set of intervals, π, whereas in Problem PMGI, only the occurreces that starts in π are of interest. Problem PMI, as is evident from the definition, is the combination of Problem PMQI and PMGI and hence is a more general problem in this regard.

In traditional indexing problem one of the basic data structures used is the suffix tree data structure. In our indexing problem, we make use of this suffix tree data structure. A complete description of a suffix tree is beyond the scope of this paper, and can be found in [START_REF] Mccreight | A space-economical suffix tree construction algorithm[END_REF][START_REF] Ukkonen | On-line construction of suffix trees[END_REF] or in any textbook on stringology (e.g. [START_REF] Crochemore | Jewels of Stringology[END_REF][START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences -Computer Science and Computational Biology[END_REF]). However, for the sake of completeness, we define the suffix tree data structure as follows. Given a string T of length n over an alphabet Σ, the suffix tree ST T of T is the compacted trie of all suffixes of T $, where $ / ∈ Σ. Each leaf in ST T represents a suffix T [i..n] of T and is labeled with the index i. We refer to the list (in left-to-right order) of indices of the leaves of the subtree rooted at node v as the leaf-list of v; it is denoted by LL(v). Each edge in ST T is labeled with a nonempty substring of T such that the path from the root to the leaf labeled with index i spells the suffix T [i..n]. For any node v, we let ℓ v denote the string obtained by concatenating the substrings labeling the edges on the path from the root to v in the order they appear. Several algorithms exist that can construct the suffix tree ST T in O(n log Σ) time6 [START_REF] Mccreight | A space-economical suffix tree construction algorithm[END_REF][START_REF] Ukkonen | On-line construction of suffix trees[END_REF][START_REF] Farach | Optimal suffix tree construction with large alphabets[END_REF]. The space requirement of suffix tree is O(n log n) bits. Given the suffix tree ST T of a text T we define the "locus" µ P of a pattern P as the node in ST T such that ℓ µ P has the prefix P and |ℓ µ P | is the smallest of all such nodes. Note that the locus of P does not exist, if P is not a substring of T . Therefore, given P, finding µ P suffices to determine whether P occurs in T . Given a suffix tree of a text T , a pattern P, one can find its locus and hence the fact whether T has an occurrence of P in optimal O(|P|) time.In addition to that, all such occurrences can be reported in constant time per occurrence.

Problem PMI

In this section, we handle Problem PMI. Since this is a more general problem than both PMQI and PMGI, any solution to PMI would also be a solution to both PMQI and PMGI. Our basic idea is to build an index data structure that would solve the problem in two steps. First, it will (implicitly) give us the set Occ P T . Then, the index would 'select' some of the occurrences to provide us with our desired set Occ P T [ℓ..r],π . We describe now the idea we employ. We first construct a suffix tree ST T . According to the definition of suffix tree, each leaf in ST T is labeled by the starting location of its suffix. We do some preprocessing on ST T as follows. We maintain a linked list of all leaves in a left-to-right order. In other words, we realize the list LL(R) in the form of a linked list, where R is the root of the suffix tree. In addition to that, we set pointers v.left and v.right from each tree node v to its leftmost leaf v ℓ and rightmost leaf v r (considering the subtree rooted at v) in the linked list. It is easy to realize that, with these set of pointers at our disposal, we can indicate the set of occurrences of a pattern P by the two leaves µ P ℓ and µ P r because all the leaves between and including µ P ℓ and µ P r in LL(R) correspond to the occurrences of P in T . In what follows, we define the terms ℓ T and r T such that LL(R)[ℓ T ] = µ P ℓ and LL(R)[r T ] = µ P r , where R is the root of ST T . Now recall that our data structure has to be able to somehow "select" and report only those occurrences that lies in the intersection of the query interval and one of the given intervals. To solve this we use the following two interesting problems.

Problem "CRSI" (Colored Range Set Intersection Problem). Suppose V [1..n] and W [1..n] are two permutations of [1..n]. Also, assume that each i ∈ [1.
.n] is assigned a not necessarily distinct color. Preprocess V and W to answer the following form of queries. Query: Find the distinct colors of the intersection of the elements of

V [i..j] and W [k..ℓ], 1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ ℓ ≤ n. Problem "CRSG" (Colored Range Search Problem on Grid). Suppose A[1..n] is a set of n colored points on the grid [0..U ] × [0..U ].
Preprocess A to answer the following form of queries. Query: Given a query rectangle q ≡ (a, b) × (c, d), find the set of distinct colors of points contained in q.

Our idea is to first reduce Problem PMI to Problem CRSI and then to the much more studied Problem CRSG. Recall that, we have an array LL(R) and an interval [ℓ T ..r T ], which implicitly gives us the set Occ P T . Recall also that, our goal is to select those i ∈ Occ P T such that i occurs in one of the intervals of π and also in [ℓ..r]. We first construct an array .n]. Now it is easy to see that, if we can find the distinct colors in the set of intersections of elements of LL(R)[ℓ T ..r T ] and M[ℓ..r], then we are (almost) done. The only additional thing we need to take care of is that if we have the color c f ixed in our output, we need to discard it. So, the Problem PMI is reduced to Problem CRSI.

M = M[1..n], such that for all k ∈ [1..n], M[k] = k. Also,
On the other hand, we can see that Problem CRSI is just a different formulation of the Problem CRSG. This can be realized as follows. We set U = n. Since V and W in Problem CRSI are permutations of [1..n], every number in [1..n] appears precisely once in each of them. We define the coordinates of every number i ∈ [1.

.n] to be (x, y), where V [x] = W [y] = i. Thus we get the n colored points (courtesy to C) on the grid [0..n] × [0..n], i.e. the array A of Problem CRSG. The query rectangle q is deduced from the two intervals [i..j] and [k..ℓ] as follows: q ≡ (i, k) × (j, ℓ). It is straightforward to verify that the above reduction is correct and hence we can solve Problem CRSI using the solution of Problem CRSG. To solve Problem CRSG, we are going to use the data structure of Agarwal et al. [START_REF] Agarwal | Range searching in categorical data: Colored range searching on grid[END_REF] 7 . This data structure can answer the query of Problem CRSG in O(log log U + K) time, where K is the number of points contained in the query rectangle q. The data structure can be built in O(n log n log 2 U ) time and requires O(n log 2 U ) space. Algorithm 1 formally states the steps to build our data structure. In the rest of this paper, we refer to this data structure as IDS PMI.

Algorithm 1 Algorithm to build IDS PMI

One final remark is that, we can use the suffix array instead of suffix tree as well with some standard modifications in Algorithm 1.

Analysis

Let us now analyze the cost of building the index data structure IDS PMI. To build IDS PMI, we first construct a traditional suffix tree requiring O(n log Σ) time. The preprocessing on the suffix tree can be done in O(n) by traversing ST T using a breadth first or in order traversal. The color array C can be setup in O(n) because π is a set of disjoint intervals and it can cover, at most, n points. The construction of the set A of points in the grid [0..n]×[0..n], on which we will apply the range search, can also be done in O(n) as follows. Assume that L is the linked list realizing LL(R). Each element in L is the label of the corresponding leaf in LL(R). We construct L -1 such that L -1 [L[i]] = i. It is easy to see that with L -1 in our hand we can easily construct A in O(n). After A is constructed we build the data structure to solve Problem CRSG which requires O(n log 3 n) time and O(n log 2 n) space because U = n. Since, we can assume Σ ≤ n, the index IDS PMI can be constructed in O(n log 3 n) time.

Algorithm 2 Algorithm for Query Processing 1: Find µ P in STT . 2: Set i = µ P .lef t, j = µ P .right. 3: Compute the set B, where B is the set of distinct colors in the set of points contained in q ≡ (i, ℓ) × (j, r)

4: return Occ P T [ℓ..r],π = {C -1 [x] | x ∈ B and x = c f ixed }

Query processing

So far we have concentrated on the construction of IDS PMI. Now we discuss the query processing. Suppose we are given a query pattern P along with a query interval [ℓ..r]. We first find the locus µ P in ST T . Let i = µ P .lef t and j = µ P .right. Then we perform a colored range search query on A with the rectangle q ≡ (i, ℓ)×(j, r). Let B is the set of those colors as output by the query. Then it is easy to verify that Occ P T [ℓ..r],π = {C And in fact, as we show below, we can solve Problem PMGI optimally. We first discuss how we construct the data structure, namely IDS PMGI, to solve PMGI. As before, we start by constructing a suffix tree (or suffix array) ST T . Then we do all the preprocessing done on ST T as we did to construct IDS PMI. We also construct the color array C. This time however, we do a slightly different encoding as follows. For each k ∈ [1.

.n], we assign

C[k] = -1, if there exists an i such that s i ≤ k ≤ f i , [s i ..f i ] ∈ π. For all other k ∈ [1.
.n] we assign C[k] = 0. In other words, all the positions of the text T , not covered by any of the intervals of π gets 0 as their color and every other positions gets the color -1. Now we make use of the following interesting problem.

Problem "RMIN" (Range Minima Query Problem). We are given an array A[1..n] of numbers. We need to preprocess A to answer following form of queries: Query: Given an interval I = [i s ..i e ], 1 ≤ i s ≤ i e ≤ n, the goal is to find the index k (or the value A[k] itself ) with minimum (maximum, in the case of Range Maxima Query) value A[k] for k ∈ I.

Problem RMIN has received much attention in the literature and Bender and Farach-Colton showed that we can build a data structure in O(n) time using O(n log n)-bit space and can answer subsequent queries in O(1) time per query [START_REF] Bender | The lca problem revisited[END_REF] 8 . Recently, Sadakane [START_REF] Sadakane | Succinct data structures for flexible text retrieval systems[END_REF] presented a succinct data structure which achieves the same time complexity using O(n) bits of space. Now, we preprocess the array C to answer the range minima queries (RMQ). Note that, in C, we have only two values. So to define a unique value in case of a tie, we consider the index along with the value. More formally, we define

C[i] ≺ C[j], 1 ≤ i = j ≤ n if and only if C[i] ≤ C[j
] and i < j. And we employ RMQ using the relation ≺. This can be easily done in O(n) slightly modifying the preprocessing used in [START_REF] Bender | The lca problem revisited[END_REF] 9 . Finally, for each C[i] = -1, we maintain a pointer to C[j] = -1 such that j > i and j is the smallest index with this property; if there doesn't exist any such C[j], then C[i] points to 'NULL'. More formally, we maintain another array D [1..n] such that for all i ∈ [1..n] with C[i] = -1, we have

D[i] = j, if and only if, C[j] = -1 and C[k] = 0, i < k < j.
For all other index the D is given a 'NULL' value. This completes the construction of IDS PMGI. Note that, the overall running time to construct IDG PMGI remains dominated by the construction of the suffix tree ST T . As a result, the construction time is O(n) for bounded alphabet and O(n log Σ) otherwise.

Now we discuss how we perform the query on IDS PMGI. Suppose we are given a query pattern P. We first find the locus µ P in ST T . Let i = µ P .lef t and j = µ For bounded alphabets, we have the following result.

Problem PMQI

This section is devoted to Problem PMQI. As is mentioned above, PMQI was studied extensively in [START_REF] Mäkinen | Position-restricted substring searching[END_REF]. The best query time achieved in [START_REF] Mäkinen | Position-restricted substring searching[END_REF] was O(m + log log n + |Occ P T [ℓ..r] |) against a data structure exhibiting O(n log 1+ǫ n) space and time complexity, where 0 ≤ ǫ ≤ 1. Note that, we can easily use IDS PMI to solve PMQI by assuming π = {[1..n]}. So, with a slightly worse data structure construction time, we can achieve the same query time of [START_REF] Mäkinen | Position-restricted substring searching[END_REF] to solve PMQI using our data structure IDS PMI to solve a more general problem, namely PMI. However, as pointed out in [START_REF] Mäkinen | Position-restricted substring searching[END_REF], it would be really interesting to get an optimal query time for this problem. In this section, we attain an optimal query time for PMQI. However, the optimal query time is achieved against a O(n 2 ) preprocessing time.

The data structure, namely IDS PMQI, is constructed as follows. As before, we start by constructing a suffix tree (or suffix array) ST T . Then we do all the preprocessing done on ST T as we did to construct IDS PMI and IDS PMGI. Recall that, with ST T in our hand, preprocessed as above, we can have the set Occ P T in the form of L[i..j] in O(m) time. To achieve the optimal query time we now must 'select' k ∈ L[i..j] such that k ∈ [ℓ..r] without spending more than constant time per selection. To achieve this goal we introduce the following interesting problem.

Problem "RNV" (Range Next Value Query Problem). We are given an array A[1..n], which is an permutation of [1..n]. We need to preprocess A to answer the following form of queries. Query: Given an integer k ∈ [1..n], and an interval [i..j], 1 ≤ i ≤ j ≤ n, the goal is to return the index of the immediate higher (or equal) number ('next value') than k from A[i..j] if there exists one. More formally, we need to return ℓ (or A[ℓ] as the value itself ) such that i ≤ ℓ ≤ j and A

[ℓ] = min{A[q] | A[q] ≥ k and i ≤ q ≤ j}
Despite extensive results on various range searching problems we are not aware of any result that directly addresses this problem. Recall that our goal now is to answer the RNV queries in O(1) time per query. We below give a solution where we can preprocess A in O(n 2 ) time and then can answer the subsequent queries in O(1) time per query. The idea is is as follows. We maintain n arrays B i , 1 ≤ i ≤ n. Each array, B i has n elements. So we could view B as a two dimensional array as well. We fill each array B i depending on A as follows. For each 1 ≤ i ≤ n we store in B i the difference between i and the corresponding element of A and then replace all negative entries of B i with ∞. More formally, for each 1 ≤ i ≤ n and for each 1 ≤ j ≤ n we set B i [j] = A[j] -i if A[j] ≥ i; otherwise we set B i [j] = ∞. Then we preprocess each B i , 1 ≤ i ≤ n for range minima query [START_REF] Bender | The lca problem revisited[END_REF]. This completes the construction of the data structure. It is clear that it will require O(n 2 ) time. The query processing is as follows. Suppose the query parameters are k and [i..j]. Then we simply apply range minima query in B k for the interval [i..j]. So we have the following theorem. .r] as output by our algorithm will always remain sorted according to their position in T , which in many applications may turn out to be useful.

Conclusion

In this paper, we have considered the problem of pattern matching in given intervals and focused on building index data structure to handle different versions of this problem efficiently. We first handled the more general problem PMI and presented an efficient data structure requiring O(n log T ,π |) query time). Finally, we improved the query time of [START_REF] Mäkinen | Position-restricted substring searching[END_REF] for Problem PMQI to optimal i.e. O(m + |Occ P T [ℓ..r] |) per query, although, at the expense of a more costly data structure requiring O(n 2 ) time and space. It would be interesting to improve the preprocessing time of both Problem PMI and PMQI and also the query time of the former. Of particular interest is the improvement of the O(n 2 ) data structure of PMQI without sacrificing the optimal query time. Furthermore, we believe that Problem RNV is of independent interest and could be investigated further.

  we construct a 'color array' C to assign colors to each k ∈ [1..n] as follows. For each k ∈ [1..n] we assign C[k] = c k , if there exists an i such that s i ≤ k ≤ f i , [s i ..f i ] ∈ π; we then say that the color of k is c k . Any other k ∈ [1..n] is assigned a fixed different color, say c f ixed . In other words, all the positions of the text T , not covered by any of the intervals of π are given a fixed color c f ixed and every other position carries a distinct color each. We also realize the inverse relation in the form of the array, C -1 , such that C -1 [c k ] = k, if and only if, C[k] = c k and c k = c f ixed . Note that, there may exist more than one positions having color c f ixed . We define C -1 (c f ixed ) = ∞. Now we can reduce our problem to Problem CRSI as follows. We have two arrays LL(R) and M and, respectively, two intervals [ℓ T ..r T ] and [ℓ..r]. Also we have color array C, which associates a (not necessary distinct) color to each i ∈ [1.

1 :

 1 Build a suffix tree STT of T . Let the root of STT is R. 2: Label each leaf of STT by the starting location of its suffix. 3: Construct a linked list L realizing LL(R). Each element in L is the label of the corresponding leaf in LL(R). 4: for each node v in STT do 5: Store v.lef t = i and v.right = j such that L[i] and L[j] corresponds to, respectively, (leftmost leaf) v ℓ and (rightmost leaf) vr of v. 6: end for 7: for i = 1 to n do 8: Set M[i] = i 9: end for 10: for i = 1 to n do 11: Set C[i] = c f ixed 12: end for 13: for i = 1 to |π| do 14: for j = si to fi do 15: C[j] = cj 16: end for 17: end for 18: for i = 1 to n do 19: Set A[i] = ǫ 20: end for 21: for i = 1 to n do 22: if there exists (x, y) such that M[x] = L[y] = i then 23: Set A[i] = A[i] S (x, y) 24: end if 25: end for 26: Preprocess A (and C) for Colored Range Search on a Grid [0..n] × [0..n].

  -1 [x] | x ∈ B and x = c f ixed }. The steps are formally presented in the form of Algorithm 2. The running time of the query processing is deduced as follows. Finding the locus µ P requires O(m) time. The corresponding pointers can be found in constant time. The construction of the set B is done by performing the range query and hence requires O(log log n + |B|) time. Note that |B| is either equal to |Occ P T [ℓ..r],π | or just one unit more than that. The latter happens when we have c f ixed ∈ B. So, in total the query time is O(m + log log n + |Occ P T [ℓ..r],π | + 1) = O(m + log log n + |Occ P T [ℓ..r],π |). We state the results of this section in the form of following theorem. Theorem 1. For Problem PMI, we can construct the IDS PMI data structure in O(n log 3 n) time and O(n log 2 n) space and we can answer the relevant queries in O(m + log log n + |Occ P T [ℓ..r],π |) time per query.

Theorem 3 .

 3 P .right. Now we basically have the set Occ P T in L[i..j]. Now we perform a range minima query on C with the query interval [i..j]. This gives us, in constant time [8], the first index k ∈ [i..j] such that C[k] = -1. Then we follow the linked list realized by D to report all the indices in the range [i..j] having color -1. More formally, we construct the set B = {k | k ∈ [i..j] and C[k] = -1}. With the help of D this can be done in O(|B|) time. And it is easy to realize that Occ P T ,π = {L[i] | i ∈ B}. Therefore we can perform the query in optimal O(m + |Occ P T ,π |) time. The following theorem present the results achieved in this section. For Problem PMGI, we can construct the IDS PMGI data structure in O(n log Σ) time and O(n log n) bits of space and the relevant queries can be answered optimally in O(m + |Occ P T ,π |) time per query.

Theorem 4 .

 4 For Problem PMGI, we can construct the IDS PMGI data structure in O(n) time and O(n log n) bits of space and the relevant queries can be answered optimally in O(m + |Occ P T ,π |) time per query.

Theorem 5 .Theorem 6 .

 56 For Problem RNV, we can construct a data structure in O(n 2 ) time and space to answer the relevant queries in O(1) time per query. Now we show how we can use the result of Theorem 5 to answer the queries of Problem PMQI optimally. To complete the construction of IDS PMQI, we preprocess the array L for Problem RNV. The query processing is as follows. Recall that, we can have the set Occ P T in the form of L[i..j] in O(m) time. Recall also that as part of the PMQI query, we are given an interval [ℓ..r]. Now we perform an RNV query on L with the parameters ℓ and [i..j]. Suppose the query returns the index q. It is easy to see that if L[q] ≤ r, then L[q] ∈ Occ P T [ℓ..r] . And then we repeat the RNV query with parameters L[q] and [i..j]. We stop as soon as a query returns an index q such that L[q] > r. So, in this way, given L[i..j], we can get the set Occ P T [ℓ..r] in O(|Occ P T [ℓ..r] |) time. So we have the following theorem. For Problem PMQI, we can construct a data structure, namely IDS PMQI, in O(n 2 ) time and space to answer the relevant query in optimal O(m + |Occ P T [ℓ..r] |) time. It is clear that the bottleneck in the construction time lies in the preprocessing of Problem RNV. So any improvement on Theorem 5 would improve Theorem 6 as well. One interesting fact is that, the occurrences in Occ P T [ℓ.

  3 n) time and O(n log 2 n) space with a query time of O(m + log log n + |Occ P T [ℓ..r],π |) per query. We then solved Problem PMGI optimally (O(n) time and O(n log n)-bits space data structure and O(m + |Occ P

  ] in a text T[1..n]. The pattern P is said to occur at position i ∈ [1..n] of T if and only if P = T [i..i + m -1]. We use Occ P T to denote the set of occurrences of P in T .The problems we handle in this paper can be defined formally as follows. Suppose we are given a text T of length n and a set of disjoint intervalsπ = {[s 1 ..f 1 ], [s 2 ..f 2 ], . . . , [s |π| ..f |π| ]} such that s i , f i ∈ [1..n] and s i ≤ f i , for all 1 ≤ i ≤ |π|.Preprocess T to answer following form of queries. Suppose we are given a text T of length n and a set of intervals π= {[s 1 ..f 1 ], [s 2 ..f 2 ], . . . , [s |π| ..f |π| ]} such that s i , f i ∈ [1..n] and s i ≤ f i , for all 1 ≤ i ≤ |π|.

	Problem "PMQI" (Pattern Matching in a Query Interval). Suppose we
	are given a text T of length n. Preprocess T to answer following form of queries.
	Query: Given a pattern P and a query interval [ℓ..r], with 1 ≤ ℓ ≤ r ≤ n, con-
	struct the set
	Occ P T [ℓ..r] = {i | i ∈ Occ P T and i ∈ [ℓ..r]}.
	Problem "PMGI" (Pattern Matching in Given Intervals). Query: Given a pattern P construct the set
	Occ P T ,π = {i | i ∈ Occ P T and i ∈ ̟ f or some ̟ ∈ π}.
	Problem "PMI" (Generalized Pattern Matching with Intervals). Preprocess
	T to answer following form of queries.
	Query: Given a pattern P and a query interval [ℓ..r] such that ℓ, r ∈ [1..n] and
	ℓ ≤ r, construct the set
	Occ P T [ℓ..r],π = {i | i ∈ Occ P T and i ∈ [ℓ, r] ̟ f or some ̟ ∈ π}.

  In Section 3, we have presented an efficient index data structure, namely IDS PMI, to solve Problem PMI. In this section, we consider Problem PMGI. Since PMI is a generalized version of PMGI, we can easily use the solution in Section 3 to solve PMGI. We use the same data structure IDS PMI. During the query, since PMGI doesn't have any query interval, we just need to assume the query interval to be[1..n]. So we have the following theorem.Theorem 2. For Problem PMGI, we can construct the IDS PMI data structure in O(n log 3 n) time and O(n log 2 n) space and we can answer the relevant queries in O(m + log log n + |Occ P T ,π |) time per query. However, as it turns out, we can achieve better results for Problem PMGI.

	4 Problem PMGI

In[START_REF] Amir | Property matching and weighted matching[END_REF] a data structure requiring O(n log Σ+n log log n) time was presented to support O(m + K) time query, where K is the output size.

For bounded alphabet the running time remains linear, i.e. O(n).

To the best of our knowledge, this is the only data structure that handles the colored range query exploiting the grid property to gain efficiency.

In particular, the only modification needed is in the construction of the Cartesian tree.

⋆ Supported by EPSRC and Royal Society grants. ⋆⋆ Supported by the Commonwealth Scholarship Commission in the UK under the Commonwealth Scholarship and Fellowship Plan (CSFP). , BUET, Dhaka-1000, Bangladesh.


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

Lucian Ilie
email: ilie@csd.uwo.ca

W F Smyth
email: smyth@mcmaster.ca

A simple algorithm for computing the Lempel-Ziv factorization

We give a space-efficient simple algorithm for computing the Lempel-Ziv factorization of a string. For a string of length n over an integer alphabet, it runs in O(n) time independently of alphabet size and uses o(n) additional space.

Introduction

The Lempel-Ziv factorization of w [START_REF] Lempel | On the complexity of finite sequences[END_REF] is the decomposition w = u 0 u 1 • • • u k , where each u i (except possibly u k ) is the longest prefix of u i u i+1 • • • u k that has another occurrence to the left in w or a single letter in case this prefix is empty. For example, the string abbaabbbaaabab has the Lempel-Ziv factorization a.b.b.a.abb.baa.ab.ab.

The Lempel-Ziv factorization is a basic and powerful technique for text compression [START_REF] Ziv | A universal algorithm for sequential data compression[END_REF]. Introduced to analyze the entropy of strings it has many variants used in gzip or PKzip software, and, more generally, in dictionary compression methods. The above factorization is specifically used in LZ77-based adaptive compression methods (see [START_REF] Storer | Data compression via textual substitution[END_REF] or Section 2.5 in [START_REF] Witten | Managing Gigabytes[END_REF]).

The factorization plays an important role in String Algorithms. The intuitive reason is that when processing a string online, the work done on an element of the factorization can usually be skipped because already done on its previous occurrence. A typical application of this idea resides in algorithms to compute repetitions in strings, such as Kolpakov and Kucherov algorithm for reporting all maximal repetitions [START_REF] Kolpakov | On maximal repetitions in words[END_REF], and indeed it seems to be the only technique that leads to linear-time algorithms independently of the alphabet size (see [START_REF] Crochemore | Computing longest previous factor in linear time and applications[END_REF]).

To compute the Lempel-Ziv factorization, some methods use suffix trees [START_REF] Rodeh | Linear Algorithm for Data Compression via String Matching[END_REF], others suffix automata [START_REF] Crochemore | Transducers and repetitions[END_REF], but these two data structures are not the most space-efficient. Recently algorithms have been proposed [START_REF] Abouelhoda | Replacing suffix trees with enhanced suffix arrays[END_REF][START_REF] Crochemore | Computing longest previous factor in linear time and applications[END_REF][START_REF] Chen | Fast and practical algorithms for computing all runs in a string[END_REF] that use suffix arrays, a more space-efficient structure. We improve here the simplest of those, that of [START_REF] Crochemore | Computing longest previous factor in linear time and applications[END_REF], so that it uses o(n) additional space as opposed to O(n) of [START_REF] Crochemore | Computing longest previous factor in linear time and applications[END_REF].

Suffix arrays

We recall in this section briefly the notions of suffix array and longest common prefix. Consider a string w = w[0 . . n -1] of length n over an integer alphabet A, that is, an integer interval of size no more than n c , for some constant c. The suffix of w starting at position i is denoted by

suf i = w[i..n -1], for 0 ≤ i ≤ n -1.
The suffix array of w, [START_REF] Manber | Suffix arrays: a new method for on-line search[END_REF], denoted SA, gives the suffixes of w sorted ascendingly in lexicographical order, that is, suf

SA[0] < suf SA[1] < • • • < suf SA[n-1]
. The suffix array of the string abbaabbbaaabab is shown in the second column of Fig. 1. The suffix array of a string of length n over an integer alphabet can be computed in O(n) time by any of the algorithms in [START_REF] Kärkkäinen | Simple linear work suffix array construction[END_REF][START_REF] Kim | Constructing suffix arrays in linear time[END_REF][START_REF] Ko | Space efficient linear time construction of suffix arrays[END_REF]; these algorithms are inspired by the O(n) suffix tree construction algorithm of [START_REF] Farach | Optimal suffix tree construction with large alphabets[END_REF].

i w[i] SA[i] LCP[i] suf SA[i] LPF[i] 0 a 8 0 aaabab 0 1 b 9 2 aabab 0 2 b 3 3 aabbbaaabab 1 3 a 12
Often the suffix array is used in combination with another array, the Longest Common Prefix (LCP) which gives the length of the longest common prefix between consecutive suffixes of SA, that is, LCP[i] is the length of the longest common prefix of suf SA[i] and suf SA[i-1] ; see the fourth column of Fig. 1 for an example.

Recall that [START_REF] Kasai | Linear-time longest-commonprefix computation in suffix arrays and its applications[END_REF] give simple linear-time algorithms to compute the LCP array; its space complexity is improved in [START_REF] Manzini | Two space-saving tricks for linear-time LCP computation[END_REF].

We shall need also the Longest Previous Factor (LPF) array, defined as follows. For any position i in w, LPF[i] gives the length of the longest factor of w starting at position i that occurs previously in w. Formally, if w[i] denotes the ith letter of w and w[i . . j] is the factor

w[i]w[i + 1] . . . w[j], then LPF[i] = max {ℓ | w[i..i + ℓ -1] is a factor of w[0..i + ℓ -2]} ∪ {0} .
LPF was introduced in [START_REF] Crochemore | Computing longest previous factor in linear time and applications[END_REF]], but appears also as the λ array in [START_REF] Franek | Computing quasi suffix arrays[END_REF]. In our example, the LPF array as defined above is given in column 6 of Fig. 1.

The algorithm

As already mentioned, we compute first the LPF array. The Lempel-Ziv factorization is then easily computed from LPF by the algorithm of Fig. 2, already proposed in [START_REF] Crochemore | Computing longest previous factor in linear time and applications[END_REF]. For the example text w = abbaabbbaaabab of Fig. 1, this algorithm outputs the sequence of starting positions of factors, LZ = [0, 1, 2, 3, 4, 7, 10, 12].

Lempel-Ziv factorization(LPF)

1. LZ[0] ← 0; i ← 0 2. while (LZ[i] < n) do 3. LZ[i + 1] ← LZ[i] + max(1, LPF[LZ[i]]) 4. i ← i + 1 5.
return LZ Figure 2. Algorithm for computing Lempel-Ziv factorization using LPF.

In order to explain the idea for the computation of LPF, it is helpful to arrange the SA and LCP arrays in a graph, as done in [START_REF] Crochemore | Computing longest previous factor in linear time and applications[END_REF]. The vertices are labeled by the SA values and the edges by the LCP values. The vertices are arranged in left-to-right order corresponding to their order in SA and are placed at a height corresponding to their starting position in the string. In other words, if SA[i] = j, then the vertex labeled j is plotted with abscissa i and ordinate j. Each edge between two vertices is labeled by the corresponding LCP value. An example if shown by the graph in Fig. 3(i) (solid edges only). Note that the graph is purely conceptual: no graph is constructed by the algorithm.

The value LPF[SA [i]] can be immediately computed, that is, by local test only, in any of the following cases:

(i) SA[i -1] < SA[i] > SA[i + 1]
, that is, for a "peak" in the graph. In this case

LPF[SA[i]] = max(LCP[i], LCP[i + 1]
). Referring to Fig. 3, for i = 3, the value LPF[SA [START_REF] Crochemore | Transducers and repetitions[END_REF]] = LCP [START_REF] Kim | Constructing suffix arrays in linear time[END_REF] can be computed and it equals max(LCP [START_REF] Crochemore | Transducers and repetitions[END_REF], LCP [START_REF] Crochemore | Algorithms on Strings[END_REF]) = 2 (maximum of the labels of the two adjacent edges). Since SA[3] = 12, the vertex labeled 12 can then be removed from the graph. An edge between 3 and 10 is created, labeled by min(LCP [START_REF] Crochemore | Transducers and repetitions[END_REF], LCP [START_REF] Crochemore | Algorithms on Strings[END_REF]) = 1 (minimum of the two labels).

(ii)

SA[i -1] < SA[i] < SA[i + 1] and LCP[i] ≥ LCP[i + 1]
, that is, the SA-values are increasing but the LCP-values are decreasing. In this case nothing better (i.e., larger) than LCP[i] can be obtained from LCP[i + 1] and so LPF[SA[i]] = LCP[i]. For i = 6, the value LPF[SA [START_REF] Duval | Linear-Time Computation of Local Periods[END_REF]] = LCP [START_REF] Crochemore | Algorithms on Strings[END_REF] can be computed and it is equal to 3. As before, since SA[6] = 4, the vertex 4 can be removed and the vertices 0 and 13 connected by an edge labeled 0

= LCP[i + 1]. (iii) SA[i -1] > SA[i] > SA[i + 1] and LCP[i] ≤ LCP[i + 1]
, that is, the SA-values are decreasing but the LCP-values are increasing. This is symmetric to (ii). However, since we consider the vertices from left to right, the case (i) will prevent the case (iii) from ever being used.

We consider then the vertices in the order given by SA and use the above cases (i)-(ii) any time we can. We maintain a stack with positions waiting to be processed. A fake The difference between this algorithm and the one of [START_REF] Crochemore | Computing longest previous factor in linear time and applications[END_REF] starts with the fact that the latter uses only the case (i) above. The use of case (ii) reduces drastically the amount of additional space needed, from O(n) to o(n), as proved by a combinatorial argument that we present below.

Consider the space used by the stack. As noted above, the positions in the stack at any moment are in increasing order (from bottom to top), and both their SA-and LCP-values are strictly increasing as well. That is, if the content of the stack is (from bottom to top)

i 1 < i 2 < • • • < i k , then SA[i 1 ] < SA[i 2 ] < • • • SA[i k ] and LCP[i 1 ] < LCP[i 2 ] < • • • LCP[i k ].
According to our algorithm, LCP[i j ] contains at this moment the length of the longest common prefix of suf i j-1 and suf i j .

We now show that i j+2i j ≥ LCP[i j+1 ] using string-combinatorial arguments; see, e.g., [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF]. Assume the opposite inequality holds. Then the factor w[i j . . i j+1 + LCP[i j+1 ] -1] has period i j+1i j (due to overlap of the identical factors w[i j . . i j + LCP[i j+1 ] -1] and

w[i j+1 . . i j+1 +LCP[i j+1 ]-1]). Since LCP[i j+2 ] > LCP[i j+1 ] and w[i j+2 . . i j+2 +LCP[i j+1 ]-1] overlaps w[i j+1 . . i j+1 + LCP[i j+1 ] -1]
by at least i j+1i j positions, the primitive roots of the two periods must synchronize. Hence, the period i j+1i j continues past the position Compute LPF(SA, LCP)

1. SA[n] ← -1; LCP[n] ← 0 2.
push(0, S ) 3.

for i from 1 to n do 4.

while (S = ∅) and

5.

SA It is interesting to note that the upper bound we just proved on the maximum stack size is asymptotically optimal. For the strings w = abab 2 ab 3 . . . ab ℓ , the stack needs to store simultaneously ℓ elements, 0, 2, 5, 9, . . . , ℓ(ℓ+1) 2 -1; that is, it requires Θ( √ n) space.

We have proved

Theorem 1

The LPF array and the Lempel-Ziv factorization of a string of length n over an integer alphabet can be computed, using SA and LCP, in O(n) time independently of alphabet size and o(n) additional space.

Conclusion

We discuss briefly a number of variations of our Compute LPF algorithm that are possible with small changes.

First, all features of the algorithm of [START_REF] Crochemore | Computing longest previous factor in linear time and applications[END_REF] are preserved. One of them is that we can keep LCP unchanged simply by storing (i, LCP[i]) pairs on the stack. Another one, the algorithm of [START_REF] Crochemore | Computing longest previous factor in linear time and applications[END_REF] computes also the PrevOcc array, which gives a previous position where a factor of length LPF[i] starts. The present algorithm can compute PrevOcc in the same way.

Second, the LPF keyed to SA instead of w can be computed, that is, if we denote the new array by LPF ′ , then LPF ′ This may be useful, for instance, if we want to save more space by computing LPF in place of LCP. (The LCP array is, by definition, keyed to SA.) In such a case, we would replace LPF by LCP and remove the steps 10 and 11.

Note that, for our initial purpose, computation of the Lempel-Ziv factorization, we would have then to compute LPF keyed to w, which can be done easily in place (using constant additional space).

Figure 3 .

 3 Figure 3. (i) Solid labeled edges form the graph representing SA and LCP for the text abbaabbbaaabab. (ii) The graph right before considering the vertex labeled 6.position is added at the end of SA -that is, SA[n] = -1, LCP[n] = 0 -to make sure that all positions are considered uniformly. The algorithm for computing LPF is given in Fig.4. Fig.3(ii) shows the modified graph right before the vertex labeled 6 is considered in step 3 (i = 11).The correctness of the algorithm follows from the above discussion. It runs in O(n) time because each position i, 0 ≤ i ≤ n -1, is pushed at most once onto the stack.The difference between this algorithm and the one of[START_REF] Crochemore | Computing longest previous factor in linear time and applications[END_REF] starts with the fact that the latter uses only the case (i) above. The use of case (ii) reduces drastically the amount of additional space needed, from O(n) to o(n), as proved by a combinatorial argument that we present below.Consider the space used by the stack. As noted above, the positions in the stack at any moment are in increasing order (from bottom to top), and both their SA-and LCP-values are strictly increasing as well. That is, if the content of the stack is (from bottom to top)i 1 < i 2 < • • • < i k , then

  [i] = j iff LPF[SA[i]] = j. We need only change LPF[SA[top(S )]] to LPF[top(S )] in steps 8 and 11.

Figure 1. The arrays SA, LCP, and LPF for the string w = abbaabbbaaabab.

				1 ab	1
	4	a	10	2 abab	3
	5	b	0	2 abbaabbbaaabab	2
	6	b	4	3 abbbaaabab	4
	7	b	13	0 b	3
	8	a	7	1 baaabab	2
	9	a	2	3 baabbbaaabab	3
	10	a	11	2 bab	2
	11	b	6	1 bbaaabab	2
	12	a	1	4 bbaabbbaaabab	2
	13	b	5	2 bbbaaabab	1

  j+1 + LCP[i j+1 ] -1 in w; that is, LCP[i j+1] is strictly shorter than the actual length of the longest common prefix of suf i j and suf i j+1 , a contradiction.Sincei j+2i j ≥ LCP[i j+1 ] and LCP[i j+1 ] > LCP[i j ],we easily obtain that k = O( √ n) and thus the maximum size of the stack is o(n).

		[i] < SA[top(S )] or
	6. 7.	(SA[i] > SA[top(S )]) and (LCP[i] ≤ LCP[top(S )]) if (SA[i] < SA[top(S )]) then	do
	8. 9. 10.	LPF[SA[top(S )]] ← max(LCP[top(S )], LCP[i]) LCP[i] ← min(LCP[top(S )], LCP[i]) else
	11. 12.	LPF[SA[top(S )]] ← LCP[top(S )] pop(S )
	13.	if (i < n) then push(i, S )
	14.	return LPF
		Figure 4. Algorithm for computing LPF.

i

Research supported in part by NSERC;