Maxime Crochemore

Costas S Iliopoulos

Gonzalo Navarro
email: gnavarro@dcc.uchile.cl

Yoan J Pinzon
email: pinzon@dcs.kcl.ac.uk

Alejandro Salinger
email: asalinge@dcc.uchile.cl

Bit-parallel (δ, γ)-Matching and Suffix Automata ⋆

Keywords: Bit-parallelism, approximate string matching, MIDI music retrieval

δ, γ)-Matching is a string matching problem with applications to music retrieval. The goal is, given a pattern P 1...m and a text T 1...n on an alphabet of integers, find the occurrences P ′ of the pattern in the text such that (i)

The problem makes sense for δ ≤ γ ≤ δm. Several techniques for (δ, γ)-matching have been proposed, based on bit-parallelism or on skipping characters. We first present an O(mn log(γ)/w) worst-case time and O(n) average-case time bit-parallel algorithm (being w the number of bits in the computer word). It improves the previous O(mn log(δm)/w) worst-case time algorithm of the same type. Second, we combine our bit-parallel algorithm with suffix automata to obtain the first algorithm that skips characters using both δ and γ. This algorithm examines less characters than any previous approach, as the others do just δ-matching and check the γ-condition on the candidates. We implemented our algorithms and drew experimental results on real music, showing that our algorithms are superior to current alternatives with high values of δ.

Introduction

The string matching problem is to find all the occurrences of a given pattern P 1...m in a large text T 1...n , both being sequences of characters drawn from a finite character set Σ. This problem is fundamental in computer science and is a basic need of many applications, such as text retrieval, music retrieval, computational biology, data mining, network security, etc. Several of these applications require, however, more sophisticated forms of searching, in the sense of extending the basic paradigm of the pattern being a simple sequence of characters.

In this paper we are interested in music retrieval. A musical score can be viewed as a string: at a very rudimentary level, the alphabet could simply be the set of notes in the chromatic or diatonic notation, or the set of intervals that appear between notes (e.g. pitch may be represented as MIDI numbers and pitch intervals as number of semitones). It is known that exact matching cannot be used to find occurrences of a particular melody, so one resorts to different forms of approximate matching, where a limited amount of differences of diverse kinds are permitted between the search pattern and its occurrence in the text.

The approximate matching problem has been used for a variety of musical applications [START_REF] Mcgettrick | MIDIMatch: Musical Pattern Matching in Real Time[END_REF][START_REF] Crawford | String matching techniques for musical similarity and melodic recognition[END_REF][START_REF] Roland | Musical pattern extraction and similarity assessment[END_REF][START_REF] Smith | A speech interface for building musical score collections[END_REF][START_REF] Cambouropoulos | Pattern processing in melodic sequences: Challenges, caveats and prospects[END_REF]. Most computer-aided musical applications adopt an absolute numeric pitch representation (most commonly MIDI pitch and pitch intervals in semitones; duration is also encoded in numeric form). The absolute pitch encoding, however, may be insufficient for applications in tonal music as it disregards tonal qualities of pitches and pitch-intervals (e.g., a tonal transposition from a major to a minor key results in a different encoding of the musical passage and thus exact matching cannot detect the similarity between the two passages). One way to account for similarity between closely related but non-identical musical strings is to permit a difference of at most δ units between the pattern character and its corresponding text character in an occurrence, e.g., a C-major {60, 64, 65, 67} and a C-minor {60, 63, 65, 67} sequence can be matched if a tolerance δ = 1 is allowed in the matching process. Additionally, we require that the total number of differences across all the pattern positions does not exceed γ, in order to limit the total number of differences while keeping sufficient flexibility at individual positions.

The formalization of the above problem is called (δ, γ)-matching. The problem is defined as follows: the alphabet Σ is assumed to be a set of integer numbers, Σ ⊂ Z. Apart from the pattern P and the text T , two extra parameters, δ, γ ∈ N, are given. The goal is to find all the occurrences P ′ of P in T such that (i) ∀1 ≤ i ≤ m, |P i -P ′ i | ≤ δ, and (ii) 1≤i≤m |P i -P ′ i | ≤ γ. Note that the problem makes sense for δ ≤ γ ≤ δm: If γ > δ then the limit on the sum of differences is larger than the limit on any difference, so one should set δ ← γ; and if γ > δm then condition (i) implies (ii) and we should set γ ← δm.

Several recent algorithms exist to solve this problem. These can be classified as follows:

Bit-parallel: The idea is to take advantage of the intrinsic parallelism of the bit operations inside a computer word of w bits [START_REF] Baeza-Yates | Text retrieval: Theory and practice[END_REF], so as to pack several values in a single word and manage to update them all in one shot. In [START_REF] Cambouropoulos | Algorithms for computing approximate repetitions in musical sequences[END_REF][START_REF] Cambouropoulos | Algorithms for computing approximate repetitions in musical sequences[END_REF] this approach was used to obtain Shift-Plus, an O(n m log(δm)/w) worstcase time algorithm. The algorithm packs m counters whose maximum value is mδ, hence it needs m⌈log 2 (δm + 1)⌉ bits overall and O(m log(δm)/w) computer words have to be updated for each text character. Occurrence heuristics: Inspired by Boyer-Moore techniques [START_REF] Boyer | A fast string searching algorithm[END_REF][START_REF] Sunday | A very fast substring searching algorithm[END_REF], they skip some text characters according to the position of some characters in the pattern. In [START_REF] Cambouropoulos | Algorithms for computing approximate repetitions in musical sequences[END_REF], several algorithms of this type were proposed for δ-matching (a restricted case where γ = δm), and they were extended to general (δ, γ)matching in [START_REF] Crochemore | Occurence and substring heuristics for δ-matching[END_REF]. The extension is done by checking the γ-condition on each candidate that δ-matches the pattern. These algorithms are Tuned-Boyer-Moore, Skip-Search and Maximal-Shift, each of which has a counterpart in exact string matching. These algorithms are faster than the bit-parallel ones, as they are simple and skip text characters. Substring heuristics: Based on suffix automata [START_REF] Czumaj | Speeding up two string-matching algorithms[END_REF][START_REF] Crochemore | Text algorithms[END_REF], these algorithms skip text characters according to the position of some pattern substrings. In [START_REF] Crochemore | Occurence and substring heuristics for δ-matching[END_REF][START_REF] Crochemore | Three heuristics for δ-matching: δ-BM algorithms[END_REF], three algorithms of this type, called δ-BM1, δ-BM2 and δ-BM3, are proposed. They try to generalize the suffix automata to δ-matching, but they obtain only an approximation that accepts more occurrences than necessary, and these have to be verified later. They also verify the γ-condition over each δ-matching candidate.

In this paper we present two new (δ, γ)-matching algorithms:

• We improve Shift-Plus in two aspects. First, we show that its worst case complexity can be reduced to O(n m log(γ)/w) by means of a more sophisticated counter management scheme that needs only ⌈1 + log 2 (γ + 1)⌉ bits per counter. Second, we show how its average-case complexity can be reduced to O(n). • We combine our bit-parallel algorithm with suffix automata, as already done with other string matching problems [START_REF] Navarro | Fast and flexible string matching by combining bitparallelism and suffix automata[END_REF][START_REF] Navarro | Flexible Pattern Matching in Strings -Practical on-line search algorithms for texts and biological sequences[END_REF], so as to obtain the first algorithm able of skipping text characters based both on δ-and γ-conditions. All previous algorithms skip characters using the δ-condition only. Moreover, our suffix automaton accepts exactly the suffixes of strings that (δ, γ)-match our pattern, so no candidate verification is necessary at all. Our algorithm examines less characters than any previous technique.

The algorithms are very efficient and simple to implement. Our experimental results on real music data show that they improve previous work when δ is large (so that their dependence on γ rather than on δ shows up). For short patterns, of length up to 20, the character skipping algorithm is the best, otherwise our simple bit-parallel algorithm dominates.

Basic Concepts

In this section we present the concepts our paper builds on: bit-parallelism and suffix automata. We start by introducing some terminology.

A string x ∈ Σ * is a factor (or substring) of P if P can be written

P = uxv, u, v ∈ Σ * . A factor x of P is called a suffix (prefix) of P if P = ux (P = xu), u ∈ Σ * .
A bit mask of length r is simply a sequence of bits, denoted b r . . . b 1 . We use exponentiation to denote bit repetition (e.g. 0 3 1 = 0001). The length of the computer word is w bits, so the mask of length r ≤ w is stored somewhere inside the computer word. Also, we write [x] r to denote the binary representation of number x < 2 r using r bits. We also use C-like syntax for operations on the bits of computer words: "|" is the bitwise-or, "&" is the bitwise-and, and "∼" complements all the bits. The shift-left operation, "<<", moves the bits to the left and enters zeros from the right, that is,

Bit-Parallelism

In [START_REF] Baeza-Yates | A new approach to text searching[END_REF][START_REF] Wu | Fast text searching allowing errors[END_REF], a new approach to text searching was proposed. It is based on bitparallelism [START_REF] Baeza-Yates | Text retrieval: Theory and practice[END_REF], a technique consisting in taking advantage of the intrinsic parallelism of the bit operations inside a computer word. By using cleverly this fact, the number of operations that an algorithm performs can be cut down by a factor of at most w, the number of bits in the computer word. Since in current architectures w is 32 or 64, the speedup is very significant in practice.

The Shift-And algorithm [START_REF] Wu | Fast text searching allowing errors[END_REF] uses bit-parallelism to simulate the operation of a nondeterministic automaton that searches the text for the pattern (see Fig. 1). A plain simulation of that automaton takes time O(mn), and Shift-And achieves O(mn/w) worst-case time (optimal speedup).

The algorithm first builds a table B which for each character c ∈ Σ stores a 1 is active. That is, after having scanned text position j, we have d i = 1 whenever P 1...i = T j-i+1...j . Therefore, we report a match whenever d m is set.

We start with D = 0 m and, for each new text character T j , update D using the formula D ← ((D << 1) | 0 m-1 1) & B[T j ] because each state may be activated by the previous state as long as T j matches the corresponding arrow. The "| 0 m-1 1" after the shift corresponds to the selfloop at the beginning of the automaton (as state 0 is not represented in D). Seen another way, the i-th bit is set if and only if the (i -1)-th bit was set for the previous text character and the new text character matches the pattern at position i. In other words, T j-i+1...j = P 1...i if and only if T j-i+1...j-1 = P 1...i-1 and T j = P i .

The cost of this algorithm is O(n). For patterns longer than the computer word (m > w), the algorithm uses ⌈m/w⌉ computer words for the simulation, with a worst-case cost of O(mn/w). By managing to update only those computer words that have some active state, an average case cost of O(n) is achieved.

It is very easy to extend Shift-And to handle classes of characters, where each pattern position does not match just a single character but a set thereof. If C i is the set of characters at position i in the pattern, then we set the i-th bit of B[c] for all c ∈ C i .

Suffix Automata

We describe the BDM pattern matching algorithm [START_REF] Crochemore | Text algorithms[END_REF][START_REF] Czumaj | Speeding up two string-matching algorithms[END_REF], which is based on a suffix automaton. A suffix automaton on a pattern P 1...m is a deterministic finite automaton that recognizes the suffixes of P . The nondeterministic version of this automaton has a very regular structure (see in Fig. 2).

The (deterministic) suffix automaton is well known [START_REF] Crochemore | Text algorithms[END_REF]. Its size, counting both nodes and edges, is O(m), and it can be built in O(m) time [START_REF] Crochemore | Text algorithms[END_REF]. A very important fact is that this automaton can also be used to recognize the factors of P : The automaton is active as long as we have read a factor of P . This structure is used in [START_REF] Crochemore | Text algorithms[END_REF][START_REF] Czumaj | Speeding up two string-matching algorithms[END_REF] to design a pattern matching algorithm called BDM, which is optimal on average (O(n log |Σ| (m)/m) time on uniformly distributed text). To search a text T for P , the suffix automaton of P r = P m P m-1 . . . P 1 (the pattern read backwards) is built. A window of length m is slid along the text, from left to right. The algorithm reads the window right to left and feeds the suffix automaton with the characters read. During this process, if a final state is reached, this means that the window suffix we have traversed is a prefix of P (because suffixes of P r are reversed prefixes of P ). Then we store the current window position in a variable last, possibly overwriting its previous value. The backward window traversal ends in two possible forms:

(1) We fail to recognize a factor, that is, we reach a character σ that does not have a transition in the automaton (see Fig. 3). In this case the window suffix read is not a factor of P and therefore it cannot be contained in any occurrence. We can actually shift the window to the right, aligning its starting position to last, which corresponds to the longest prefix of P seen in the window. We cannot miss an occurrence because in that case the suffix automaton would have found its prefix in the window. (2) We reach the beginning of the window, therefore recognizing the pattern P . We report the occurrence, and shift the window exactly as in the previous case (we have the previous last value).

It is possible to simulate the suffix automaton in nondeterministic form by using bit-parallelism [START_REF] Navarro | Fast and flexible string matching by combining bitparallelism and suffix automata[END_REF][START_REF] Navarro | Flexible Pattern Matching in Strings -Practical on-line search algorithms for texts and biological sequences[END_REF], so as to obtain very efficient and simple algorithms.

Improving the Bit-Parallel Algorithm

First of all, notice that δ-matching is trivial under the bit-parallel approach, as it can be accommodated using the ability to search for classes of characters. We define that pattern character c matches text characters c -δ . . . c + δ.

Hence, if B[c] = b m . . . b 1 , we set b i = 1 if and only if |P i -c| ≤ δ.
The rest of the algorithm is unchanged and the same complexities are obtained.

The real challenge is to do (δ, γ)-matching. The solution we present is an improvement over that of [START_REF] Cambouropoulos | Algorithms for computing approximate repetitions in musical sequences[END_REF][START_REF] Cambouropoulos | Algorithms for computing approximate repetitions in musical sequences[END_REF] and it has some resemblances with that of [START_REF] Baeza-Yates | Fast string matching with mismatches[END_REF] for Hamming distance.

Let us focus for a moment on γ-matching alone. Instead of storing just one bit d i to tell whether P 1...i matches T j-i+1...j , we store a counter c i to record the sum of the absolute differences between the corresponding characters. That is

c i = 1≤k≤i |P k -T j-i+k | (1)
and we wish to report text positions where c m ≤ γ.

The next Lemma shows how to update the c i values for a new text position, and suggests an O(mn) time γ-matching algorithm.

Lemma 1. Assume that we want to compute the counters c 1 . . . c m according to Eq. ( 1) for text position j, and have computed c ′ 1 . . . c ′ m for position j -1. The c i values satisfy

c i = 1≤k≤i |P k -T j-i+k | = c ′ i-1 + |P i -T j | assuming c ′ 0 = 0.
Proof. Immediate by substitution of c ′ i-1 according to Eq. ( 1). 2

The update technique given in Lemma 1 is good for a bit-parallel approach.

Let us assume that each c i counter will be represented using ℓ bits, where ℓ will be specified later. Hence the state of the search will be expressed using the bit mask

D = [c m ] ℓ [c m-1 ] ℓ . . . [c 2 ] ℓ [c 1 ] ℓ . (2)
We precompute a mask

B[c] of counters [b m ] ℓ . . . [b 1 ] ℓ , so that b i = |P i -c|.
Then, the following Lemma establishes the bit-parallel formula to update D.

Eq. ( 2) for text position j, and have computed D ′ for position j -1. Then

D = (D ′ << ℓ) + B[T j ]. (3)
Proof.

The i-th counter of D ′ is c ′ i . After the shift-left ("<<") the i-th

counter becomes c ′ i-1 . The i-th counter of B[T j ] is |P i -T j |.
Hence the i-th counter of the right hand side of the equality is

c ′ i-1 + |P i -T j |. According to Lemma 1, this is c i . 2
This gives us a solution for γ-matching. Start with D = ([γ + 1] ℓ ) m (to avoid matching before reading T m ) and update it according to Eq. ( 3). Every time we have c m ≤ γ, report the last text position processed as the end of an occurrence.

In order to include δ-matching in the picture, we change slightly the definition of B[c]. The goal is that if, at any position, it holds |P i -T j | > δ, then we ensure that the corresponding occurrence is discarded. For this sake, it is enough to redefine

B[c] = [b m ] ℓ . . . [b 1 ] ℓ as follows: b i = if |P i -c| ≤ δ then |P i -c| else γ + 1. (4)
The next Lemma establishes the suitability of the above formulas for (δ, γ) matching.

Lemma 3. If the update formula of Eq. ( 3) is applied and B[c] is defined according to Eq. ( 4), then after processing text position j it holds that c m ≤ γ if and only if T j-m+1...j (δ, γ)-matches P .

Proof. By Lemmas 1 and 2 and Eq. ( 1) we have that, if the original definition

b i = |P i -c| is used, then c m = 1≤k≤m |P k -T j-m+k |
after processing text position j. The only difference if the definition of Eq. ( 4) is used is that, if any of the |P k -T j-m+k | was larger than δ, then b k > γ for B[T j-m+k ], and therefore c k > γ after processing text position j -m + k. Since counters only increase as they get shifted and added in Eq. ( 3), that counter c k at position j -m + k will become counter c m at position j, without decreasing. Thus c m > γ after processing text position j. Therefore c m ≤ γ if and only if T j-m+1...j (δ, γ)-matches P . 2

Let us consider now the ℓ value. In principle, using B[c] as in Eq. ( 4), counter c m can be as large as m(γ + 1), since b i ≤ γ + 1 (recall that δ ≤ γ). However, recall that counter values never decrease as they get shifted over D. This means that, once they become larger than γ, we do not need to know how larger they are. Thus, instead of storing the real c i value, we would rather store min(c i , γ + 1), and then need only ⌈log 2 (γ + 2)⌉ bits per counter.

In principle, whenever c i exceeds γ, we store γ + 1 for it. The problem is how to restore this invariant after adding B[c] to the counters, and also how to avoid overflows in that summation. We show now that we can handle both problems by using the following number of bits per counter:

ℓ = 1 + ⌈log 2 (γ + 1)⌉. (5)
Thus, our bit mask D needs mℓ = m(1+⌈log 2 (γ +1)⌉) bits and our simulation needs O(m log(γ)/w) computer words.

Instead of representing counter c i as [c i ] ℓ , we represent it as

c i -→ [c i + 2 ℓ-1 -(γ + 1)] ℓ . (6)
This guarantees that the highest bit of the counter will be set if and only if c i ≥ γ + 1, as its representation will be ≥ 2 ℓ-1 .

Before adding B[T j ], we will record all those highest bits in a bit mask H = D & (10 ℓ-1 ) m , and clear those highest bits from D. Once its highest bit is cleared, every counter representation is smaller than 2 ℓ-1 and we can safely add b i without overflowing the counters, since the resulting value is at most 2 ℓ-1 -1 + (γ + 1) = 2 ℓ-1 + γ ≤ 2γ + 1 because of Eq. ( 5). And again because of Eq. ( 5), a counter can hold up to value 2(γ + 1) -1 = 2γ + 1. After adding B[T j ] we restore those highest bits set in H.

Note that it is not strictly true that we maintain min(c i , γ + 1), but it is true that the highest bit of the representation of c i is set if and only if c i > γ, and this is enough for the correctness of the algorithm. The next Lemma establishes this correctness.

Lemma 4.

Assume that c i is represented as in Eq. ( 6) if c i ≤ γ, and as [2 ℓ-1 +x] ℓ otherwise, for some x ≥ 0. Then, if the update formula of Lemma 2 is applied with the exception that the highest bits set in the counters are removed before and restored after adding B[T j ], then it holds that the representation is maintained after processing T j .

Proof. If c i already exceeded γ before adding b i , it will exceed γ after adding b i . In this case, the representation of c i was 2 ℓ-1 + x and thus it already had its highest bit set. This bit will be restored after adding b i . Thus, regardless of which value actually stores, the representation will correctly maintain its highest bit set, that is, it will be of the form 2 ℓ-1 + x for some x ≥ 0.

On the other hand, if c i did not exceed γ before adding b i , then its representation was c i + 2 ℓ-1 -(γ + 1) and the highest bit was not set. Thus the manipulation of highest bits will not affect its result. After the summation the representation will hold c i + b i + 2 ℓ-1 -(γ + 1). This is a correct representation for the new value c i + b i , either if c i + b i ≤ γ or if c i + b i > γ, as in the latter case the representation is of the form 2 ℓ-1 + x, where x = c i + b i -(γ + 1) ≥ 0. 2 Fig. 4 depicts the algorithm. It is called Forward-Scan to distinguish it from our next algorithms that scan windows backward. The preprocessing consists of computing ℓ according to Eq. ( 5) and table B according to Eq. ( 4). Pattern P is processed backwards so as to arrange B[c] in the right order [b m ] ℓ . . . [b 1 ] ℓ . Line 10 initializes the search by setting c i = γ + 1 in D, according to the representation of Eq. ( 6). Occurrences are reported in lines 12-13, whenever c m ≤ γ, that is, the highest bit of the representation of c m is not set. Line 14 is the equivalent to D ← D << ℓ, except that the counter c 0 = 0 that is moved to the position of c 1 must be represented as 2 ℓ-1 -(γ + 1) according to Eq. ( 6). Line 15 computes H as explained, to record the highest bits. Line 16 completes the computation of Eq. ( 3), by removing bits set in H from D and restoring them after the summation with B[T j ].

Assuming that the bit masks fit in a computer word, that is, mℓ ≤ w, the algorithm complexity is O(m|Σ|+n). If several computer words are needed, the search complexity becomes O(mn log(γ)/w). However, we defer the details of handling longer bit masks to Section 5, as it is possible to obtain O(n) search time on average.

Forward-Scan

(P 1...m , T 1...n , δ, γ) 1. Preprocessing 2. ℓ ← 1 + ⌈log 2 (γ + 1)⌉ 3. for c ∈ Σ do 4. B[c] ← ([0] ℓ ) m 5.
for i ∈ m . . . 1 do if D & 10 mℓ-1 = 0 mℓ then 13.

6. if |c -P i | ≤ δ then 7. B[c] ← (B[c] << ℓ) | (|c -P i |) 8. else B[c] ← (B[c] << ℓ) | (γ + 1) 9. Search
Report an occurrence at j -m + 1

Using Suffix Automata

As demonstrated in [START_REF] Navarro | Fast and flexible string matching by combining bitparallelism and suffix automata[END_REF][START_REF] Navarro | Flexible Pattern Matching in Strings -Practical on-line search algorithms for texts and biological sequences[END_REF], the suffix automaton approach of Section 2.2 can be extended to search for more complex patterns by combining it with bitparallelism. In this section we combine our bit-parallel approach of Section 3 with the suffix automaton concept to obtain an algorithm that does not inspect all the text characters.

Imagine that we process a text window T pos+1...pos+m right to left. Our goal is that, after having processed T pos+j , we have computed

c i = 0≤k≤m-j |P r i-(m-j)+k -T pos+m-k | = 0≤k≤m-j |P 2m+1-i-j-k -T pos+m-k | (7) for m -j + 1 ≤ i ≤ m.
This can be obtained by initializing c i = 0 before starting processing the window and then updating the c i values according to the following Lemma.

Lemma 5. Assume that we have values c ′ i computed for T pos+j+1 according to Eq. [START_REF] Cambouropoulos | Algorithms for computing approximate repetitions in musical sequences[END_REF]. Then values c i for T pos+j satisfy

c i = c ′ i-1 + |P r i -T pos+j |.
Proof. It is immediate by rewriting c ′ i-1 according to Eq. ( 7). 2

If we maintain values c i computed according to Eq. ( 7), then, after processing T pos+j , (i) if c m ≤ γ, then 0≤k≤m-j |P 1+m-j-k -T pos+m-k | ≤ γ, that is, P 1...m-j+1 γ-matches window suffix T pos+j...pos+m ; (ii) if c i > γ for all m -j + 1 ≤ i ≤ m, then the window suffix T pos+j...pos+m does not γ-match any pattern substring P m-i+1...(m-i+1)+m-j , and therefore no occurrence can contain T pos+j...pos+m .

Therefore, a BDM-like algorithm would be as follows. Process text window T pos+1...pos+m by reading it right to left and maintaining c i values. Every time c m ≤ γ, mark the current window position last so as to remember the last time a window suffix γ-matched a pattern prefix. If, at some moment, c i > γ for all i, then shift the window to start at position last and restart. If all the window is traversed and still c m ≤ γ, then report the window as an occurrence and also shift it to start at position last. The correctness of this scheme should be obvious from Section 2.2.

A bit-parallel computation of the c i values is very similar to the one developed in Section 3, as the update formulas of Lemmas 1 and 5 are so close. In order to work on P r , we simply store B[c] in reverse fashion. Vector c i is initialized at c i = 0 according to Eq. ( 7). To determine whether c m ≤ γ we simply test the highest bit of its representation. To determine whether c i > γ for all i we test all highest bits simultaneously. To account also for δ-matching we change the preprocessing of B[c] just as in Eq. ( 4).

Fig. 5 depicts the algorithm, called "backward-scanning" because of the way windows are processed. The preprocessing is identical to Fig. 4 except that the pattern is processed left to right. D is initialized in line 13 with c i = 0 considering the representation of Eq. ( 6). Line 14 continues processing the window as long as c i ≤ γ for some i. The update to D is as in Fig. 4, except that the first shift left ("<<") of each window is omitted to avoid losing the first c 1 value. Condition c m ≤ γ is tested in line 18. When it holds, we update last unless we have processed all the window, in which case it means that we found an occurrence and also must maintain the previous last value. Line 21 shifts D and introduces values γ + 1 from the right, to ensure that the relevant i values are m -j + 1 ≤ i ≤ m and that the loop will terminate after m iterations. Finally, the window is shifted by last.

Backward-Scan

(P 1...m , T 1...n , δ, γ) 1. Preprocessing 2. ℓ ← 1 + ⌈log 2 (γ + 1)⌉ 3. for c ∈ Σ do 4. B[c] ← ([0] ℓ ) m 5.
for i ∈ 1 . . . m do 6.

if |c -P i | ≤ δ then

D ← ([2 ℓ-1 -(γ + 1)] ℓ ) m 14. while D & (10 ℓ-1 ) m = (10 ℓ-1 ) m do 15. H ← D & (10 ℓ-1 ) m 16. D ← ((D & ∼ H) + B[T j ]) | H 17. j ← j -1 18. if D & 10 mℓ-1 = 0 mℓ then 19. if j > 0 then last ← j 20.
else Report an occurrence at pos + 1 Note that, given the invariants we maintain, we can report occurrences with-out any further verification. Moreover, we shift the window as soon as the window suffix read does not (δ, γ)-match a pattern substring. This is the first character-skipping algorithm with these properties. Previous ones only approximate this property and require verifying candidate occurrences. Consequently, we inspect less characters than previous algorithms.

Handling Longer Patterns

Both algorithms presented are limited by the length of the computer word. They work for m(1 + ⌈log(γ + 1)⌉) ≤ w. However, in most cases this condition is not fulfilled, so we must handle longer patterns.

Active Computer Words

The first idea is just to use as many computer words as needed to represent D. In each computer word we store the maximum amount of counters that fully fit into w bits. So we keep κ = ⌊w/ℓ⌋ counters in each word (except the last one, that may be underfilled), needing ⌈m/⌊w/ℓ⌋⌉ words to represent D. Each time we update D we have to process all the words simulating the bit-parallel operations. With this approach, the forward scanning takes time O(nm log(γ)/w). We remark that previous forward scanning algorithms [START_REF] Cambouropoulos | Algorithms for computing approximate repetitions in musical sequences[END_REF][START_REF] Cambouropoulos | Algorithms for computing approximate repetitions in musical sequences[END_REF] required O(nm log(mδ)/w) time, which is strictly worse than our complexity. The difference is that we have managed to keep the counters below 2(γ + 1) instead of letting them grow up to mδ. This alternative is called simply "Forward" in the experiments.

A key improvement can be made to the forward scanning algorithm by noticing that it is not necessary to update all the computer words at each iteration. As counter c i stores the sum of all the differences between characters P 1...i and their corresponding characters in the text (Eq. ( 1)), depending on the values of δ and γ and on the size of the alphabet, most of the time the highest counters will have surpassed γ. Once a counter surpasses γ we only require that it stays larger than γ (recall Section 3 and Lemma 4), so it is not even necessary to update it. Let us say that a computer word is active when at least one of its counters stores some c i ≤ γ. The improvement works as follows:

• At each iteration of the algorithm we update the computer words only until the one we have marked as the last active word. • As we update each word we check whether it is active or not, remembering the new last active word.

• Finally, we check if the last counter of the last active word is ≤ γ. In that case, the word that follows the last active word must be the new last active word, as in the next iteration its first counter may become less than γ + 1, and hence we may need to process it.

This algorithm has the same worst-case complexity of the basic one, but the average case is significantly improved. Consider a random text and pattern following a zero-order model (that is, character probabilities are independent of the neighbor characters). Say that p s is the probability of the s-th character of the alphabet. Then the probability that P i δ-matches a random text character is π i = P i -δ≤s≤P i +δ p s . The probability of P 1...i δ-matching T j-i+1...j for a random text position j is

w i = Π 1≤k≤i π k .
The first computer word will be always active; the second will be active only if P 1...κ matches T j-κ+1...j ; the third will be active only if P 1...2κ matches T j-2κ+1...j ; and so on. Hence the average number of computer words active at a random text position is at most

1 + w κ + w 2κ + . . . = i≥0 w iκ
and this is O(1) provided π = max 1≤i≤m π i < 1, as in this case w i ≤ π i and the average number of active words is i≥0 w iκ ≤ i≥0 π iκ = 1/(1 -π κ ). 4Hence, as we update O(1) computer words on average, the average search time is O(n). Note that this holds even without considering γ, which in practice reduces the constant factor. The lower the values of δ and γ are, the better the performance will be. This alternative is called "Forward last" in the experiments.

Yet another improvement can be made to this algorithm by combining it with the basic single-word algorithm. We store the first word used to represent D in a register and run the algorithm using just this word, as long as this one is the only active word. Whenever the second word becomes active, we switch to the multiple word algorithm. We switch back to the basic algorithm whenever the first word becomes the last active word. The use of a register to store the first word yields a better performance, as we have to make less memory accesses. The more time the first word is the only active word, the more significant is the improvement. This alternative is called "Forward register" in the experiments.

Unfortunately this idea cannot be applied to the backward-scanning algorithm, as in this one we will have counters ≤ γ uniformly distributed across all the computer words. This happens because c i ≤ γ after reading T pos+j if P m-i+1...(m-i+1)+m-j (δ, γ)-matches T pos+j...pos+m (Eq. ( 7)), and this probability does not necessarily decrease with i (actually it is independent of i on a uniform distribution). The plain multi-word backward scanning algorithm is called simply "Backward" in the experiments.

Pattern Partitioning

Another idea to handle long patterns is to partition them into pieces short enough to be handled with the basic algorithm. Notice that if P (δ, γ)-matches T j-m+1...j , and we partition P into j disjoint pieces of length ⌊m/j⌋ and ⌈m/j⌉, then at least one piece has to (δ, γ ′ )-match its corresponding substring of T j-m+1...j , where γ ′ = ⌊γ/j⌋. The reason is that, otherwise, each piece adds up at least γ ′ + 1 differences, and the total is at least j(γ ′ + 1) = j(⌊γ/j⌋ + 1) > j(γ/j) = γ, and then γ-matching is not possible.

Hence we run j (δ, γ ′ )-searches for shorter patterns and check every match of a piece for a complete occurrence. The check is simple and does not even need bit parallelism. Note that if δ > γ ′ , we can actually do (γ ′ , γ ′ )-matching.

We must choose the largest j such that ⌈m/j⌉ (1 + ⌈log 2 (⌊γ/j⌋ + 1)⌉) ≤ w and hence we perform j = O(m log(γ)/w) searches. For forward scanning, each such search costs O(n). Piece verification time is negligible on average. Hence the average search time of this approach is O(nm log(γ)/w), which is not attractive compared to the worst-case search time of the basic approach. However, each of these searches can be made using registers for D, so in practice it could be relevant. It could be also relevant for backward matching, where using D in registers is not possible for long patterns.

Furthermore, the pieces can be grouped and searched for together using socalled "superimposition" [START_REF] Baeza-Yates | Faster approximate string matching[END_REF][START_REF] Navarro | Improving an algorithm for approximate string matching[END_REF]. By making groups of r pieces each, we perform ⌈j/r⌉ searches. For each search, counter b i of B[c] will store the minimum difference between c and the i-th character of any piece in the group, or γ ′ + 1 if none of these differences is smaller than γ ′ +1. Every time we find a match of the whole group we check the occurrence of each of the substrings forming that group. For all the pieces that matched we check the occurrence of the whole pattern at the corresponding position. The greater r is, the less searches we perform, but the more time we spend checking occurrences. The time spent in checking occurrences also increases with δ and γ. Because of this, the optimum r depends on δ,γ and m.

These algorithms are called "Forward superp" and "Backward superp" in the experiments. These include the case r = 1, where no superimposition is done.

Experimental Results

In this section we show experimental evidence comparing the different versions of our algorithms against δ-BM2 [10,11], which is the most efficient alternative (δ, γ)-matching algorithm.

The tests were performed using a Pentium IV, 2 GHz, 512 Mb RAM and 512 Kb cache running Suse Linux with w = 32. We used the GNU gcc compiler version 2.95.3. Each data point represents the median of 100 trials.

We ran our experiments using real music data obtained from a database of MIDI files of classic music, totalizing 10.5Mb of absolute pitches. We focused on typical parameter values for music searching, namely 2-4 for δ, 1.5m-2.0m for γ, and 10-200 for m.

The results for forward algorithms are shown in Fig. 6. The variants are called "Forward" (plain multiword forward), "Forward last" (same but updating only up to the last relevant word), "Forward register" (same but switching to single-word mode when possible), and "Forward superp" (partition plus superimposing in the way that gives the best results).

As expected, Forward and Forward-superp are the slowest and their cost grows linearly with m. Forward-superp shows a better constant factor and it is attractive for very short patterns, but soon its linear dependence with m renders it useless. Superimposition alleviates this only partially, as the optimum was to superimpose 2 to 7 patterns for δ = 2 and 2 to 5 for δ = 4. These numbers grow slowly as m increases and stay at a maximum of 5 or 6, making the whole scheme linear in m anyway.

Forward-last and Forward-register, on the other hand, display their O(n) average case time, independent of n. As expected, Forward-register is by far the best. We will consider only this alternative to compare against backward algorithms. Fig. 7 compares backward algorithms (which includes the relevant competing alternatives), and Forward-register. The backward algorithm only has variants "Backward" (plain single-or multi-word, as needed) and "Backward superp" (partition plus superimposing in the best possible way). δ-BM2 is the best existing alternative algorithm.

We observe that partitioning (including superimposition) is also a bad choice for backward scanning. The reasons are the same as for the forward version. In general, backward searching does not behave competitively when many computer words are involved. Backward was better than Forward-register when the whole (superimposed) representation fit in a single computer word. As more than a single word is necessary, Forward-register becomes superior. The reason is that backward searching needs to effectively update all its computer words, while the forward versions do so only for a few active computer words.

With respect to the competing algorithm, it can be seen that δ-BM2 is faster than ours for small δ = 2, but as we use a larger δ = 4 it becomes not competitive, as it can be expected from its only-δ filtration scheme. Our algorithms are the only ones that can filter using δ and γ simultaneously.

Finally, we notice that the dependence on δ is significant to the extent that it can double the time it takes by going from δ =2 to δ =4. The dependence on γ, on the other hand, is not much significant. We note, however, that Forwardregister is rather insensitive to both δ and γ, becoming a strong and stable choice for general (δ, γ)-matching.

Conclusions

We have presented new bit-parallel algorithms for (δ, γ)-matching, an extended string matching problem with applications in music retrieval. Our new algorithms make use of bit-parallelism and suffix automata and has several advantages over the previous approaches: they make better use of the bits of the computer word, they inspects less text characters, they are simple, extendible, and robust.

Especially important is that our algorithms are the first truly (δ, γ) characterskipping algorithms, as they skip characters using both criteria. Existing approaches do just δ-matching and check the candidates for the γ-condition. This makes our algorithms a stronger and more stable choice for this problem.

We have also presented several ideas to handle longer patterns, as the algorithms are limited by the length of the computer word. The fastest choice is an algorithm that uses several computer words and updates only those that hold relevant values, switching to single-word mode when possible.

b m b m- 1

 1 . . . b 2 b 1 << r = b m-r . . . b 2 b 1 0 r . Finally, we can perform arithmetic operations on the bits, such as addition and subtraction, which operate the masks as numbers. For instance, b r . . . b x 10000 -1 = b r . . . b x 01111.

Fig. 1 .

 1 Fig. 1. A nondeterministic automaton to search a text for the pattern P = "abcdefg". The initial state is 0. bit mask B[c] = b m . . . b 1 , so that b i = 1 if and only if P i = c. The state of the search is kept in a bit mask D = d m . . . d 1 , where d i = 1 whenever the state numbered i in Fig.1is active. That is, after having scanned text position j, we have d i = 1 whenever P 1...i = T j-i+1...j . Therefore, we report a match whenever d m is set.

Fig. 2 .

 2 Fig. 2. A nondeterministic suffix automaton for the pattern P = "abcdefg". Dashed lines represent ε-transitions. The initial state is I.

Fig. 3 .

 3 Fig. 3. Basic search with the suffix automaton

10 .D

 10 ← (10 ℓ-1 ) m 11.for j ∈ 1 . . . n do 12.

14 .DFig. 4 .

 144 Fig. 4. Bit-parallel algorithm for (δ, γ)-matching. Constant values are precomputed.

7 .B

 7 [c] ← (B[c] << ℓ) | (|c -P i |) 8. else B[c] ← (B[c] << ℓ) | (γ + 1) while pos ≤ n -m do 12. j ← m, last ← m 13.

21 .DFig. 5 .

 215 Fig. 5. Backward scanning algorithm for (δ, γ)-matching. Constant values are precomputed.

  δ = 2 and γ=2m (d) δ = 4 and γ=2m

Fig. 6 .

 6 Fig. 6. Timing figures for forward algorithms, in seconds per megabyte.

  δ = 2 and γ=2m (d) δ = 4 and γ=2m

Fig. 7 .

 7 Fig. 7. Timing figures for backward algorithms and the best forward algorithm, in seconds per megabyte.

This holds also if there are O(1) i values such that π i = 1.

We have shown that our algorithms are the best choice in practice when δ is not small enough to make up a good filter by itself. In this case, the ability of our algorithms to filter with γ at the same time becomes crucial.

We plan to investigate further on more sophisticated matching problems that arise in music retrieval. For example, it would be good to extend (δ, γ)matching in order to permit insertions and deletions of symbols, as well as transposition invariance. Bit-parallel approaches handling those options, albeit not (δ, γ)-matching at the same time, have recently appeared [15].

Another challenging problem is to consider text indexing, that is, preprocessing the musical strings to speed up searches later. A simple solution is the use of a suffix tree of the text combined with backtracking, which yields search times which are exponential on the pattern length but independent of the text length [23].

 [START_REF] Baeza-Yates | Text retrieval: Theory and practice[END_REF]Partly supported by CNRS and NATO. 2 Supported by CYTED VII.19 RIBIDI Project. 3 Funded by Millennium Nucleus Center for Web Research, Grant P01-029-F, Mideplan, Chile.


Maxime Crochemore¡

Costas S Iliopoulos¢ £¡

Thierry Lecroq¡
email: thierry.lecroq@univ-rouen.fr

Yoan J Pinzon¡
email: pinzon@dcs.kcl.ac.uk

Wojciech Plandowski
email: w.plandowski@mimuw.edu.pl

Wojciech Rytter
email: w.rytter@mimuw.edu.pl

Occurrence and Substring Heuristics for -Matching

Keywords: String algorithms, approximate string matching, dynamic programming, computerassisted music analysis

We consider a version of pattern matching useful in processing large musical data: ¤matching, which consists in finding matches which are ¤ -approximate in the sense of the distance measured as maximum difference between symbols. The alphabet is an interval of integers, and the distance between two symbols ¥ , ¦ is measured as § ¥ ©¦ § . We also consider ¤ -matching, where is a bound on the total sum of the differences. We first consider "occurrence heuristics" by adapting exact string matching algorithms to the two notions of approximate string matching. The resulting algorithms are efficient in practice. Then we consider "substring heuristics". We present ¤ -matching algorithms fast on the average providing that the pattern is "non-flat" and the alphabet interval is large. The pattern is "flat" if its structure does not vary substantially. The algorithms, named ¤ -BM1, ¤ -BM2 and ¤ -BM3 can be thought as members of the generalized Boyer-Moore family of algorithms. The algorithms are fast on average. This is the first paper on the subject, previously only "occurrence heuristics" have been considered. Our substring heuristics are much stronger and refer to larger parts of texts (not only to single positions). We use ¤ -versions of suffix tries and subword

Introduction

This paper focuses on a set of string pattern-matching problems that arise in musical analysis, and especially in musical information retrieval. A musical score can be viewed as a string: at a very rudimentary level, the alphabet could simply be the set of notes in the chromatic or diatonic notation, or the set of intervals that appear between notes (e.g. pitch may be represented as MIDI numbers and pitch intervals as number of semitones). Approximate repetitions in one or more musical works play a crucial role in discovering similarities between different musical entities and may be used for establishing "characteristic signatures" (see [START_REF] Crawford | String Matching Techniques for Musical Similarity and Melodic Recognition[END_REF]). Such algorithms can be particularly useful for melody identifi cation and musical retrieval.

The approximate repetition problem has been extensively studied over the last few years. Effi cient algorithms for computing the approximate repetitions are directly applicable to molecular biology (see [START_REF] Fischetti | Identifying periodic occurrences of a template with applications to protein structure[END_REF][START_REF] Karlin | Efficient algorithms for molecular sequences analysis[END_REF][START_REF] Milosavljevic | Discovering simple DNA sequences by the algorithmic significance method[END_REF]) and in particular in DNA sequencing by hybridization ( [START_REF] Pevzner | Gray Code Masks for DNA Sequencing by Hybridization[END_REF]), reconstruction of DNA sequences from known DNA fragments (see [START_REF] Schmidt | All shortest paths in weighted grid graphs and its application to finding all approximate repeats in strings[END_REF][START_REF] Skiena | Reconstructing strings from substrings[END_REF]), in human organ and bone marrow transplantation as well as the determination of evolutionary trees among distinct species ( [START_REF] Schmidt | All shortest paths in weighted grid graphs and its application to finding all approximate repeats in strings[END_REF]).

The approximate matching problem has been used for a variety of musical applications (see overviews in McGettrick [START_REF] Mcgettrick | MIDIMatch: Musical Pattern Matching in Real Time[END_REF]; Crawford et al [START_REF] Crawford | String Matching Techniques for Musical Similarity and Melodic Recognition[END_REF]; Rolland et al [START_REF] Rolland | Musical Pattern Extraction and Similarity Assessment, Readings in Music and Artifi cial Intelligence[END_REF]; Cambouropoulos et al [START_REF] Cambouropoulos | Pattern Processing in Melodic Sequences: Challenges, Caveats and Prospects[END_REF]). It is known that exact matching cannot be used to fi nd occurrences of a particular melody. Approximate matching should be used in order to allow the presence of errors. The number of errors allowed will be referred to as ¡ . This paper focuses in one special type of approximation that arise especially in musical information retrieval, i.e. ¡ -approximation. Most computer-aided musical applications adopt an absolute numeric pitch representation (most commonly MIDI pitch and pitch intervals in semitones; duration is also encoded in a numeric form). The absolute pitch encoding, however, may be insuffi cient for applications in tonal music as it disregards tonal qualities of pitches and pitch-intervals (e.g. a tonal transposition from a major to a minor key results in a different encoding of the musical passage and thus exact matching cannot detect the similarity between the two passages). One way to account for similarity between closely related but non-identical musical strings is to use what will be referred to as ¡ -approximate matching (and ¢ -approximate matching). In ¡ -approximate matching, equal-length patterns consisting of integers match if each corresponding integer differs by not more than ¡ -e.g. a C-major £ ¥¤ §¦ ©¤ ¤ ¤ and a C-minor £ ¥¤ §¦ ©¤ ! ¤ ¤ sequence can be matched if a tolerance ¡ #" %$ is allowed in the matching process (¢ -approximate matching is described in the next section).

In [START_REF] Cambouropoulos | Algorithms for computing approximate repetitions in musical sequences[END_REF], a number of effi cient algorithms for ¡ -approximate matching, using "occurrence heuristics" was presented (i.e. the SHIFT-AND algorithm and SHIFT-PLUS algorithm). The SHIFT-AND algorithm is based on the & (' )$ 10 -time computation of different states for each symbol in the text. Hence the overall complexity is & (' 32 40 . These algorithms use the bitwise technique [START_REF] Baeza-Yates | A new approach to text searching[END_REF][START_REF] Wu | Fast text searching allowing errors[END_REF]. It is possible to adapt fast and practical exact string matching algorithms to these kind of approximations. In this paper we will present the adaptations of the TUNED-BOYER-MOORE [START_REF] Hume | Fast string searching[END_REF], the SKIP-SEARCH algorithm [START_REF] Charras | A very fast string matching algorithm for small alphabets and long patterns[END_REF] and the MAXIMAL-SHIFT algorithm [START_REF] Sunday | A very fast substring search algorithm[END_REF] and present some experiments to assert that these adaptations are faster than the algorithms using the bitwise technique.

Then we present three new algorithms, using "substring heuristics": ¡ -BM1, ¡ -BM2 and ¡ -BM3. They can be thought as members of the Boyer-Moore family of algorithms. The two fi rst algorithms implement a heuristic based on a suitable generalization of the suffi x trees data structure. The third algorithm uses a heuristic that considers fi ngerprints for selected substrings of the pattern and compares them with corresponding fi ngerprints of substrings of the text to be processed. The algorithms are fast on average. We provide experimental results and observations on the suitability of the heuristics. Our algorithms are particularly effi cient for "non-flat" patterns over large alphabet intervals, and many patterns are of this kind.

The paper is organized as follows. In the next section we present some basic defi nitions for strings and background notions for approximate matching. In section 3 we present the adaptation of TUNED-BOYER-MOORE, SKIP-SEARCH and MAXIMAL-SHIFT to ¡ -and (¡ 1)¢ )-approximate string matching algorithms. In section 4 we present the data structures for our "substring heuristics", the three algorithms which use them and an average case analysis for two of them. In section 5 we present experimental results for all these algorithms. Finally in section 6 we present our conclusions.

Background and basic string definitions

A string is a sequence of zero or more symbols from an alphabet ; the string with zero symbols is denoted by ¡ . The set of all strings over the alphabet is denoted by

£¢ . A string ¤ of length ¥ is represented by ¤ §¦ $ ©¥ , where ¤ ¦ for $ ! " # $¥ . A string % is a substring of ¤ if ¤ " '& (% 0) for & 1)
% in ¤ . A string % is a prefix of ¤ if ¤ " @% A& for & 2 B ¢ . Similarly, % is a suffix of ¤ if ¤ " @& (% for & B B ¢ .
The string ¤ (C is a concatenation of two strings ¤ and C . The concatenations of D copies of ¤ is denoted by ¤ FE .

Let ¤ be a string of length ¥ . The integer G is said to be a period of ¤ , if ¤ §¦ " H¤ §¦ 6 IG P for all $ Q R S T¥ VU WG . The period of a string ¤ is the smallest period of ¤ . A string C is a border of ¤ if C is a prefi x and a suffi x of ¤ .

Let be an alphabet of integers and ¡ an integer. Two symbols X ¨Y of are said to be ¡ -approximate, denoted X Ra" "Y if and only if

Occurrence heuristics

The problem of ¡ -approximate pattern matching is formally defi ned as follows: given a string C " uC ¦ $ ©¨2 and a pattern ¤ " @¤ §¦ $ ©¥ compute all positions of C such that ¤ "a" uC ¦ x¨ #6 ¥ HU $ xÄ naive solution to this problem is to build an Aho-Corasick automaton (see [START_REF] Aho | Efficient string matching: an aid to bibliographic search[END_REF]) of all strings that are ¡ -approximate to ¤ and then use the automaton to process C . The time required to build the automaton is & (' ¡ ¢¡ 0 since there are s ¤£ ¡ S6 $ different letters that can be used in each position, thus this method is of no practical use for large values of ¡ and ¥ . In [START_REF] Cambouropoulos | Algorithms for computing approximate repetitions in musical sequences[END_REF] an effi cient algorithm was presented based on the & (' )$ 10 -time computation of the "delta states" by using bit operations under the assumption that ¥ % , where % is the number of bits in a machine word. In this section we present direct adaptations of exact string matching algorithms to the notion of ¡ -approximate string matching. The new algorithms use only heuristics on single positions of the pattern. Section 3.1 presents the adaptation of the TUNED-BOYER-MOORE exact string matching algorithm. Section 3.2 depicts the adaptation of the SKIP-SEARCH exact string matching algorithm. Section 3.3 presents the adaptation of the MAXIMAL-SHIFT exact string matching algorithm. Section 3.4 shows the adaptation of these algorithms to (¡ 1)¢ )-approximate string matching.

¥ -TUNED-BOYER-MOORE Approximate Pattern Matching

Here we present an adaptation of the TUNED-BOYER-MOORE for exact pattern matching algorithm to ¡ -approximate pattern matching. The exact pattern matching problem consists in fi nding one or more (generally all) exact occurrences of a pattern ¤ of length ¥ in a text C of length 2 . Basically a pattern matching algorithm uses a window which size is equal to the length of the pattern. It fi rst aligns the left ends of the window and the text. Then it checks if the pattern occurs in the window and shifts the window to the right. It repeats the same procedure again until the right end of the window goes beyond the right end of the text.

The TUNED-BOYER-MOORE algorithm [START_REF] Hume | Fast string searching[END_REF] is a very fast practical variant of the famous BOYER-MOORE algorithm [START_REF] Boyer | A fast string searching algorithm[END_REF]. It only uses the occurrence shift function to perform the shifts. The occurrence shift function is defi ned for each symbol X in the alphabet as follows: shift ¦ X " §¦ © £ £ 8¥ U 4 ¤ §¦ " uX with $ ¥ £ 8¥ rT he TUNED-BOYER-MOORE algorithm gains its effi ciency by unrolling three shifts in a very fast skip loop to locate the occurrences of the rightmost symbol of the pattern in the text. Once an occurrence of ¤ ¦ ¥ is found, it checks naively if the whole pattern occurs in the text. Then the shift consists in aligning the rightmost symbol of the window with the rightmost reoccurrence of ¤ ¦ ¥ in ¤ §¦ $ ©¥ U $ , if any. The length of this shift is defi ned as follows:

" ¦ © £ £ 8¥ U 4 ¤ §¦ " @¤ §¦ ¥ and ¦ © ¥ £ 8¥ rT o do ¡ -approximate pattern matching, the shift function can be defi ned to be for each symbol X in the alphabet the distance from the right end of the pattern of the closest symbol ¤ ¦ such that ¤ §¦ a" uX : Then the length of the shift becomes:

shift ¦ X " §¦ © £ £ 8¥ U 4 ¤ §¦ a" $X with $ ¥ £ 8¥ r¨ ¡ -TUNED-BOYER-MOORE ' ¤ 4¨¥ 1C ¨2 ¡ 0 1 Preprocessing 2 for all X B 3 do shift ¦ X x ¢¡ ¦ © £ £ 8¥ U 4 ¤ §¦ a" $X £ 8¥ 4 £¡ ¦ © £ £ 8¥ U S4 7¤ §¦ ¤ a" @¤ §¦ ¥ and ¦ ¥ £ 8¥ 5 C h¦ 2 !6 $ ©¨2 6 I¥ ¥¡ ' ¤ ¦ ¥ 30 ¡ 6 Searching 7 ¦¡ ¥ 8 while 2 9 do D §¡ shift ¦ C h¦ © 10 while D ¨" ¦ 11 do ©¡ 06 D 12 D §¡ shift ¦ C ¦ c 13 ©¡ 6 D 14 D §¡ shift ¦ C ¦ c 15 ©¡ 6 D 16 D §¡ shift ¦ C ¦ c 17 if ¤ §¦ $ ©¥ U $ a" uC ¦ QU ¥ 6 $ ©¨ U $ and
" ¦ £ £ 8¥ HU 4 7¤ ¦ ¤ a" R¤ ¦ ¥ and ¦ © ¥ £ 8¥ rT
he reason why it is necessary to use s ¡ in the new defi nition of is that s ¡ is the minimum such that for any three symbols

X ¨Y ¥#" B , if X ua" $Y and Y Ba" $" then X ¤ a" %" .
The pseudo-code for ¡ -TUNED-BOYER-MOORE algorithm can be found in fi gure 1.

¥ -SKIP-SEARCH Approximate Pattern Matching

In the SKIP-SEARCH algorithm [START_REF] Charras | A very fast string matching algorithm for small alphabets and long patterns[END_REF], for each symbol of the alphabet, a bucket collects all of that symbol's positions in ¤ . When a symbol occurs D times in the pattern, there are D corresponding positions in the symbol's bucket. When the word is much shorter than the alphabet, many buckets are empty. The buckets are stored in a table defi ned as follows:

¡ -SKIP-SEARCH ' ¤ 1¥ 1C ¨2 ¡ 0 1 Preprocessing 2 for all X B 3 do (¦ X ¢¡ £ 8 S4 ¤ §¦ a" uX 4
(¦ X x " £ 8 4 ¤ ¦ " uX with $ £ ¥ rT he main loop of the search phase consists in examining every ¥ -th text symbol, C ¦ c (so there will be 2 ¢ ¥ main iterations). Then for C h¦ © , it uses each position in the bucket (¦ C ¦ c to obtain a possible starting position of ¤ in C and checks if the pattern occurs at that position.

To do ¡ -approximate pattern matching, the buckets can be computed as follows:

(¦ X x " £ 8 4 ¤ ¦ a" uX with $ £ ¥ rF igure 2 shows the pseudo-code for ¡ -SKIP-SEARCH algorithm. In this case when ¥ is much shorter than the alphabet and the pattern ¤ is flat (i.e. its structure does not vary substantially), many buckets are empty.

¥ -MAXIMAL-SHIFT Approximate Pattern Matching

Sunday [START_REF] Sunday | A very fast substring search algorithm[END_REF] designed an exact string matching algorithm where the pattern positions are scanned from the one which will lead to a larger shift to the one which will lead to a shorter shift, in case of a mismatch. Doing so one may hope to maximize the lengths of the shifts and thus to minimize the overall number of comparisons.

Formally we defi ne a permutation £ ¥¤ £ $ §¨s qqq¥1¥ 1¥ 6 $ §¦ £ $ §¨s qqq1¥ 1¥ 6 $ and a function shift such that shift ¦ £ ' 0 ¡ shift ¦ £ ' 6 $ 10

for $ ¥ and shift ¦ £ ' 0 " ¦ © £ £¢ 4 ' i such that $ £ 1¤ §¦ £ ' 0 U ¤¢ " @¤ §¦ £ ' 0 30 and ' ¤ ¦ £ ' 0 5U ¤¢ "@¤ ¦ £ ' 0 30

for $ b @ @¥ and £ ' ¥ 6 $ 10 " ¥ 6 $ . Furthermore shift ¦ ¥ 6 $ is set with the value of the period of the pattern ¤ .

We also defi ne a function ¥ §¦ for each symbol of the alphabet:

¥ ¨¦ ¦ X " © ¦ © £ 4 ¦ ! ¥ and ¤ §¦ ¥ VU © " $X if X occurs in ¤ ¥ otherwise for X B .
Then, when the pattern is aligned with the C h¦ c¨ !6 @¥ U $ the comparisons are performed in the following order ¤ §¦ £ ' )$ 10 1¤ ¦ £ ' s 0 qqq1¤ §¦ £ ' ¥ 0 until the whole pattern is scanned or a mismatch is found.

If a mismatch is found when comparing ¤ §¦ £ ' 0 then a shift of length ¦ £ shift ¦ £ ' 0 ¥ ¨¦ ¦ C h¦ 6 ¥ 6 $ is performed. Otherwise an occurrence of the pattern is found and the length of the shift is equal to the maximum value between the period of the pattern and ¥ §¦ ¦ C h¦ £6 ¥ 6 $ . Then the comparisons resume with ¤ ¦ £ ' )$ 10 without keeping any memory of the comparisons previously done.

To perform ¡ -approximate string matching the two functions can be redefi ned as follows:

shift ¦ £ ' 0 " ¦ © £ £¢ 4 ' i such that $ £ 1¤ §¦ £ ' 0 U ¤¢ ¤ a" @¤ ¦ £ ' 0 30 and ' ¤ §¦ £ ' 0 rU ¤¢ a "@¤ §¦ £ ' )0 30
for $ ¥ and shift ¦ ¥ 6 $ " ¦ £ £¢ 4 ©¤ §¦ a" @¤ ¦ F6 ¢ for $ £ e ¥ HU ¢ ¥ and ¥ ¨¦ ¦ X x " © ¦ ©¨ £ 4 §¦ 9 ¥ and ¤ ¦ ¥ HU © a" uX if such a exists¥ otherwise for X B . The preprocessing phase can be done in & (' ¥ ¤ 0 . Figure 3 gives the pseudo-code of the searching phase.

¥ ! ¡" -Approximate String Matching Algorithms

The problem of ' ¡ )¢ 0 -approximate pattern matching is formally defi ned as follows: given a string C " C ¦ $ ©¨2 and a pattern ¤ " @¤ §¦ $ ©¥ compute all positions of C such that ¤ a p t" C h¦ c¨ £6 I¥ HU $ xÏ n [START_REF] Cambouropoulos | Algorithms for computing approximate repetitions in musical sequences[END_REF] this problem was solved by making use of the SHIFT-AND algorithm to fi nd the ¡ -approximate matches of the pattern ¤ in C . Once a ¡ -approximate match was found, it was then tested to check

¡ -MAXIMAL-SHIFT ' ¤ 1¥ ¨C ¨2 ¡ ¥¨shift ¥ ¨¦ §0 1 Searching 2 ¡ ¦ 3 while 2 U ¥ 4 do ¡ $
5 while e ¥ and ¤ §¦ £ ' 0 " @C h¦ 6 £ ' 0 whether it is also a ¢ -approximate match. This was done by computing successive "delta states" and "gamma states" in & (' )$ 10 time using bit operations under the assumption that ¥ % where % is the number of bits in a machine word.

6 do ¡ 6 $ 7 if ¡ ¥ 8 then REPORT ' 0 9 ©¡ 6 ¦ £ shift ¦ £ ' 0 ¥ ¨¦ ¦ C h¦ 6 I¥ 6 $
In order to adapt the ¡ -TUNED-BOYER-MOORE, ¡ -SKIP-SEARCH and ¡ -MAXIMAL-SHIFT algorithms to the case of ' ¡ 1)¢ 0 -approximation, it just suffi ces to adapt the naive check of the pattern. The resulting algorithms are named ' ¡ )¢ 0 -TUNED-BOYER-MOORE algorithm, ' ¡ 1)¢ 0 -SKIP-SEARCH algorithm and ' ¡ 1)¢ 0 -MAXIMAL-SHIFT algorithm.

Substring heuristics

In this section we introduce "substring heuristics" to solve the problem of ¡ -and (¡ 1)¢ )-approximate string matching. It is the fi rst time that such heuristics are considered for this kind of problems. Section 4.1 defi nes two notions of approximate dictionaries which corresponding data structures are given in sections 4.2 and 4.3. In section 4.4 we give three new algorithms using these approximate dictionaries and we give an average case analysis for two of them in section 4.5.

Two approximate dictionaries

The Boyer-Moore type algorithms are very effi cient on average since scanning a small segment of size D allows, on average, to make large shifts of the pattern. Eventually this gives sublinear average time complexity. This general idea has many different implementations, see [START_REF] Crochemore | Speeding-up two string matching algorithms[END_REF]. In this section, our approach to ¡ -matching is similar, we scan a segment of size D in the text. If this segment is not ¡ -approximate with any subword of the pattern we know that no occurrence of the pattern starts at ¥ U ID positions to the left of the scanned segment. This allows to make a large shift of size ¥ HU D . The choice of D affects the complexity. In practice small D would suffi ce. Hence the fi rst issue, with this approach, is to have a data structure which allows to check fast if a word of size D is ¡ -approximate to a subword of ¤ . We are especially interested in the answer "no" which allows to make a large shift, so an important parameter is the rejection ratio, denote by Exact-RR. It is the probability that a randomly chosen D -subword is not ¡ -approximate with a subword of ¤ . If this ratio is high then our algorithms would work much faster on average. However another parameter is the time to check if the answer is "no". It should be proportional to D . We do a compromise: build a data structure with smaller rejection ratio but with faster queries about subwords of size D . Smaller rejection ratio means that sometimes we have answer "yes" though it should be "no", however if the real answer is "no" then our data structure always outputs "no" also. This is the negative answer which speeds up Boyer-Moore type algorithms. The positive answer has small effect. The data structure is an approximate one, its rejection ratio is denoted by RR, and it is hard to analyze it exactly. Hence we rather deal with heuristics. The performance depends on particular structure, the parameter D and class of patterns. Another important factors are rejection ratios: Exact-RR and RR. If Exact-RR is too small we cannot expect the algorithms to be very fast. On the other hand we need to have RR as close to Exact-RR as possible. The applicability is verifi ed in practice. The starting structure is the suffi x trie, it is effective in searching but it could be too large theoretically, though in practice D is small and D -truncated suffi x trie is also small. Surprisingly we do not have linear size equivalent of (compact) suffi x trees, but we have a linear size equivalent of subword graphs: ¡ -subword graphs. this shows that suffi x trees and subword graphs are very different in the context of ¡ -matching. Below we give a formal defi nition of our data structures and rejection ratios. Denote by SUB' ¤ 4¨D 0 the set of all substrings of ¤ of size D . Denote also:

¡ -SUB' ¤ ¨D 0 " £ 4 a
" R% for some % ' SUB' ¤ ¨D 0 rT his is similar to the computation of high-scoring words in BLAST [START_REF] Altschul | Basic local alignment search tool[END_REF].

An approximate dictionary for a given string ¤ is the data structure w a p E which answers the queries: we denote the corresponding data structure for the queries involving the equality a p t " % . In order for our data structure to work fast we allow that the answers could be incorrect. w a p E ' 0 can answer true although is not in ¡ -SUB' ¤ 4¨D 0 . By an effi ciency of w a p E we understand the rejection-ratio proportion:

RR E ' £ w a p E 0 " 4 £ B E 4 ¤ w a p E ' 0 " ¦¥ ¨ § © ¨ d4 4 4 E

Öptimal

effi ciency is the exact rejection-ratio for ¤ :

Exact-RR E ' ¤ 0 " $ U 4 ¡ -SUB' ¤ 4¨D 0 q4 4 4 E
Ïn other words the effi ciency RR E is the probability that a random substring of length D is not accepted by w a p E and the effi ciency Exact-RR E is the probability that a random substring of length D is not an element of ¡ -SUB' ¤ 4¨D 0 . Our data structures are partially correct:

¡ -SUB' ¤ ¨D 0 £ 4 ¤ w a p E ' 0 " ! " r¨

¥ -suffix tries and ¥ -subword graphs

Denote ¡ ¡ " ¦ £ 8 U ¡ ¨¦ £ and £¢ ¡ " ¦ ©¨ £ 8 g6 ¡ 1¨¦ £ . We defi ne ¡ -suffi x tries and ¡ -subword graphs algorithmically. The ¡ -suffi x trie of a pattern ¤ is built as follows: ¤ build the trie ¥ " ' §¦ ©¨0 recognizing all the suffi xes of ¤ where ¦ is the set of nodes and ¨ ¦ £ B §£ ¦ is the set of edges of ¥ ;

¤ replace each edge ' G ¨X © 0 ¨by ' G ¨¦ ¦ £ 1¦ ©¨X 9U ¡ ¨¦ © £ ¢¦ £ ¨X 6 ¡ q © 0 ;

¤ for all the nodes ) T ¦ , if there are two edges ' ) ¨¦ X ¨Y ¨G 0 1' ) ¨¦ " © c © 0 ¨such that ¦ X ¨Y ` ¡ ¦ " © x ¨" then merge G and into a single new node and replace ' ) ¨¦ X ¨Y ` ¨G 0 and ' ) ¨¦ " © c © 0 by one edge ' ) ¨¦ ¦ © £ X #" ¥ ¨¦ £ 7Y ¥© q ¨ §0 .

We have an equivalence relation on the set of vertices: two vertices are equivalent iff they are roots of isomorphic subtrees. In the ¡ -suffi x trie construction we process nodes by taking at each large step all vertices which are in a same equivalence class . Then in this step we process all edges outgoing from vertices from . All these vertices are independent and we can think that it is done in parallel. The construction terminates when the trie stabilizes. The ¡ -subword graph of a sequence ¤ is obtained by minimizing its ¡ -suffi x trie. This means that each equivalence class of vertices is merged into a single vertex. Figure 5 shows an example of ¡ -suffi x trie and ¡ -subword graph. It should be noted that using an alphabet of ranges is not a new idea (see [START_REF] Fredkin | Trie memory[END_REF]).

Proof:

The number of equivalence classes of the initial suffi x trie is at most s 2 . In the process of merging edges the nodes which are equivalent initially will remain equivalent until the end. Hence the number of equivalence classes of intermediate ¡ -suffi x trie (after processing all edges outgoing from nodes in a same equivalence class) is at most s 2 , which gives the upper bound on the number of nodes of the ¡ -subword graph. The bound on the number of edges can be shown similarly as for standard subword graphs.

Families of intervals

For each subword % SUB' ¤ 4¨D 0 of ¤ , denote by ! § ¤ "! 4' % 0 the sum of the symbols of C . For each D 4 ¤ 54

we introduce the following families of intervals (overlapping and adjacent intervals are "glued together") of the interval ¦ ¦ © £ rD £ ¦ £ q which represents respectively the sets: (a) If a" @% for some % SUB' ¤ 4¨D 0 then ! § ¤ "! 4' 0 # a ' ¤ 4¨D 0 ;

# a ' ¤ ¨D 0 " $ % '& SUB( w E 0) ¦ 1! § ¤ "! 4' % 0 2 D ¡ 13! § ¤ "! 4' % 0 2¢ D ¡ 8 and 4 t ' ¤ 4¨D 0 " $ % 5& SUB( w E 6) ¦ 1! § ¤ 7! ' % 0 ' ¦ © £ 7D ¡ )¢ 4 8! § ¤ 7! ' % 0 '¢ ¦ © £ 7D ¡ )¢ 4 q xC learly 4 E a ' ¤ 4¨D 0 " # a ' ¤ ¨D 0 .
(b) If a p t" % for some % SUB' ¤ ¨D 0 then ! § ¤ "! 4' 0 S 4 t ' ¤ 4¨D 0 . The effi ciency of the family of intervals can be measured as RR' ¡ 0 " $ U £¢ ¥¤ ¥ ' ! § ¤ "! 4' 0 ¦ 0 where is a random string of length D . In other words it is the probability that an integer is not in any interval of the family. Observe that in our case is always represented as a family of disjoint intervals, overlapping and adjacent ones have been glued together.

Three ¥ -BM algorithms

We show how the data structures introduced in this section are used in ¡ -matching. We now want to fi nd all the ¡ -occurrences of a pattern ¤ of length ¥ in a text C of length 2 . We apply a very simple greedy strategy: place the pattern over the text such that the right end of the pattern is over position in the text. Then check if the suffi x ¥ of length D (D may depend on ¤ ) of text ending at is "sensible". If not the pattern is shifted by a large amount and many positions of of the text are never inspected at all. If ! ¥ is sensible then a naive search in a "window" on the text is performed. Figure 7 implements this method.

We denote here by NAIVE ' G © 0 a procedure checking directly if ¤ ends at positions in the interval ¦ G ¨ 7 , for G .

We design an improved version of ¡ -BM1 using ¡ -subword graphs instead of tries. The ¡ -subword graph of the reverse pattern is denoted by ' 7¦ 1) ¨ § §© ©¨0 , where is the alphabet, ¦ is the set of states, ) § ¦ is the initial state, © ¦ is the set of fi nal states and ¨ ¦ £ £ ¦ is the set of transitions. Let ¡ -' ¤ 0 be the ¡ -period of the word ¤ defi ned by ¡ -¨ ' ¤ 0 " ¦ ©¨ £ 1G 4 i $ £ e ¥ U G 1¤ §¦ a" u¤ §¦ 6 AG P .

Then it is possible to adopt the same strategy as the Reverse Factor algorithm [START_REF] Crochemore | Speeding-up two string matching algorithms[END_REF] for exact string matching to ¡ -approximate string matching. When the pattern ¤ is compared with C h¦ rU ¥ 6 $ © the symbols of C ¦ xU b¥ T6 $ © are parsed through the ¡ -subword graph of the reverse pattern from right to left starting with the initial state. If transitions are defi ned for every symbol of C h¦ U ¥ 6 $ © , it means that a ¡ -occurrence of the pattern could have been found and the pattern can be shifted by ¡ -¨ ' ¤ 0 positions to the right. Otherwise the pattern can be shifted by ¥ minus the length of the path, in the ¡ -subword graph, from the initial state and the last fi nal state encountered while scanning C h¦ U ¥ '6 $ © from right to left. Indeed the ¡ -subword graph of the reverse pattern recognizes at least all the ¡ -suffi xes of the

¡ -BM2 ' ¤ 41¥ 1C ¨2 ¡ §0 1 ¡ ¥ 2 while e 2 3 do ¡ ) § 4 ¡ 5 Y ¡ ¦ 6 while ' 1C h¦ © ¨G 0 A 7 do ¡ VG 8 ©¡ QU $ 9 if b © 10 then Y ¡ U 11 if U ¥ 12
then check and report a ¡ -occurrence at position §U ¥ 6 $ 13

¡ F6 ¡ -¨ ' ¤ 0 14 else ¡ F6 I¥ HU 3Y Figure 8. ¤ -BM2 algorithm.
reverse pattern from right to left and thus at least all the ¡ -prefi xes of the pattern from left to right. Figure 8 implements this method.

The value ¡ -' ¤ 0 can be approximated using the ¡ -subword graph of the reverse pattern.

Our last algorithm can be used also for ' ¡ )¢ 0 -approximate string matching. We apply the data structure of interval families. Figure 9 implements this method. ¡ -BM3 algorithm is conceptually simpler than the other algorithms and its preprocessing is easy.

Average time analysis of algorithms ¥ -BM1 and ¥ -BM3

Denote G " ¡ £¢ ¥¤ Y §' ¤ a" @C 0 where ¤ and C are random symbols and E w " RR E ' £ w a p E 0 .

Lemma 4.2. The overall average number of comparisons made by ¡ -BM1 and ¡ -BM3 algorithms is at most

2 ¥ HU 3D ¦ D Q6 ' )$ U E w 0 ¥ $ U G ¨ § Proof:
Divide the text into windows of size ¥ HU 3D . In each window the probability that the pattern is moved to the next window after at most D comparisons is E w . Now it is enough to prove that the average number of comparisons made by the naive algorithm in the window is bounded by ¡ © . We assume now that our algorithm performs worse than in reality and no matter what is the result of comparisons of symbols at positions ¥ "U D r6 $ ©¥ of the window the algorithm goes further and ends when one of the other window

The analysis of our algorithms would be simpler and we would get slightly better estimation for the average number of symbol comparisons if we assume that in each window the naive algorithm performs comparisons of text symbols at positions ¥ U $D 6 $ ©¥ at the end. The estimation is however not signifi cantly better. In particular it does not give an improvement in the estimation in our next theorem. here that our analysis does not depend on the data structure . The only thing it assumes is that the scheme of the algorithm matches the structure of the algorithms ¡ -BM1 and ¡ -BM3. Clearly, the effi ciency of such algorithms depends heavily on the choice of D and the effi ciency of . For instance, for ¡ " ¦ , (ie. we consider string matching without errors) we may choose D " s ¤£ ¦¥ ¢ § v ḧv ¥ . Then, for ¡ -BM1, $ U E w is the probability that a random string of length D is not a subword of ¤ . The number of subwords of length D of ¤ is at most ¥ and the number of all words of length D is ¥ ¤ so $ 0U E w ¡ thus the average time complexity is & (' © ¡ £ ¦¥ ¢ § ¥ 0 , the best possible. Moreover D may depend also on the pattern ¤ itself. If G is "good" then D may be chosen small and when it is "bad" D may be chosen bigger.

In particular we may increase D up to the moment when $ U E w decreases below an acceptable level.

Experimental Results

We fi rst count the number of text character inspections of the algorithms in section 5.1 while we observe their running times in section 5.2.

Text character inspections

We computed experimentally the values RR and Exact-RR for our approximate dictionaries for various values of D and different sizes of the alphabet. These effi ciencies correspond to average case complexity of our ¡ -BM algorithms. We compared the values of RR and Exact-RR with average running time for suffi ciently large sample of random inputs. We counted the average number of text character inspections for the following algorithms: ¡ -TUNED-BOYER-MOORE, ¡ -SKIP-SEARCH, ¡ -MAXIMAL-SHIFT [START_REF] Crochemore | Approximate string matching in musical sequences[END_REF] and ¡ -BM1, ¡ -BM2 and ¡ -BM3.

All the algorithms have been implemented in C in a homogeneous way such as to keep their comparison signifi cant. The text used is composed of §¦ ¦ ©¨¦ ¦ ¦ symbols and was randomly built. The size of the alphabet is 100. The target machine is a PC, with a AMD-K6 II processor at 330MHz running Linux kernel 2.2. The compiler is . For each pattern length ¥ , we searched per one hundred patterns randomly built.

We counted the number " of text character inspections for one text character. The results are presented in fi gures 10 and 11. For ¡ " $ the best results for ¡ -BM1 algorithm have been obtained with D " £ ¦¥ ¢ § ¤ ¥ . The best results for the ¡ -BM3 algorithm have always been obtained with D " s . For small values of ¡ , ¡ -BM1 and ¡ -BM2 algorithms are better than ¡ -TUNED-BOYER-MOORE algorithm (which is the best among the known algorithms) for large values of ¥ (¥ Rs §¦ ). For large values of ¥ , ¡ -BM1 and ¡ -BM2 algorithms are performing a large number of text character inspections since the ¡ -subword graph and the ¡ -suffi x trie tend to be a line with all edges labeled with ¦ ¦ © £ x¨¦ £ q . For larger values of ¡ (up to 5) ¡ -BM1 and ¡ -BM2 algorithms are better than ¡ -TUNED-BOYER-MOORE algorithm for small values of ¥ (¥ $ 8s ). For larger values of ¡ , the ¡ -TUNED-BOYER-MOORE algorithm is performing better than the other algorithms. In conclusion the algorithms introduced in this article are of particular practical interest for large alphabets, short patterns and small values of ¡ . Alphabets used for music representations are typically very large. A "bare" absolute pitch representation can be base-7 (7 symbols), base-12, base-40 or 120 symbols for MIDI. But meaningful alphabets that will allow us to do in-depth music analysis use symbols that in reality is a set of parameters. A typical symbol could be ' X ¨X ¤ ¨X ! qqq1¨X E 0 , where X represents the pitch, X ¤ represents the duration, X " the accent etc. A typical pattern ("motif") in musical sequence is 15-20 notes but an alphabet can have thousands of symbols. Thus the need of algorithms that perform well for small patterns and large alphabets.

Running times

We implemented in C, in a homogeneous way, the following algorithms:

SHIFT-AND, ¡ -TUNED-BOYER-MOORE, ¡ -SKIP-SEARCH, ¡ -MAXIMAL-SHIFT and SHIFT-PLUS, ' ¡ 1)¢ 0 -TUNED-BOYER-MOORE, ' ¡ 1)¢ 0 -SKIP-SEARCH and ' ¡ )¢ 0 -MAXIMAL-SHIFT. We randomly built a text of §¦ ¦ ©¨¦ ¦ ¦ symbols on an alphabet of size ¦ . We then searched for each values of ¥ , 100 random patterns and took the average running time. Times are measured in hundredth of seconds and include both preprocessing and searching times. The design of effi cient algorithms for the preprocessing phase of the algorithms using "substring heuristics" is still an open problem, they are not included in the running time experimentation.

The results for ¡ -approximation are shown in tables 1 to 5. For the values used in these experiments, the ¡ -TUNED-BOYER-MOORE algorithm is always faster than the ¡ -SKIP-SEARCH algorithm which is itself always faster than the SHIFT-AND algorithm. The results for ' ¡ 1)¢ 0 -approximation are shown in tables 6 to 10. For the values that were used in these experiments, the ' ¡ 1)¢ 0 -TUNED-BOYER-MOORE algorithm is always faster than the ' ¡ 1)¢ 0 -SKIP-SEARCH algorithm which is itself always faster than the SHIFT-PLUS algorithm.

Experiments conduct only on ¢ -approximation show that an adaptation to this case of the SKIP-SEARCH algorithm is faster than an adaptation of the TUNED-BOYER-MOORE algorithm.

One should notice that the SHIFT-AND and SHIFT-PLUS algorithms need constant time to run whatever the values of the parameters are. In case of very high values for ¡ and/or ¢ they have to be considered as the best choice.

Conclusion

We presented in this article two types of heuristics for ¡ -and ¢ -string matching problems. We fi rst consider "occurrence heuristics" for which we designed the SKIP-SEARCH, TUNED-BOYER-MOORE and MAXIMAL-SHIFT approximate string matching algorithms that outperform, in practice, the one presented in [START_REF] Cambouropoulos | Algorithms for computing approximate repetitions in musical sequences[END_REF]. Then we consider "substring heuristics". Using ¡ -tries, ¡ -subword graphs and families of intervals we gave three new algorithms that can be considered as members of the Boyer-Moore family of pattern matching algorithms. The algorithms using "occurrence heuristics" are very fast in practice. A theoretical study of the algorithms using "substring heuristics" shows that they are optimal in the average. An experimental study shows that for small values of ¡ (1 or 2) the ¡ -BM algorithms are effi cient. For mid values of ¡ the TUNED-BOYER-MOORE algorithm is the fastest algorithm. In case of very high values for ¡ and/or ¢ the SHIFT-AND and SHIFT-PLUS algorithms have to be considered as the best choice.

A problem remains in designing effi cient algorithms for building ¡ -tries and ¡ -subword graphs.

2 3 ¢

 3 ; we equivalently say that the string % occurs at position 4 & 54 76 $ of the string ¤ . The position 4 & 4 86 $ is said to be the starting position of % in ¤ and the position 4 & 4 86 "4 % 94 the end position of

2 18then 19 ©¡ # 6 Figure 1 .

 21961 Figure1. Adaptation of the TUNED-BOYER-MOORE exact pattern matching algorithm to do ¤ -approximate pattern matching. Line 3, copies of ¥ ¦ are appended at the end of . Line 5, shift is set to so that during the inner loop (lines 10-16) of the searching phase whenever becomes greater than , ! becomes equal to .

10 ¡ # 6 I¥Figure 2 .

 1062 Figure 2. Adaptation of the SKIP-SEARCH exact pattern matching algorithm to do ¤ -approximate pattern matching.

Figure 3 .

 3 Figure 3. Adaptation of the MAXIMAL-SHIFT exact pattern matching algorithm to do ¤ -approximate pattern matching.

  the result (true or false) of such query for a string given by the data structure w

Theorem 4 . 1 .

 41 The numbers of nodes and of edges of ¡ -subword graph for the string ¤ are & (' 4 ¤ 4 0 .

Figure 6

 6

Figure 4 .Figure 5 .Figure 6 .¥ 2 while e 2 3 4 then

 45624 Figure 4. The suffix tree and subword graph for the word ¢¡ £ ¥¤ §¦ ¨£ © ¤ §¦ © ¤ and ¡

Figure 7 .Lemma 4 . 1 .

 741 Figure 7. ¤ -BM1 algorithm.

Theorem 4 . 2 .

 42 Let D T ¦ ¡ ¢ ¥ and G $ ¦ ¡ ¢ . The average time complexity of the algorithms ¡ -BM1 and ¡ -BM3 is &

Figure 10 .

 10 Figure 10. Results for ¤ 8¡ £ .

Figure 11 .

 11 Figure 11. Results for ¤ 8¡ ¦ .

Table 1 .

 1 Running times for ¤ -approximation with ¤ ¡ ¤ .

	¡ -SKIP-SEARCH

¥

SHIFT-AND

¡ -TUNED-BOYER-MOORE

Table 2 .

 2 Running times for ¤ -approximation with ¤ ¡ © .

	¡ -SKIP-SEARCH

¥

SHIFT-AND

¡ -TUNED-BOYER-MOORE

Table 3 .

 3 Running times for ¤ -approximation with ¤ ¡ ¡ .

	¥	SHIFT-AND	¡ -TUNED-BOYER-MOORE	¡ -SKIP-SEARCH
	8	33.65	16.65	24.99
	9	33.14	16.05	24.06
	10	33.05	15.71	23.62
	20	32.93	14.82	21.42

Table 4 .

 4 Running times for ¤ -approximation with ¤ ¡

	¡ -SKIP-SEARCH

6

.

¥

SHIFT-AND

¡ -TUNED-BOYER-MOORE

Table 5 .

 5 Running times for ¤ -approximation with ¤ ¡ .

	¥	SHIFT-AND	¡ -TUNED-BOYER-MOORE	¡ -SKIP-SEARCH
	8	36.46	26.82	34.64
	9	34.46	24.36	31.46
	10	33.41	23.61	30.55
	20	33.00	22.32	27.54

Table 6 .

 6 Running times for ¤ -approximation with ¤ ¡ ¡ ¢ ¤£ ¦¥ £ ¨ § and 9¡ £ £ .

	¥	SHIFT-PLUS	' ¡ )¢ 0 -TUNED-BOYER-MOORE	' ¡ )¢ 0 -SKIP-SEARCH
	8	50.73	23.33	31.93
	9	50.32	27.78	35.52
	10	51.79	33.76	39.45
	20	50.26	32.46	36.91

Table 7 .

 7 Running times for ¤ -approximation with ¤ ¡ ¡ ¢ ¤£ ¦¥ £ ¨ § and 9¡ £ 4¤ .

	¥	SHIFT-PLUS	' ¡ )¢ 0 -TUNED-BOYER-MOORE	' ¡ )¢ 0 -SKIP-SEARCH
	8	50.88	23.16	31.99
	9	50.86	28.70	36.40
	10	51.87	33.74	39.58
	20	51.11	32.53	37.38

Table 8 .

 8 Running times for ¤ -approximation with ¤ ¡ ¡ ¢ ¤£ ¦¥ £ ¨ § and 9¡ £ ¥© .

	¥	SHIFT-PLUS	' ¡ )¢ 0 -TUNED-BOYER-MOORE	' ¡ )¢ 0 -SKIP-SEARCH
	8	50.72	23.33	32.02
	9	50.70	27.96	35.65
	10	51.94	33.88	40.00
	20	51.35	33.20	37.03

Table 9 .

 9 Running times for ¤ -approximation with ¤ ¡ ¡ ¢ ¤£ ¦¥

	¥	SHIFT-PLUS	' ¡ 1)¢ 0 -TUNED-BOYER-MOORE	' ¡ 1)¢ 0 -SKIP-SEARCH
	8	50.67	23.29	32.20
	9	50.83	28.38	35.74
	10	51.93	34.41	39.91
	20	50.18	32.94	37.10

£

¨ § and ¡ £ .

Table 10 .

 10 Running times for ¤ -approximation with ¤ ¡ ¡ ¢ ¤£ ¦¥ £ ¨ § and 9¡ £ 6 .

	¥	SHIFT-PLUS	' ¡ 1)¢ 0 -TUNED-BOYER-MOORE	' ¡ 1)¢ 0 -SKIP-SEARCH
	8	51.24	23.57	32.22
	9	50.31	28.33	35.73
	10	51.83	34.36	40.15
	20	49.97	32.77	37.03

Crochemore, Iliopoulos, Lecroq, Pinzon, Plandowski and Rytter / Occurrence and Substring Heuristics for -Matching

Crochemore, Iliopoulos, Lecroq, Pinzon, Plandowski and Rytter / Occurrence and Substring Heuristics for -Matching

Acknowledgements

The authors are very grateful to the anonymous referees who greatly improved the quality of this article.

The work of these authors was partially supported by NATO grant PST.CLG.977017.

!

The work of this author was partially supported by Welcome foundation, Royal Society and EPSRC grants.

symbols mismatches the symbol of the pattern or all of them match. This is because we cannot assume that the symbols at positions ¥ U D S6 $ ©¥ are random since they matched the symbols in the dictionary.

Making this assumption the average number of comparisons made by the naive algorithm at position

imilarly the average number of comparisons made by the naive algorithm at position ¥ 6 $ is

imilarly the average number of comparisons made by the naive algorithm at position ¥ V6 U $ for " $ ©¥ U 3D is