Gilles Didier
email: gilles.didier@univ-amu.fr

Laurent Tichit
email: laurent.tichit@univ-amu.fr

Designing optimal-and fast-on-average pattern matching algorithms

Given a pattern w and a text t, the speed of a pattern matching algorithm over t with regard to w, is the ratio of the length of t to the number of text accesses performed to search w into t. We first propose a general method for computing the limit of the expected speed of pattern matching algorithms, with regard to w, over iid texts. Next, we show how to determine the greatest speed which can be achieved among a large class of algorithms, altogether with an algorithm running this speed. Since the complexity of this determination make it impossible to deal with patterns of length greater than 4, we propose a polynomial heuristic. Finally, our approaches are compared with 9 pre-existing pattern matching algorithms from both a theoretical and a practical point of view, i.e. both in terms of limit expected speed on iid texts, and in terms of observed average speed on real data. In all cases, the pre-existing algorithms are outperformed.

Introduction

We focus on algorithms solving the online string matching problem, which consists in reporting all, and only the occurrence positions of a pattern w in a text t (online meaning that no pre-processing of the text is allowed). As one of the oldest problems addressed in computer science, it has been extensively studied. We refer to [START_REF] Faro | The Exact Online String Matching Problem: A Review of the Most Recent Results[END_REF] for a comprehensive list and an evaluation of all the pattern matching algorithms developed so far. By the authors' count, more than 80 algorithms have already been proposed, among which more than a half were published during the last ten years. This fact sounds quite paradoxical, since the Morris-Pratt algorithm, which is optimal in terms of worst case analysis, dates back to 1970.

A possible explanation is that there is wide gap between the worst case complexity of algorithms and their computation times on real data. For instance, there are pattern matching algorithms with non-linear worst case complexities, which perform much better than Morris-Pratt on English texts. Basically, the average case analysis is way more suited to assess the relevance of a pattern matching algorithm from a practical point of view. The average case analysis of some pattern matching algorithms, notably Boyer-Moore-Horspool and Knuth-Morris-Pratt, has already been carried out from various points of view [START_REF] Yao | The complexity of pattern matching for a random string[END_REF][START_REF] Guibas | String overlaps, pattern matching, and nontransitive games[END_REF][START_REF] Barth | An analytical comparison of two string searching algorithms[END_REF][START_REF] Baeza-Yates | Average running time of the Boyer-Moore-Horspool algorithm[END_REF][START_REF] Mahmoud | Analysis of Boyer-Moore-Horspool string-matching heuristic[END_REF][START_REF] Régnier | Complexity of Sequential Pattern Matching Algorithms[END_REF][START_REF] Smythe | The Boyer-Moore-Horspool heuristic with Markovian input[END_REF][START_REF] Tsai | Average Case Analysis of the Boyer-Moore Algorithm[END_REF]. We provide here a general method for studying the limit average behavior of a pattern algorithm over iid texts. More precisely, following [START_REF] Marschall | Probabilistic Arithmetic Automata and Their Application to Pattern Matching Statistics[END_REF], we consider the limit expectation of the ratio of the text length to the number of text accesses performed by an algorithm for searching a pattern w in iid texts. This limit expectation is called the asymptotic speed of the algorithm with regard to w under the iid model. The computation of the asymptotic speed is based on w-matching machines which are automata-like structures able to simulate the behavior of a pattern matching algorithm while searching the pattern w. The underlying idea is the same as in [START_REF] Marschall | Probabilistic Arithmetic Automata and Their Application to Pattern Matching Statistics[END_REF][START_REF] Marschall | Exact Analysis of Horspools and Sundays Pattern Matching Algorithms with Probabilistic Arithmetic Automata[END_REF][START_REF] Marschall | An Algorithm to Compute the Character Access Count Distribution for Pattern Matching Algorithms[END_REF][START_REF] Marschall | Probabilistic Arithmetic Automata and Their Applications[END_REF] and can be seen as a generalization of the string matching automaton [START_REF] Cormen | Introduction to Algorithms[END_REF].

In the companion paper, G. Didier provided a theoretical analysis of the asymptotic speed of pattern matching algorithms over iid texts [START_REF] Didier | Optimal pattern matching algorithms[END_REF]. In particular, he showed that, for a given pattern w, the greatest asymptotic speed among a large class of pattern matching algorithms, is achieved by a w-matching machine in which the states are essentially subsets of positions of w. Such machines are called strategies below.

We provide here a brute force algorithm computing the Fastest strategy for a given pattern w and the frequencies of an iid model. The algorithm is based on an original structure associated to the pattern w and called its position lattice, which gives a full representation of the overlap relations between the subsets of positions of w.

Since the brute force algorithm cannot be applied on patterns of length greater than 4, because of its (very high) time-complexity, we propose a polynomial K-Heuristic, in which the polynomial order K may be chosen by the user.

The Fastest and K-Heuristic approaches are finally compared with 9 several pre-existing pattern matching algorithms:

• from a theoretical point of view, by computing their limit expected speeds with regard to various patterns and iid models,

• from a practical point of view, by computing their average speeds over two sources (an English text and a DNA sequence).

In both cases, the Fastest and K-Heuristic (with K large enough) approaches outperform the pre-existing algorithms.

The software and the data used to perform the tests are available at https: //github.com/gilles-didier/Matchines.git.

The rest of the paper is organized as follows. Section 2 presents the notations and recalls some concepts and results from [START_REF] Didier | Optimal pattern matching algorithms[END_REF]. It is followed by two sections which introduce the central objects of this work: the strategies and the position lattice of a pattern. In particular, we provide an algorithm computing the position lattice of a given pattern. Section 5 shows how to use the position lattice of a pattern to obtain the Fastest strategy with regard to this pattern and an iid model. In Section 6, we provide a polynomial heuristic allowing to compute fast strategies. Section 7 presents the results of various comparisons between 9 pre-existing pattern matching algorithms, the K-Heuristic and, each time it is possible, the Fastest strategy. The results are discussed in the last section.

Notations and definitions

Notations and general definition

For all finite sets S, P(S) is the power set of S and |S| is its cardinal. An alphabet is a finite set A of elements called letters or symbols.

A word, a text or a pattern on A is a finite sequence of symbols of A. We put |v| for the length of a word v. Words are indexed from 0, i.e. v = v 0 v 1 . . . v |v|-1 . We write v [i,j] for the subword of v starting at its position i and ending at its position j, i.e. v [i,j] = v i v i+1 . . . v j . The concatenate of two words u and v is the word uv

= u 0 u 1 . . . u |u|-1 v 0 v 1 . . . v |v|-1 .
For any length n ≥ 0, we note A n the set of words of length n on A, and A , the set of finite words on A, i.e. A = ∞ n=0 A n . Unless otherwise specified, all the texts and patterns considered below are on a fixed alphabet A.

A pattern matching algorithm takes a pattern w and a text t as inputs an reports all, and only the occurrence positions of w in t. For all patterns w, we say that two pattern matching algorithms are w-equivalent if, for all texts t, they access exactly the same positions of t on the input (w, t).

Matching machines and the generic algorithm [8]

For all patterns w, a w-matching machine is 6-uple (Q, o, F, α, δ, γ) where

• Q is a finite set of states, • o ∈ Q is the initial state, • F ⊂ Q is the subset of pre-match states, • α : Q → N is the next-position-to-check function, which is such that for all q ∈ F , α(q) < |w|, • δ : Q × A → Q is the transition state function, • γ : Q × A → N is the shift function.
By convention, the set of states of a matching machine always contains a sink state , which is such that, for all symbols x ∈ A, δ( , x) = and γ( , x) = 0.

The order O Γ of a matching machine Γ = (Q, o, F, α, δ, γ) is defined as

O Γ = max q∈Q {α(q)}. S0 0 S1 1 S2 2 a/1 b/1 a/1 a/0 b/0 b/1
Figure 1: abb-matching machine of the naive algorithm. The next-position-to check are displayed below all states S0, S1 and S2. Edges from states Si are labelled with "x/γ(Si, x)" for all symbols x. The transition associated to a match is blue-colored.

The w-matching machines carry the same information as the Deterministic Arithmetic Automatons defined in [START_REF] Marschall | Exact Analysis of Horspools and Sundays Pattern Matching Algorithms with Probabilistic Arithmetic Automata[END_REF][START_REF] Marschall | An Algorithm to Compute the Character Access Count Distribution for Pattern Matching Algorithms[END_REF].

The generic algorithm takes a w-machine machine and a text t as inputs and outputs positions of t (Algorithm 1).

input : a w-matching machine (Q, o, F, α, δ, γ) and a text t output: all the occurrence positions of w in t (hopefully)

1 (q, p) ← (o, 0) 2 while p ≤ |t| -|w| do 3 if q ∈ F
and t p+α(q) = w α(q) then 4 print " occurrence at position p " 5 (q, p) ← (δ(q, t p+α(q) ), p + γ(q, t p+α(q) ))

Algorithm 1: The generic algorithm A w-matching machine Γ is valid if, for all texts t, the execution of the generic algorithm on the input (Γ, t) outputs all, and only the occurrence positions of w in t.

We claim that for all the pattern matching algorithms developed so far and all patterns w, there exists a w-matching machine Γ which is such that, for all texts t, the generic algorithm and the pattern matching algorithm access exactly the same positions of t on the inputs (Γ, t) and (w, t) respectively [START_REF] Didier | Optimal pattern matching algorithms[END_REF]. For instance, Figure 1 displays a abb-matching machine which is abb-equivalent to the naive algorithm.

Full-memory expansion -standard matching machines [8]

For all n ∈ N, R n is the set of subsets H of {0, . . . , n} × A verifying that, for all i ∈ {0, . . . , n}, there exists at most one pair in H with i as first entry.

(S0, ∅) For all H ∈ R n , we put f (H) for the set comprising all the first entries of the pairs in H, namely

0 (S1, {(0, a)}) 1 (S2, {(0, a), (1, b)}) 2 (S0, {(0, a)}) 0 (S0, {(0, b), (1, a)}) 0 (S0, {(0, b), (1, b)}) 0 (S0, {(0, b)}) 0 a/1 a/1 a/0 b/0 a/1 b/1 b/1 b/1 b/1 b/1
f (H) = {i | ∃x ∈ A with (i, x) ∈ H}. For all k ∈ N and H ∈ R n , the k-shifted of H is k ← - H = {(u -k, y) | (u, y) ∈ H with u ≥ k},
i.e. the subset of R n obtained by subtracting k from the first entries of the pairs in H and by keeping only the pairs with non-negative first entries.

The full memory expansion of a w-matching machine Γ = (Q, o, F, α, δ, γ) is the w-matching machine Γ obtained by removing the unreachable states of Γ = (Q , o , F , α , δ , γ ), defined as:

• Q = Q × R OΓ • o = (o, ∅) • α ((q, H)) = α(q)
• γ ((q, H), x) = γ(q, x)

• F = F × R OΓ • δ ((q, H), x) =          (δ(q, x), γ(q,x) ← ----------- H ∪ {(α(q), x)}) if ∀a ∈ A, (α(q), a) ∈ H if ∃a = x s.t. (α(q), a) ∈ H (δ(q, x), γ(q,x) ← - H ) if (α(q), x) ∈ H
By construction, at all iterations of the generic algorithm on the input (Γ , t), if the current state and position are (q, H) and p, respectively, then the positions of {j + p | j ∈ f (H)} are exactly the positions of t greater than p accessed so far (the second entries of the corresponding elements of H give the symbols read).

For all texts t, the generic algorithm access the same positions of t on the inputs (Γ, t) and (Γ , t) [START_REF] Didier | Optimal pattern matching algorithms[END_REF].

A w-matching machine Γ is standard if each state q of Γ appears in a unique pair/state of its full memory expansion. For all states q of a standard matching machine Γ, we put h Γ (q) for the second entry of the unique pair/state of Γ in which q appears. We implemented a basic algorithm computing the full-memory expansion

Γ = (Q , o , F , α , δ , γ ) of a w-matching machine Γ = (Q, o, F, α, δ, γ) in O(|w|.|Q |) time. We have |Q | ≤ (A + 1) |w| |Q|
but the size of Q may vary a lot with regard to the matching machine/algorithm considered.

iid and Markov models

An independent identically distributed (iid) model (aka Bernoulli model) is fully specified by a probability distribution π on the alphabet (i.e. π x is the probability of the symbol x in the model). Such a model will be simply referred to as "π" below. Under π, the probability of a text t is

p π (t) = |t|-1 i=0 π(t i ).
A Markov model M over a given set of states Q is a 2-uple (π M , δ M ), where π M is a probability distribution on Q (the initial distribution) and δ M associates a pair of states (q, q ) with the probability for q to be followed by q (the transition probability). Under a Markov model M = (π M , δ M ), the probability of a sequence s of states is F,α,δ,γ) be a w-matching machine. If a text t follows an iid model and Γ is standard then the sequence of states parsed by the generic algorithm on the input (Γ, t) follows a Markov model (π M , δ M ).

p M (s) = π M (s 0 ) |s|-1 i=0 δ M (s 0 , s 1 ). Theorem 1 ([8]). Let Γ = (Q, o,
Proof. Whatever the text model and the machine, the sequence of states always starts with o with probability 1. We have π M (o) = 1 and π M (q) = 0 for all q = o.

The probability δ M (q, q ) that the state q follows the state q during an execution of the generic algorithm, is equal to:

• 1, if there exists a symbol x such that δ(q, x) = q and (α(q), x) ∈ h Γ (q)),

•

x s.t. δ(q, x) = q π(x), otherwise, independently of the previous states.

Asymptotic speed

Let M be a text model and A be an algorithm. The w-asymptotic speed of A under M is the limit expectation, under M, of the ratio of the text length to the number of text accesses performed by A [START_REF] Didier | Optimal pattern matching algorithms[END_REF]. Namely, by putting a A (t) for the number of text accesses performed by A to parse t and p M (t) for the probability of t with regard to M, the asymptotic speed of

A under M is AS M (A) = lim n→∞ t∈A n |t| a A (t) p M (t).
The asymptotic speed AS M (Γ) of a w-matching machines Γ is that the generic algorithm with Γ as first input. From Theorem 5 of [START_REF] Didier | Optimal pattern matching algorithms[END_REF], the asymptotic speed of a standard w-matching machine Γ = (Q, o, F, α, δ, γ) under an iid model π exists and is given by

(1) AS π (Γ) = q∈Q α q E(q),
where (α q ) q∈Q are the limit frequencies of the states of the Markov model associated to Γ and π in Theorem 1, and

E(q) = γ(q, x) if (α(q), x) ∈ h Γ (q)),
x γ(q, x)π x otherwise. Computing the asymptotic speed of a pattern matching algorithm, with regard to a pattern w and an iid model π is performed by following the stages below.

1. We get a w-matching machine Γ which simulates the behavior of the algorithm while looking for w (Figure 1). The transformation of the 9 algorithms presented in Section 7 (and a few others, see our GitHub repository) into w-matching machines, given w, has been implemented.

2. We obtain the full-memory extension Γ of Γ (Figure 2, Section 2.3).

3. We compute the limit frequencies of the Markov model associated to Γ and π in Theorem 1. This mainly needs to solve a system of linear equations of dimension |Q |.

4.

We finally obtain the asymptotic speed of the algorithm from these limit frequencies, π and Γ by using Equation 1.

The most time-consuming stage is the computation of the limit frequencies, which has O(|Q | 3 ) time complexity, where |Q |, the number of states of the full memory expansion, is smaller than (A + 1) |w| |Q|.

Strategies

For all sets I ⊂ N and k ∈ N, we define the k-left-shifted of I as

∆(I, k) = {i -k | ∃i ∈ I and i ≥ k}. A w-strategy S = (Q, o, F, α, δ, γ) is a w-matching machine such that • Q ⊆ P({0, . . . , |w| -1}) \ {{0, . . . , |w| -1}} and ∅ ∈ Q, • o = ∅, • F = {s ∈ Q | |s| = |w| -1}, • α : Q → {0, 1, . . . , |w| -1} is such that for all s ∈ Q, α(s) ∈ s and |s| < |w| -1 ⇒ s ∪ {α(s)} ∈ Q, • γ : Q × A → {0, 1, .
. . , |w|} is such that for all states s and all symbols x, γ(q, x)

= min{k ≥ 1 | w α(s)-k = x if α(s) ≥ k and w j = w j+k for all j ∈ ∆(s, k)} if q ∈ F, min{k ≥ 0 | w α(s)-k = x if α(s) ≥ k and w j = w j+k for all j ∈ ∆(s, k)} otherwise, • δ : Q × A → Q is such that for all q ∈ Q and all symbols x, δ(s, x) = ∆(s ∪ {i}, γ(s, x)).
Proposition 1. A w-strategy is a standard, valid and non-redundant w-matching machine.

Proof. By construction, a w-strategy is both standard and non redundant. The validity of a w-strategy follows from Theorem 1 of [START_REF] Didier | Optimal pattern matching algorithms[END_REF].

Proposition 2. There is a w-strategy which achieves the greatest asymptotic speed among all the w-matching machines of order |w| -1.

Proof. The Corollary 2 of [START_REF] Didier | Optimal pattern matching algorithms[END_REF] implies that there exists a w-matching machine which achieves the greatest asymptotic speed among those of order of order |w| -1 and which is 4. in which all the states are relevant (i.e. such that they may lead to a match without any positive shift [START_REF] Didier | Optimal pattern matching algorithms[END_REF]), 5. such that there is no pair of states (q, q ) with q = q and h Γπ (q) = h Γπ (q ).

1. standard, 2. compact, 3. valid,
Let us verify that a w-matching machine Γ = (Q, o, F, α, δ, γ) of order |w| -1 satisfying the properties above is (isomorphic to) a w-strategy. Since it verifies in particular the properties 4 and 5, its set of states Q is in bijection with a subset of P({0, . . . , |w| -1}). Let us identify all states q of Q with f (h Γ (q)), its corresponding element of P({0, . . . , |w| -1}). Since Γ is standard, compact and of order |w| -1, we don't have {0, . . . , |w| -

1} ∈ Q. Moreover, since Γ is standard, we have δ(s, x) = ∆(s ∪ {i}, γ(s, x)). Last, by construction, if γ(q, x) > min{k ≥ 1 | w α(s)-k = x if α(s) ≥ k and w j = w j+k for all j ∈ ∆(s, k)} if q ∈ F, min{k ≥ 0 | w α(s)-k = x if α(s) ≥ k and w j = w j+k for all j ∈ ∆(s, k)} otherwise,
then Γ is not valid, and if

γ(q, x) < min{k ≥ 1 | w α(s)-k = x if α(s) ≥ k and w j = w j+k for all j ∈ ∆(s, k)} if q ∈ F, min{k ≥ 0 | w α(s)-k = x if α(s)
≥ k and w j = w j+k for all j ∈ ∆(s, k)} otherwise, then δ(q, x) is not relevant.

Position lattices

The position lattice of a pattern w is the 3-uple

L [w] = (Q [w] , (δ [w] s ) s∈Q [w] , (γ [w] s ) s∈Q [w]
) where, by putting s for {0, . . . , |w| -1} \ s,

• Q [w] = P({0, . . . , |w| -1}) \ {{0, . . . , |w| -1}}, i.e. the set made of all the subsets of positions of w but {0, . . . , |w| -1},

• for all s ∈ Q [w] , γ [w] s is a map from s × A to {0, . . . , |w|}, • for all s ∈ Q [w] , δ [w] s is a map from s × A to Q [w] ,
where, for all s ∈ Q [w] , all i ∈ s and all x ∈ A, we have

γ [w] s (i, x) = min{k ≥ 1 | w α(s)-k = x if α(s) ≥ k and w j = w j+k for all j ∈ ∆(s, k)} if |s| = |w| -1, min{k ≥ 0 | w α(s)-k = x if α(s) ≥ k and w j = w j+k for all j ∈ ∆(s, k)} otherwise,
and

δ [w] s (i, x) = ∆(s ∪ {i}, γ [w] s (i, x)).
In particular, if x = w i and |s| < |w| -1 then we have γ

[w] s (i, x) = 0 and δ [w] s (i, x) = s ∪ {i}.
Let us remark that, since max(s) ≤ |w| -1 for all s ∈ Q [w] , we have, for all i ∈ s and all x ∈ A, ∆(s ∪ {i}, |w|) = ∅, thus γ

s (i, x) ≤ |w| which is consistent with the definition of γ [w]
s . The edges of L [w] are the pairs (s, δ s (i, x)) for all s ∈ Q [w] , all i ∈ s and all x ∈ A (see Figure 3).

∅ {0} {1} {2} {0, 1} {0, 2} {1, 2} 0, a|0 0, b|1 1, a|1 1, b|0 2, a|2 2, b|0 1, a|1 1, b|0 2, a|2 2, b|0 0, a|0 0, b|2 2, a|2 2, b|0 2, a|2 2, b|3 0, a|0 0, b|1 1, a|1 1, b|0 1, a|1 1, b|3 0, a|3 0, b|3
Figure 3: Position lattice of the pattern abb. Vertices represent the states of L [abb] . For all states s, there is an outgoing edge for all pairs (i, x) with i ∈ {0, . . . , |abb| -1} \ s and x ∈ A. This outgoing edge is labeled with "i, x|γ

[abb] s (i, x)", is colored according to i, and goes to δ Remark 2. Let s be a state of Q [w] , i and j be two positions in s such that i = j and x and y be two symbols of A. We have

γ [w] δ [w] s (i,x) (j -γ [w] s (i, x), y) + γ [w] s (i, x) = γ [w] δ [w] s (j,y) (i -γ [w] s (j, y), x) + γ [w]
s (j, y), and

δ [w] δ [w] s (i,x) (j -γ [w] s (i, x), y) = δ [w] δ [w] s (j,y) (i -γ [w] s (j, y), x).
By considering the particular case where x = w i , we get

γ [w] s∪{i} (j, y) = γ [w] δ [w] s (j,y) (i -γ [w] s (j, y), w i ) + γ [w]
s (j, y), and

δ [w] s∪{i} (j, y) = δ [w] δ [w] s (j,y) (i -γ [w] s (j, y), w i ).
Let prec w be the table indexed on {0, . . . , |w| -1} × A and in which, for all positions i of w and all symbols x of A, the entry prec w [i, x] is defined as

prec w [i, x] = max{j ≤ i | w j = x} if {j ≤ i | w j = x} = ∅, NULL otherwise.
Lemma 1. Let s be a state of Q [w] , i a position in s and x a symbol of A.

1. If x = w i then • if |s| = |w|-1 then δ [w] s (i, x) = {0, . . . , B-1} and γ [w]
s (i, x) = |w|-B, where B is the length of the longest proper suffix of w which is a prefix of w;

• otherwise δ [w] s (i, x) = s ∪ {i} and γ [w] s (i, x) = 0. 2. If x = w i , (a) if s = ∅ then δ [w] ∅ (i, x) = {prec w [i, x]} if prec w [i, x] = NULL, ∅ otherwise, γ [w] ∅ (i, x) = i -prec w [i, x] if prec w [i, x] = NULL, i + 1 otherwise, (b) if s = ∅ then for all ∈ s, we have δ [w] s (i, x) = δ [w] δ [w] s\{ } (i,x) ( -γ [w] s\{ } (i, x), w ), γ [w] s (i, x) = γ [w] δ [w] s\{ } (i,x) ( -γ [w] s\{ } (i, x), w ) + γ [w] s\{ } (i, x).
Proof. The only case which does not immediately follow from the definition of L [w] , is when x = w i and s = ∅ which is given by Remark 2.

The relation on Q [w] is defined as follows. For all sets s and s in Q [w] , we have s s if one of the following properties holds:

• |s| < |s |,
• |s| = |s |, s = s and min(s s ) ∈ s, where s s is the symmetric difference of s and s ,

• s = s .

The relation defines a total order on Q [w] . We write " s ≺ s " for " s s and s = s ".

Lemma 2. Let s be a state of Q [w] with |s| > 1, i a position in s and x a symbol of A.

If x = w i then δ [w]
s\{max s} (i, x) ≺ s.

Proof. Under the assumption that |s| > 1, we have min s = min(s \ {max s}).

By construction, the fact that x = w i implies that γ

[w] s\{max s} (i, x) > 0. If we have min((s \ {max s}) ∪ {i}) < γ [w] s\{max s} (i, x) then |δ [w] s\{max s} (i, x)| < |s|, thus δ [w] s\{max s} (i, x) ≺ s. Otherwise, we have |δ [w] s\{max s} (i, x)| = |s| but since necessarily min δ [w] s\{max s} (i, x) ≤ min|s| -γ [w]
s\{max s} (i, x) < min|s|, we get again δ Proof. Let us first show that Algorithm 2 determines the shifts and the transitions of the state s before those of the state s if and only if s ≺ s . The loop at Lines 3-9 computes the shifts and the transitions of ∅. Next, the loop at Lines 10-24 computes the shifts and the transitions of the singletons from {0} to {|w| -1}. The last loop (Lines 25-43) determines the shifts and the transitions of the states corresponding to the subsets of increasing cardinals from 2 to |w| -1. Inside the last loop, the way in which the next subset s is computed from the current subset s, both of cardinal , ensures that s ≺ s (Lines 39-43).

For all iterations i of the loop at Lines 3-9 and all symbols x, we have last[x] = prec w [i, x] at the beginning of the inner loop (Line 5). From Lemma 1 (Cases 1 and 2a), the transitions δ ∅ (i, x) for all positions i of w and all symbols x, are correctly computed at the end of the loop.

The loop at Lines 10-24 computes the shifts and the transitions from the singleton states. For all pairs of positions (i, j) and all symbols x, determining δ 1 B ← length of the longest proper suffix of w which is also a prefix;

2 for x ∈ A do last[x] ← NULL ; 3 for i = 0 to |w| -1 do 4 last[wi] ← i; 5 for x ∈ A do 6 if last[x] = NULL then 7 γ [w] ∅ (i, x) ← i -last[x]; δ [w] ∅ (i, x) ← {last[x]}; 8 else 9 γ [w] ∅ (i, x) ← i + 1; δ [w] ∅ (i, x) ← ∅; 10 for i = 0 to |w| -1 do 11 for j = 0 to i -1 do 12 for x ∈ A do 13 γ [w] {i} (j, x) ← γ [w] ∅ (j, x) + γ [w] δ [w] ∅ (j,x) (i -γ [w] ∅ (j, x), wi); 14 δ [w] {i} (j, x) ← δ [w] δ [w] ∅ (j,x) (i -γ [w] ∅ (j, x), wi); 15 for j = i + 1 to |w| -1 do 16 for x ∈ A do 17 if x = wj then 18 if |w| = 2 then 19 γ [w] s (i, x) ← |w| -B; δ [w] s (i, x) ← {0, . . . , B -1}; 20 else 21 γ [w] {i} (j, x) ← 0; δ [w] {i} (j, x) ← {i, j}; 22 else 23 γ [w] {i} (j, x) ← γ [w] δ [w] ∅ (i-1,w i ) (j -γ [w] ∅ (i -1, wi), x); 24 δ [w] {i} (j, x) ← δ [w] δ [w] ∅ (i-1,w i ) (j -γ [w] ∅ (i -1, wi), x);
s (i, x) ← |w| -B; δ [w] s (i, x) ← {0, . . . , B -1}; 34 else 35 γ [w] s (i, x) ← 0; δ [w] s (i, x) ← s ∪ {i}; 36 else 37 γ [w] s (i, x) ← γ [w] s (i, x) + γ [w] δ [w] s (i,x) (S[ -1] -γ [w] s (i, x), w S[ -1] ); 38 δ [w] s (i, x) ← δ [w] δ [w] s (i,x) (S[ -1] -γ [w] s (i, x), w S[ -1] ); 39 j ← -1; 40 while j ≥ 0 and S[j] ≥ |w| -+ j do j ← j -1 ; 41 if j ≥ 0 then 42 S[j] ← S[j] + 1; 43 for k = j + 1 to -1 do S[k] ← S[k -1] + 1 ; 44 until j < 0;
Algorithm 2: Computation of the position lattice.

• If i > j, then δ [w]
∅ (j, x) ≺{i} and its shifts and transitions were already computed. Formula of Remark 2 gives us those of {i} (Lines 13-14).

• If i < j, we distinguish between two subcases according to the symbol x considered. If x = w j then the shift and the transition state are given in Lemma 1 -Case 1. Otherwise, we remark that, since γ

[w] {i} (j, x) is positive, we have that γ [w] {i} (j, x) = min{k ≥ 1 | w j-k = x if j ≥ k and w i-k = w i }. This implies that γ [w] {i} (j, x) = γ [w] δ [w] ∅ (i-1,wi) (j, x). We have δ [w]
∅ (i-1, w i ) ≺ s, thus both the shifts and the transitions of the state δ The last loop, lines 25-43, computes the shifts and the transitions of the states corresponding to the subsets of cardinals 2 to -1. For all states s with 2 ≤ |s| ≤ |w| -1, all positions i ∈ s and all symbols x = w i , the corresponding shift and transition γ s\{max s} (i, x) following Lemma 1 -Cases 2b (in Algorithm 2, we put s for s \ {max s}). Lemma 2 ensures that δ

[w] s\{max s} (i, x) ≺ s, thus that the shifts and transitions of δ

The Fastest w-strategy

Determining the fastest w-strategy, which, from Proposition 2, has the greatest asymptotic speed among all the w-matching machines of order |w| -1, may be performed by computing the asymptotic speed of all the w-strategies and by returning the fastest one.

In order to enumerate all the w-strategies, let us remark that they are all contained in the position lattice of w in the sense that:

• the set of states of a w-strategy is included in that of the position lattice;

• all the w-strategies Γ = (Q, o, F, α, δ, γ) verify δ(s, x) = δ [w] s (α(s), x) and γ(s, x) = γ [w]
s (α(s), x) for all s ∈ Q and all symbols x.

Reciprocally, to any map φ from Q [w] to {0, . . . , |w|-1} such that φ(s) ∈ s for all states s ∈ Q [w] , there corresponds the unique w-strategy S = (Q, o, F, α, δ, γ) for which the next-position-to-check function α coincides with φ on Q.

Finally, our brute force algorithm 1. takes as input a pattern w and an iid model π,

computes the position lattice of w,

3. enumerates all the maps φ such that φ(s) ∈ s for all states s ∈ Q

[w] ,
4. for each φ, gets the corresponding w-strategy by keeping only the states of Q [w] reachable from ∅, with the next-position-to-check function φ, 5. computes the asymptotic speed of all the w-strategies under π,

6. returns the w-strategy with the greatest speed.

The time complexity of the brute force algorithm is

O     |w|-1 k=1 k ( |w| k )   2 3|w|   ,
where the first factor stands for the number of functions φ and the second one for the computation of the asymptotic speed of a w-strategy, which needs to solve a linear system of size equal to the number of states, which is O(2 |w| ). Its memory space complexity is |w|2 |w|-1 , i.e. what is needed to store the position lattice of w.

Under its current implementation, the brute force determination of the fastest w-strategy is unfeasible for patterns of length greater than 4.

A polynomial heuristic

There are two points which make the complexity of the brute force algorithm that high:

1. the size of the position lattice, which is exponential with the length of the pattern, 2. determining the fastest strategy in the position lattice, which needs a time exponential with its size.

Our heuristic is based on two independent stages, each one aiming to overcome one of these two points. Both of them start from the general idea that, since, for any current position of the text, the probability that no mismatch occurs until the n th text access decreases geometrically with n, the first relative positions accessed by a strategy (or more generally by a pattern algorithm) are those which have the greatest influence on its asymptotic speed.

n-sets sublattices

A sufficient condition for a sublattice U ⊆ Q [w] to contain a w-strategy is that, for all s ∈ U, there exists at least a position i ∈ s with δ s (i, x) ∈ U for all x ∈ A. A sublattice U verifying this condition will be said to be complete.

Let us introduce some additional notations here. For all sets S of positions, the prefix of S is defined as P (S) = max{i ∈ S | j ∈ S for all 0 ≤ j ≤ i} and its rest is R(S) = S \ {0, . . . , P (S)} For all positive integers n, the n-sets sublattice of w is the sublattice U of Q [w] which contains all and only the subsets of Q [w] with a rest containing less than n positions, i.e. the subsets of the form {0, . . . , p} ∪ X with p < |w| -1 and |X | ≤ n.

By construction, the n-sets sublattice of w is complete. It contains O(|w| n ) states and O(|w| n+1 ) transitions.

We adapted Algorithm 2 to compute the n-sets sublattice of w in O(|w| n+1 ) time with the same amount of memory space.

-shift expectation

We are now interested in a fast way for finding an efficient w-strategy in a given complete sublattice. For all integers and all states s of a sublattice U, the -shift expectation of s is defined as the greatest shift expectation one could possibly get in steps in U by starting from s. Namely, the -shift expectation is computed following the recursive formula:

• ES [w] 0 [s] = 0, • for all k > 0, ES [w] k [s] = max i∈Tr(s) x∈A γ [w] s (i, x) + ES [w] -1 [δ [w] s (i, x)]
where Tr(s

) = {i ∈ s | δ [w]
s (i, x) ∈ U for all x ∈ A}. The -shift expectation of a complete sublattice U is well defined and can be computed in O( T ) time, where T is the number of transitions of the sublattice U and by using O(|U|) memory space.

We finally extract a w-strategy from U by setting the next-position-to-check of all states s ∈ U to arg max

i ∈Tr(s) x ∈A γ [w] s (i, x) + ES [w] -1 [δ [w] s (i, x)] .

K-Heuristic

The K-Heuristic combines the two approaches above in order to compute a w-strategy in a time polynomial with the length of the pattern.

Being given an order K ≥ 1, we start by computing the K-sets sublattice of w, thus in O(|w| K+1 ) time. In order to select a w-strategy from the K-sets sublattice, we next compute the (K + 1)-shift expectation of all its states and extract a w-strategy as described just above. This computation is performed in O(K|w| K+1 ) time, since the number of transition of the sublattice is O(|w| K+1 ), by using O(|w| K ) memory space.

Let us remark that the order of the -shift expectation does not have, a priori, to be strongly related to the order K of the K-sets sublattice on which it is computed. By experimenting various situations, we observed that considering an order greater than K + 1 generally does not improve much the performances, whereas the strategies obtained from -expectations with smaller than K may be significantly slower.

The K-Heuristic returns a w-strategy in O(K|w| K+1 ) time by using O(|w| K ) memory space. We insist on the fact that the K-Heuristic generally does not return the fastest strategy, even if K > |w|. However, we will see in the next section that it performs quite well in practice.

Evaluation

We shall compare the approaches introduced in Sections 5 and 6 with selected pattern matching algorithms. The comparison is performed, first, from a theoretical point of view, by computing their asymptotic speeds under iid models, and second, in practical situations, by measuring their average speed over real data. The average speed with regard to a pattern w, of an algorithm or a matching machine on a text t is the ratio of |t| to the number of text accesses performed by the algorithm to search w in t.

We are also interested in to what extent taking into account the frequencies of the letters of an iid model or a text, for determining the Fastest and the K-Heuristic strategies, actually improves their asymptotic or their average speeds. To this purpose, we compute the Fastest and the K-Heuristic strategies from the uniform iid model. Next, we test their efficiency in terms of asymptotic speed under a non-uniform iid model and in terms of average speeds on data with non-uniform frequencies of letters.

Pre-existing pattern matching algorithms

More than forty years of research have already led to the development of dozens algorithms. We selected the 9 ones below for our evaluation: 6. TVSBS [START_REF] Thathoo | TVSBS: A fast exact pattern matching algorithm for biological sequences[END_REF], a"right-to-left" algorithm in which shifts are given by a badcharacter rule [START_REF] Boyer | A fast string searching algorithm[END_REF][START_REF] Sunday | A very fast substring search algorithm[END_REF] taking into account the two letters at distances |w|-1 and |w| from the current position of the text, 7. EBOM [START_REF] Faro | Efficient variants of the backward-oracle-matching algorithm[END_REF], a version of the Backward Oracle Matching algorithm [START_REF] Allauzen | Efficient experimental string matching by weak factor recognition[END_REF] which also uses a "bad two-characters" rule, 8. HASHq [START_REF] Wu | A fast algorithm for multi-pattern searching[END_REF], which implements the Boyer-Moore algorithm on blocks of length q by using efficient hashing techniques [START_REF] Karp | Efficient randomized pattern-matching algorithms[END_REF] (our tests are performed with q = 3), 9. FJS [START_REF] Franek | A simple fast hybrid patternmatching algorithm[END_REF], which combines the ideas of Knuth-Morris-Pratt [START_REF] Knuth | Fast pattern matching in strings[END_REF] and Sunday [START_REF] Sunday | A very fast substring search algorithm[END_REF] algorithms.

Algorithms 1 to 5 are classics. The last four ones were chosen for being known to be efficient on short patterns and small alphabets [START_REF] Faro | The Exact Online String Matching Problem: A Review of the Most Recent Results[END_REF], a situation in which the determination of the fastest strategy is feasible.

Let us remark that the order of the w-matching machine associated to TVSBS is equal to |w|, thus greater than that of the Fastest strategy that we compute.

The transformation into matching machines was implemented for a few other pattern matching approaches, for instance the SA algorithm (the Baeza-Yates-Gonnet algorithm) based on bitwise operations [START_REF] Baeza-Yates | A new approach to text searching[END_REF], or the string-matching automaton [START_REF] Cormen | Introduction to Algorithms[END_REF]. Since the asymptotic and average speeds of these two algorithms are exactly 1, whatever the pattern, the model and the text, there is no point in displaying them.

Results

We shall evaluate:

• the pre-existing pattern matching algorithms presented in Section 7.1,

• the 1-2-and 3-Heuristics and

• the Fastest strategy (each time it is possible).

Asymptotic speed

The asymptotic speeds are computed for texts and patterns on the binary alphabet {a, b}.

Table 1 displays the asymptotic speeds for all the patterns of length 4 on iid texts drawn from the uniform distribution. As expected, the strategy computed with the brute force algorithm (last column) is actually the fastest, but the speeds of the 1-,2-and 3-Heuristics are very close. The pre-existing algorithms are outperformed by all our approaches (even by the 1-Heuristic) for all the patterns. We observe that the Naive, Morris-Pratt and Knuth-Morris-Pratt algorithms have asymptotic speeds always smaller than 1. One cannot expect them to be faster since, by construction, they access all the positions of a text at least once. In the following, we will not display their speeds, nor that of Quicksearch, for they are always smaller than at least one of the other preexisting algorithms. The full tables can easily be re-computed by using our software. Table 3: Asymptotic speeds for some patterns of length 10 on {a, b} (drawn from the uniform distribution) under the iid model (π a , π b ) = (0.1, 0.9).

N a i v e M o r r i s -P r a t t K n u t h -M o r r i s -P r a t t Q u i c k s e a r c h H o r s p o o l F J S T V S B S E B O M H a s h q 1 -H e u r i
Table 2 displays the asymptotic speeds with regard to the same patterns as Table 1, but under the iid model (π a , π b ) = (0.1, 0.9). This table shows the asymptotic speeds of the K-Heuristics and the Fastest strategies computed with regard to an uniform iid model (the columns starting with "Unif."). The strategies such obtained are not optimized according to the letter probabilities of the model. They may be used as general purpose approaches, while the strategies obtained from the model probabilities will be called adapted below. Overall, our methods are faster than the pre-existing algorithms, with a few exceptions: Horspool is faster than the 1-Heuristic for two patterns ending with the rare letter a: aaaa and baaa. And EBOM is faster than the 1-Heuristic for searching baba. The K-Heuristics and the Fastest strategies computed with regard to an uniform iid model have asymptotic speeds smaller than their counterparts obtained from the actual probabilities of the text model (here highly unbalanced). Nevertheless, the uniform approaches still perform quite well, notably better than the pre-existing algorithms, except for the uniform 1-Heuristic and the same patterns as above.

Considering longer patterns leads to similar observations. Table 3 shows the asymptotic speeds obtained for random patterns of length 10. The 3-Heuristic outperforms all the others approaches (the Fastest strategy cannot be computed for this length). The (uniform) 1-Heuristic is slower than algorithms such EBOM or Hashq. But both the uniform 2-and 3-Heuristic overall perform better than the pre-existing algorithms, though they are slightly slower for a few patterns.

Average speed

Our data benchmark consists in the Wigglesworthia glossinidia genome, known for its bias in nucleotide composition (78% of {a, t}), and the Bible in English 4: Average speeds for some patterns of length 4 picked from the benchmark data (the Wigglesworthia glossinidia complete genome and the Bible in English). from [START_REF] Faro | The Exact Online String Matching Problem: A Review of the Most Recent Results[END_REF].

H o r s p o o l F J S T V S B S E B O M H a s h q U n i f .
Table 4 displays the average speeds of patterns randomly picked from the data. Let us remark that we are now dealing with real texts, which are not iid. In particular, the Fastest strategy could possibly be outperformed (this is not observed on the benchmark data). The 2-and 3-Heuristics, uniform and adapted, are faster than the pre-existing algorithms for all the patterns, whereas the 1-Heuristic is sometimes slightly outperformed by Horspool. Horspool is almost as fast as our approaches on the Bible while being sometimes significantly outperformed on the Wigglesworthia glossinidia genome. The average speeds are overall greater on the Bible than on the DNA sequence. In both cases, we do not observe a wide performance gap between the uniform and the adapted approaches, though our benchmark data are far from following an uniform iid model. Let us remark that the 2-and 3-Heuristics have almost the same performances both in the uniform and the adapted cases.

Table 5 shows the averages speeds with regard to patterns of length 30. The average speeds on the Bible are about twice those on the Wigglesworthia glossinidia genome. One actually expects the speed to be greater in average on texts with large alphabets, since the less likely the match between two symbols, the greater the shift expectation per iteration. Again the 3-Heuristic, uniform or Table 5: Average speeds for some patterns of length 30 picked from the benchmark data (the Wigglesworthia glossinidia complete genome and the Bible in English).

H o r s p o o l F J S T V S B S E B O M H a s h q U n i f .
adapted, outperforms the pre-existing algorithms. The speeds of the 3-Heuristic and of the 2-Heuristic differ in a greater amount than with patterns of length 4 for the Wigglesworthia glossinidia genome, and, to a smaller extent, for the Bible.

Discussion

In practical situations and though they don't take into account the letter frequencies, the uniform K-Heuristics and the uniform Fastest strategy perform generally almost as well as their adapted counterparts. The greatest difference observed is for the patterns of length 30 on the Wigglesworthia glossinidia genome (Table 5) and is relatively small. We do observe a notable amount of difference for the quite extreme case of the asymptotic speed under the iid model (π a , π b ) = (0.1, 0.9). But even for these frequencies, the uniform approaches show greater asymptotic speeds than any of the selected pre-existing algorithms. The 3-Heuristic has very good results whatever the pattern or the text. There is no situation for which the performances of the 2-heuristic are far from the best. On the contrary, the performance ranking of the pre-existing algorithms depends heavily on the patterns and on the texts or the model. For instance, Horspool may perform very well, even almost optimally, for some patterns and texts or models while its speed may completely plummet in other situations.

The question of selecting the most efficient order of K-Heuristic still deserves further investigations. A basic answer could be "the greater, the better" but we should take into consideration that an higher order of heuristic comes with an increased computational cost. After some experiments, we observed that the asymptotic speed the K-Heuristic tends to stop improving beyond a certain rank. For instance, the difference in average speed between the 2-and 3-Heuristics for patterns of length 4, both on the genome and on the Bible, probably does not justify the computational cost of the 3-Heuristic, while it is worth to use the 3-Heuristic rather than the 2-Heuristic for searching patterns of length 30 in the Bible (not that much for the Wigglesworthia glossinidia genome). The best trade-off for the order of the K-Heuristic depends on the pattern (notably its length) and on the text features (in particular the alphabet size and the letter frequencies).

It is certainly possible to obtain efficient heuristic with a lower computational cost than for the K-Heuristic. Since in standard situation, the length of the text is much greater thna that of the pattern, there is no real reason for considering only pattern matching algorithms with linear pre-processings of the pattern. In the extreme case where the texts are arbitrary long with regard to the patterns, any pre-processing, i.e. whatever its computation time, would be beneficial as soon as it improves the overall speed.

Figure 2 :

 2 Figure 2: Full memory expansion of the abb-matching machine of Figure 1.

Remark 1 .

 1 The position lattice of w contains 2 |w| -1 states and |A|.|w|.2 |w|-1 edges.

Theorem 2 .

 2 s\{max s} (i, x) ≺ s. Algorithm 2 computes the position lattice of the pattern w in O(|w|2 |w| ) time by using the same amount of memory.

∅

  (i, x) and the shifts γ

  [w] {i} (j, x) and γ[w] {i} (j, x) is performed by distinguishing between two cases.

25 for = 2

 2 to |w| -1 do 26 for j = 0 to -1 do S[j] ← j ; 27 repeat 28 s ← {S[0], . . . , S[ -1]}; s ← {S[0], . . . , S[ -2]}; 29 for i ∈ {0, . . . , |w| -1} \ s do 30 for x ∈ A do 31 if x = wi then 32 if = |w| -1 then 33 γ [w]

∅

  (i -1, w i ) are computed before s (Lines 23-24).

  [w]s (i, x) and δ [w] s (i, x) are computed from the shifts and transitions of the state δ [w]

  s\{max s} (i, x) are computed before those of s. For all states s with 2 ≤ |s| ≤ |w| -1, all positions i ∈ s, the shift and transition γ [w] s (i, w i ) and δ [w] s (i, w i ) are given in Lemma 1 -Case 1. The time complexity is O( |w|-1 k=0 (k + |w|k) |w| k ) (loop Lines 25-43), i.e. O(|w|2 |w| ). We do not use more memory than needed to store the lattice, which is, from Remark 1, O(|w|2 |w| ).

Table 1 :

 1 Asymptotic speeds for the patterns of length 4 on {a, b} under the uniform model.

	s t i c 2 -H e u r i s t i c 3 -H e u r i s t i c F a s t e s t

Table 2 :

 2 Asymptotic speeds the patterns of length 4 on {a, b} under the iid model (π a , π b ) = (0.1, 0.9).

	H o r s p o o l F J S	T V S B S E B O M	H a s h q	U n i f . 1 -H e u r i s t i c U n i f . 2 -H e u r i s t i c U n i f . 3 -H 1 -H e u r i s t i c e u r i s t i c 2 -H e u r i s t i c 3 -H e u r i s t i c
	babbbaabab 0.85 0.42 0.22 1.42 1.57 1.09 1.98 1.54 1.22 2.38 2.71
	ababbbbbab 0.70 0.55 0.29 0.77 0.85 1.19 1.34 1.47 1.43 1.87 2.34
	aaabaaaaba 0.91 0.87 3.01 3.93 2.61 3.04 4.78 4.92 3.04 4.79 5.27
	bbbabbabab 0.84 0.27 0.24 1.45 1.77 1.02 1.05 1.72 1.02 1.29 2.30
	bbabaabbab 0.80 0.31 0.22 2.21 1.92 1.15 1.41 1.69 1.15 2.14 3.02
	baabbaaaaa 4.10 2.17 1.86 2.40 2.45 1.99 4.03 4.72 1.99 4.06 4.78
	abbbababbb 0.31 0.58 0.32 1.32 1.20 1.08 1.33 1.52 1.35 1.90 2.29
	baabbbabba 0.90 0.81 0.68 1.39 1.14 1.61 1.12 1.63 1.73 2.44 2.78
	baabbaabab 0.85 0.37 0.22 2.22 2.29 1.77 2.21 2.26 1.77 3.15 3.54
	bbbbababbb 0.31 0.26 0.20 0.95 0.84 1.03 1.05 1.10 1.03 1.20 1.50

Table

  .89 3.05 3.06 3.01 2.89 3.05 3.06 3.06 are 3.13 1.76 1.60 1.45 0.67 3.01 3.16 3.16 3.11 3.01 3.16 3.16 3.16 at d 3.15 2.02 1.85 1.46 0.66 2.96 3.22 3.22 3.22 2.96 3.22 3.22 3.22 f th 2.72 1.81 1.69 1.35 0.65 2.94 3.03 2.87 3.05 2.94 3.10 3.10 3.10 r th 2.73 1.80 1.69 1.36 0.66 2.94 3.04 2.87 3.06 2.94 3.12 3.12 3.12 fede 3.35 1.97 1.73 1.49 0.66 3.23 3.53 3.53 3.53 3.23 3.53 3.53 3.53

		1 -H e u r i s t i c U n i f . 2 -H e u r i s t i c U n i f . 3 -H e u r i s t i c U n i f . F a s t e s t 1 -H e u r i s t i c 2 -H e u r i s t i c 3 -H e u r i s t i c F a s t e s t
	atat 1.17 0.77 0.74 1.04 0.60 1.46 1.70 1.74 1.80 1.46 1.73 1.73 1.81
	tatg 1.69 1.11 1.28 1.10 0.63 1.64 2.16 2.16 2.16 1.64 2.16 2.16 2.17
	aaat 1.58 0.85 0.66 0.92 0.58 1.57 1.76 1.84 1.84 1.57 1.80 1.90 1.90
	tccc 2.82 1.70 1.50 1.43 0.63 2.72 3.03 3.08 3.09 2.72 3.03 3.08 3.09
	caat 1.53 0.77 0.71 1.05 0.63 1.74 1.87 1.83 1.87 1.74 1.94 1.97 1.97
	aacc 2.47 1.56 1.45 1.23 0.63 2.12 2.67 2.77 2.77 2.12 2.69 2.77 2.77
	acta 1.36 0.70 0.76 1.26 0.65 1.67 1.77 1.81 1.85 1.67 1.85 1.88 1.88
	tatc 1.67 1.12 1.27 1.09 0.63 1.64 2.15 2.14 2.14 1.64 2.15 2.14 2.15
	gtga 1.92 0.82 0.93 1.34 0.65 1.97 2.11 2.09 2.11 1.97 2.17 2.18 2.19
	gatt 1.07 0.87 0.89 1.06 0.63 1.75 2.04 1.87 2.04 1.75 2.04 2.04 2.05
	he m 3.16 2.02 1.85 1.39 0.66 2.88 3.23 3.23 3.24 2.88 3.24 3.24 3.24
	, to 3.20 1.91 1.78 1.42 0.66 3.01 3.28 3.25 3.28 3.01 3.29 3.29 3.29
	usal 3.53 2.18 1.87 1.48 0.66 3.50 3.60 3.60 3.62 3.50 3.62 3.62 3.62
	le t 2.84 1.78 1.70 1.42 0.66 2.89 2.99 3.03 3.06 2.89 3.07 3.07 3.07
	hem	3.04 1.59 1.48 1.45 0.66 21

  at the mount called the mount 11.9 5.9 8.0 11.[START_REF] Cormen | Introduction to Algorithms[END_REF] 8.6 8.0 17.2 18.0 8.0 17.6 18.4 ith Israel, to wit, with all t 13.3 7.2 8.4 12.6 8.7 8.9 17.1 18.0 9.1 18.0 18.8 Syria, that dwelt at Damascus, 16.2 8.4 9.6 12.8 8.8 10.4 19.3 20.0 10.4 19.6 20.1

				1 -H e u r i s t i c U n i f . 2 -H e u r i s t i c U n i f . 3 -H 1 -H e u r i s t i c e u r i s t i c 2 -H e u r i s t i c 3 -H e u r i s t i c
	tggataaaaatttgttattaccatatctat	1.8 1.0 2.2	6.1 4.7	2.3	4.6	7.5	2.3	5.5	8.9
	cttctttaattatgttttctatttcttttt	2.8 1.8 3.3	7.2 5.2	2.5	5.0	7.9	2.6	5.3	8.5
	gttctatttgttggagatttaaaataatta	3.0 1.7 2.0	6.2 4.4	2.6	5.3	8.0	2.7	6.1	9.1
	tcctactttaacctctaaatgtcccttatt	1.4 1.0 2.1	7.0 4.4	2.5	5.5	8.4	2.6	6.5	9.9
	tccttatgtaaaatataaatgtagcaattt	1.4 1.0 1.7	6.1 5.0	2.2	4.7	7.5	2.3	5.5	8.5
	aaaagaaccccggcgaggggagtgaaatag	2.7 1.6 3.7	8.3 5.4	3.4	6.9 11.3	3.5	9.3 12.5
	aattttcaactaatattaaaccacgttctg	3.0 1.7 2.8	6.3 4.7	2.0	4.8	8.1	2.2	5.6	9.7
	aaaggtccattaagtattactatcacagca	2.7 1.1 2.3	7.4 5.5	2.3	5.1	8.1	2.5	6.6 10.2
	agatttgcgtgatttaaaataatcatctaa	1.9 1.1 1.9	6.4 4.9	2.4	4.9	7.5	2.5	5.8	9.1
	ataggaaaagattggattaaactagatatg	2.1 1.3 2.9	6.8 4.7	2.2	5.1	8.3	2.3	5.9	9.7
	esus going up to Jerusalem too	11.9 6.0 8.9 13.2 8.8	9.5 18.0 18.5	9.4 18.1 18.7
	them, as they were able to hea 12.4 6.1 8.1 11.7 8.6	7.8 16.5 17.9	7.8 16.6 18.0
	o in Osee, I will call them my 14.8 7.5 9.0 12.0 8.5	9.0 18.5 19.3	8.9 18.8 19.3
	things are come upon thee, the	10.1 5.8 7.6 11.7 8.6	8.5 16.3 17.7	8.5 16.8 18.1
	full of darkness. If therefor	12.8 6.8 8.6 11.9 8.5	9.4 18.5 18.9	9.4 18.7 19.1
	e it: for there is no other sa 12.4 5.5 8.0 11.7 8.8	7.7 16.4 17.6	7.7 16.9 17.9
	g, Syria is confederate with E	12.1 6.3 9.4 12.8 8.6	9.8 18.6 18.9	9.8 18.6 18.9

Authors' contributions

Gilles Didier provided the initial idea, led the software development and wrote all the manuscript but the section Evaluation. Laurent Tichit collaborated on the software development, ran the tests and wrote the section Evaluation. Both authors read, edited and approved the final manuscript.


Caroline Bauzet

Time-splitting approximation of the Cauchy problem for a stochastic conservation law

Keywords: Stochastic PDE, multiplicative noise, Itô integral, time-splitting method, Young measures, entropy solution 2014 MSC: 35L60, 60H15, 35L60

Time-splitting approximation of the Cauchy problem for a stochastic conservation law

Introduction

We are interested in the Cauchy problem for a nonlinear hyperbolic scalar conservation law with a multiplicative stochastic perturbation of type:

   du + div f (u)dt = h(u)dW in ]0, T [×R d × Ω, u(ω, 0, x) = u 0 (x), ω ∈ Ω, x ∈ R d , (1)
Email address: caroline.bauzet@univ-amu.fr (Caroline Bauzet) URL: http://www.cmi.univ-mrs.fr/~caroline.bauzet/ (Caroline Bauzet)

Preprint submitted to Journal of Mathematics and Computers in SimulationDecember 8, 2014 where div is the divergence operator with respect to the space variable (which belongs to R d ), d 1, T > 0 and W = {W t , F t ; 0 ≤ t ≤ T } is a standard adapted one-dimensional continuous Brownian motion defined on the classical Wiener space (Ω, F, P ). By denoting Q =]0, T [×R d , this equation has to be understood in the following way: P-a.s. in Ω and ∀ϕ ∈ D(Q)

Q u∂ t ϕ + f (u).∇ x ϕdxdt = Q t 0 h(u)dW (s)∂ t ϕdxdt.
Note that, even in the deterministic case, a weak solution to a nonlinear scalar conservation law is not unique in general. The mathematical stake consists in introducing a selective criterion in order to identify the physical solution. In the present work we consider a stochastic version of the entropy condition proposed by S.N. Kruzhkov in the 70s, the one used in [START_REF] Bauzet | The Cauchy problem for a conservation law with a multiplicative stochastic perturbation[END_REF] and presented in Section 2.

We assume the following hypotheses:

H 1 : f : R → R d is a Lipschitz-continuous function with f (0) = 0.

H 2 : h : R → R is a Lipschitz-continuous function with h(0) = 0.

H 3 : u 0 ∈ L 2 (R d ).
H 4 : There exists M > 0 such that supph ⊂ [-M, M ].

H 5 : u 0 ∈ L ∞ (R d ) ∩ BV (R d ) 1 .
Remark 1.

1 where BV (R d ) denotes the set of integrable functions with bounded variation on R d .

2

. H 1 , H 2 and H 3 are claimed conditions from the theoretical point of view to ensure the well-posedness in the sense of [START_REF] Bauzet | The Cauchy problem for a conservation law with a multiplicative stochastic perturbation[END_REF]. Let us first mention that H 1 can be weakened by assuming that f is a locally Lipschitz continuous function. Indeed, since the solution u is bounded by a constant M 1 depending only on M and u 0 ∞ , the result holds by a truncation argument of f outside [-M 1 , M 1 ]. Secondly, since div[ f (0)] = 0, one can assume by convenience that f (0) = 0.

. H 4 and H 5 are specific conditions from the numerical analysis point of view.

These are technical assumptions to control the estimates in the forthcoming lemmas, in particular to apply Lemma 3.3. Note that H 4 is a necessary condition to keep the solution u bounded.

Former results

Only few papers have been devoted to the theoretical study of hyperbolic scalar conservation laws with a multiplicative stochastic forcing: the development of a well-posedness theory has been done in [START_REF] Chen | On nonlinear stochastic balance laws[END_REF]- [START_REF] Feng | Stochastic scalar conservation laws[END_REF] by the way of strong entropy solution, in [START_REF] Debussche | Scalar conservation laws with stochastic forcing[END_REF] by the use of kinetic formulation, and in [START_REF] Bauzet | The Cauchy problem for a conservation law with a multiplicative stochastic perturbation[END_REF]- [START_REF] Bauzet | The Dirichlet problem for a conservation law with a multiplicative stochastic perturbation[END_REF] with the notion of stochastic entropy solution. For a thorough exposition of all these papers, we refer the reader to the introduction of [START_REF] Bauzet | On a time-splitting method for a stochastic conservation law with Dirichlet boundary condition and numerical experiments[END_REF]. Concerning the numerical analysis of such stochastic problems, there is also, to our knowledge, few papers.

Let us cite the work of Holden-Risebro [START_REF] Holden | A stochastic approach to conservation laws[END_REF] where a time-discretization of the equation is proposed by the use of an operator-splitting method. They proposed a result of convergence to prove the existence of pathwise weak solutions to the Cauchy problem for (1) set in R. In the recent paper of Bauzet [START_REF] Bauzet | On a time-splitting method for a stochastic conservation law with Dirichlet boundary condition and numerical experiments[END_REF], a generalization of the work of Holden-Risebro [START_REF] Holden | A stochastic approach to conservation laws[END_REF] is proposed in a bounded domain D of R d . The author proved that the pathwise weak solution obtained in [START_REF] Holden | A stochastic approach to conservation laws[END_REF] is the unique entropy weak solution of the stochastic conservation law and that the whole sequence of approximation given by the time-splitting scheme converges strongly. are interested in a recent work in a method of handling the finite volume schemes for the approximate solution of the Cauchy problem for (1) and investigate on a space-discretization of the equation. For a class of strongly monotone numerical fluxes they established the pathwise convergence of a semi-discrete finite volume solution towards a stochastic entropy solution. Since the authors use a stochastic version of the compensated compactness approach, the study is restricted to the one-dimensional case.

Goal of the study and main result

In a recent published paper [START_REF] Bauzet | On a time-splitting method for a stochastic conservation law with Dirichlet boundary condition and numerical experiments[END_REF], a generalization of the time-splitting method introduced much earlier by Holden and Risebro [START_REF] Holden | A stochastic approach to conservation laws[END_REF] is proposed to approximate solution of the stochastic conservation law (1) set in a bounded domain D of R d and with homogeneous Dirichlet boundary condition. Precisely, the author showed that the pathwise weak limit obtained in the former study of Holden and Risebro is the unique stochastic entropy solution of (1) and that the whole sequence of approximate solutions converges strongly with respect to all its variables. Our aim in the present paper is to prove that the tools developed in [START_REF] Bauzet | On a time-splitting method for a stochastic conservation law with Dirichlet boundary condition and numerical experiments[END_REF] are sufficiently strong to be extended to an unbounded domain and allow us to complete the work of Bauzet-Vallet-Wittbold [START_REF] Bauzet | The Cauchy problem for a conservation law with a multiplicative stochastic perturbation[END_REF] by a numerical analysis using their well-posedness theory for stochastic entropy solution. The main result of the present paper which deals with the convergence of our numerical scheme is stated in the following theorem.

Theorem 1.1. Assume that hypotheses H 1 to H 5 hold. Set N ∈ N * and let ∆ = T N be the time step of the time-spliting operator scheme. Then, the associated approximate solution denoted u ∆ in the sequel and defined p.13 converges in L p loc (Ω × Q) for any finite p towards the unique stochastic entropy solution of the stochastic conservation law (1).

The paper is organized as follows. Section 2 is devoted to the presentation of the theoretical background : we recall the definition of a solution for (1) proposed in [START_REF] Bauzet | The Cauchy problem for a conservation law with a multiplicative stochastic perturbation[END_REF] and their well-posedness result. In Section 3, we present firstly the time-splitting scheme used to approximate the solution of our problem. Several preliminaries results satisfied by the time-splitting approximate solution u ∆ are then stated. The remainder of Section 3 is devoted to show the convergence of u ∆ towards the unique stochastic entropy solution of (1). To illustrate our proposal, we present in Section 4 numerical experiments around the stochastic burgers' equation in the one-dimensional case.

Notations

. E denotes the integral over Ω with respect to the probability measure P .

. Consider BV (R d ) the set of integrable functions with bounded variation on R d endowed with the norm

v BV (R d ) = v L 1 (R d ) + T V x (v), where T V x (v)
denotes the total variation of v on R d (see Evans-Gariepy [START_REF] Evans | Measure theory and fine properties of functions[END_REF]).

. Denote by N 2 w (0, T, L 2 (R d )) the set of the predictable processes of L 2 (]0, T [×Ω, L 2 (R d )) (Da Prato-Zabczyk [START_REF] Da Prato | Encyclopedia of Mathematics and its Applications[END_REF] p.94).

. Consider E the set of any C 2,1 (R) nonnegative convex approximation of the absolute-value function such that η(0) = 0 and that there exists δ > 0

such that η (x) = 1 (resp. -1) if x > δ (resp. x < δ ).
. F η denotes the entropy flux defined for any a, b ∈ R and for any smooth

entropy η ∈ E by F η (a, b) = a b η (σ -b)f (σ) dσ. Note in particular that F η is a Lipschitz-continuous function.

Existence and uniqueness result

Let us recall the definitions and the result introduced in the paper of Bauzet-Vallet-Wittbold [START_REF] Bauzet | The Cauchy problem for a conservation law with a multiplicative stochastic perturbation[END_REF]. These results are obtained under hypotheses H 1 to H 3 .

Definition 2.1. (Stochastic entropy solution)

A function u of N 2 w 0, T, L 2 (R d ) ∩ L ∞ 0, T ; L 2 Ω, L 2 (R d
) is an entropy solution of the stochastic scalar conservation law (1) with the initial condition

u 0 ∈ L 2 (R d ), if P-a.s in Ω, for any η ∈ E and for any (λ, ϕ) ∈ R×D + ([0, T [×R d ) 0 R d η(u 0 -λ)ϕ(0, x)dx + Q η(u -λ)∂ t ϕdxdt + Q F η (u, λ).∇ x ϕdxdt + T 0 R d η (u -λ)h(u)ϕdxdW (t) + 1 2 Q h 2 (u)η (u -λ)ϕdxdt.
For technical reasons, as in [START_REF] Bauzet | The Cauchy problem for a conservation law with a multiplicative stochastic perturbation[END_REF], we also need to consider a generalized notion of entropy solution. In fact, in a first step, we will only prove the convergence of the approximate solution to a measure-valued entropy solution. Then, thanks to the result of uniqueness stated in Theorem 2.3, we will be able to deduce the convergence of the approximate solution to the unique stochastic entropy solution of Problem (1).

Definition 2.2. (Measure-valued entropy solution)

A function u of N 2 w 0, T, L 2 R d × (0, 1) ∩ L ∞ 0, T ; L 2 Ω × R d × (0, 1
) is a measure-valued entropy solution of the stochastic scalar conservation law [START_REF] Bauzet | On a time-splitting method for a stochastic conservation law with Dirichlet boundary condition and numerical experiments[END_REF] with the initial condition u 0 ∈ L 2 (R d ), if P-a.s in Ω, for any η ∈ E and for any

(λ, ϕ) ∈ R × D + ([0, T [×R d ) 0 R d η(u 0 -λ)ϕ(0, x)dx + Q 1 0 η(u(., α) -λ)∂ t ϕdαdxdt + Q 1 0 F η (u(., α), λ).∇ x ϕdαdxdt + T 0 R d 1 0 η (u(., α) -λ)h(u(., α))ϕdαdxdW (t) + 1 2 Q 1 0 h 2 (u(., α))η (u(., α) -λ)ϕdαdxdt.

And the main result of [2] is

Theorem 2.3. Under assumptions H 1 to H 3 there exists a unique measurevalued entropy solution for the Problem (1) and this solution is obtained by viscous approximation. Moreover, it is the unique stochastic entropy solution in the sense of Definition 2.1.

Time-splitting method

Introduction

Our aim is to approximate Problem (1) under Assumptions H 1 to H 5 . We introduce the method proposed by Holden-Risebro in [START_REF] Holden | A stochastic approach to conservation laws[END_REF], which consists in splitting the effect of the source term. This technique allows us to construct a sequence to approximate the solution of (1). In few words, this approach is based on considering the equation in two parts, solving first a stochastic differential equation, and then using the obtained solution as an initial condition for a homogeneous hyperbolic scalar conservation law. As an extension of [START_REF] Holden | A stochastic approach to conservation laws[END_REF], we propose in this paper to generalize their estimates on the approximate sequence to the R d -case, in the idea of Chen-Ding-Karlsen [START_REF] Chen | On nonlinear stochastic balance laws[END_REF] concerning BV estimates.

Following the notations introduced in [START_REF] Holden | A stochastic approach to conservation laws[END_REF] we define here two operators for s, t ∈ [0, T ] and associated results. Let R(t, s) be the operator which takes a number u to the solution u at time t of the stochastic differential equation,

∀t ∈ [s, T ]    du(t) = h(u)dW (t) u(t = s) = u, (2)
i.e u(t

) = R(t, s)u = u + t s h(u)dW .
And S(t -s) denotes the operator which takes an initial function u(x, s) at time s to the weak entropy solution u at time t of the first-order hyperbolic equation

   u t + div f (u) = 0 in ]0, T [×R d , u(t = s) = u(x, s), (3)
i.e u(x, t) = S(t -s)u(x, s). Proof. Consider the process u defined for all t ∈ [s, T ] by u(t) = R(t, s)u(s).

Applying the Itô formula to a regular function Ψ independent of the time variable t, vanishing in [-M, M ] and increasing outside this interval, one gets, P-a.s:

Ψ(u(t)) = Ψ(u(s)) + t s Ψ t (u(σ)) =0 dσ + t s Ψ x (u(σ))h(u(σ)) =0 dW (σ) + 1 2 t s Ψ xx (u(σ))h 2 (u(σ)) =0 dσ, ∀t ∈ [s, T ]. Consider ω ∈ Ω, where Ω is a full measure subset of Ω and t ∈ [s, T ]. Thus, if u(s, ω) ∈ [-M, M ], Ψ(u(s, ω)) = 0 = Ψ(u(t, ω)) and u(t, ω) ∈ [-M, M ]. Else, Ψ(u(t, ω)) = Ψ(u(s, ω)), by injectivity of Ψ in R -[-M, M ], u(t, ω) = u(s, ω) and R(t, s) = I d . Lemma 3.2. Consider s ∈ [0, T ], v 0 ∈ L 1 (Ω×R d )∩L 2 (Ω×R d ) a F s -measurable process such that E[T V x (v 0 )] < ∞. Define the process v for all t ∈ [s, T ] by v(t) = R(s, t)v 0 . Then for all t ∈ [s, T ] E[T V x (v(t))] E[T V x (v 0 )].
Remark 2. Let us mention that using the lower semi-continuity property and the positivity of the total variation

T V x on L 1 (R d ), for all v in L 1 (Ω × R d ), E[T V x (v)] has a sense. Proof. Consider s ∈ [0, T ] and let v 0 ∈ L 1 (Ω × R d ) ∩ L 2 (Ω × R d ) be a F s - measurable process with E[T V x (v 0 )] < ∞. Define for all t ∈ [s, T ] v(t) =
R(s, t)v 0 and consider η δ ∈ E. Applying Itô's formula with the process v and the function η δ , one gets by taking the integral over R d and the expectation, for

every t ∈ [s, T ] E R d η δ (v(t))dx = E R d η δ (v 0 )dx + 1 2 E R d t s η δ (v(t))h 2 (v)dσdx.
Passing to the limit on δ to 0 to get for every t ∈ [s, T ]

155 E v(t) L 1 (R d ) = E v 0 L 1 (R d ) .
Following the idea of Chen-Ding-Karlsen [START_REF] Chen | On nonlinear stochastic balance laws[END_REF] we consider v 0 a smooth approximation of v 0 such that

v 0 → v 0 in L p (Ω × R d ), p = 1, 2 (4)
E R d |∇v 0 | 2 dx < ∞, for each fixed (5) E[T V x (v 0 )] E[T V x (v 0 )]. (6)
The proof of these results relies on approximation of BV-function in the deterministic setting, we refer the reader to Evans-Gariepy [START_REF] Evans | Measure theory and fine properties of functions[END_REF] p.172.

Let us define for all t in [s, T ] v (t) = R(s, t)v 0 . Now we need estimate on ∂ xi v 160 in order to obtain BV estimate for v. Applying Itô's formula to the process

d(v -v) = [h(v ) -h(v)
]dW and the function η δ , taking the integral over R d and the expectation, we obtain for every t ∈

[s, T ] E R d η δ (v -v)(t)dx = E R d η δ (v 0 -v 0 )dx + 1 2 E R d t s η δ (v -v)[h(v ) -h(v)] 2 dσdx.
Passing to the limit on δ to 0 to get for every t ∈ [s, T ]

E (v -v)(t) L 1 (R d ) = E v 0 -v 0 L 1 (R d ) .
Thus, for every t

∈ [s, T ], v (t) → v(t) in L 1 (Ω × R d ).
As P-a.s and for all t

∈ [0, T ], v (t) = v (0) + t 0 h(v )dW in W 1,2 (R d ), using
the linear-continuity of the derivation operator

∂ xi : W 1,2 (R d ) → L 2 (R d ) for all
i ∈ {1, . . . , d} and the chain-rule derivation formula, we get for all i ∈ {1, . . . , d}

∂ xi v (0) = ∂ xi v 0 and: ∂ xi v (t) = ∂ xi v (0) + ∂ xi t 0 h(v )dW = ∂ xi v (0) + t 0 h (v )∂ xi v dW, in L 2 (R d ).
Applying Itô's formula with such a process and the function η δ to get that, after taking the integral over R d , the expectation and passing to the limit on δ, for

all t ∈ [s, T ] E R d |∂ xi v |dx = E R d |∂ xi v 0 |dx < ∞. (7)
Thus, for all t ∈ [s, T ] and P-a.s,

v (t) ∈ BV (R d ). As for all t ∈ [s, T ] v (t) → v(t) in L 1 (Ω × R d ),
for a subsequence denoted in the same way, for all t ∈ [s, T ] and P-a.s, v (t) → v(t) in L 1 (R d ). According to Malek-Necas-Otto-Rokyta-Ruzicka [START_REF] Málek | Weak and measure-valued solutions to evolutionary PDEs[END_REF] p.36, we thus have for all t ∈ [s, T ] and P-a.s

T V x (v(t)) lim inf T V x (v (t)).
Consequently, taking the expectation thanks to Remark 2, using Fatou's Lemma, ( 7) then ( 6), one gets that for every t ∈ [s, T ]

E[T V x (v(t))] lim inf E[T V x (v (t))] = lim inf E[T V x (v 0 )] E[T V x (v 0 )],
and the result holds.

Lemma 3.3. Let u 0 ∈ L ∞ (R d ) ∩ BV (R d
), t > 0, and u(t) = S(t)u 0 . Then: there exists a constant C > 0 such that for almost every t > 0,

i) u(t) L ∞ (R d ) u 0 L ∞ (R d ) , ii) R d |u(t 1 , x) -u(t 2 , x)|dx CT V x (u 0 )|t 1 -t 2 |, for all t 1 , t 2 ∈ [0, T ],
iii) T V x (u(t)) T V x (u 0 ).

Proof. These results are classical ones and the proof would be outside the scope of the present work, we refer the reader to Malek-Necas-Otto-Rokyta-Ruzicka [START_REF] Málek | Weak and measure-valued solutions to evolutionary PDEs[END_REF] p.68.

Construction of the approximate solution

Let us now explain the construction of the approximate solution as introduced in Holden-Risebro [START_REF] Holden | A stochastic approach to conservation laws[END_REF]. We consider a positive integer N , denote by ∆ = T N and split the time interval by denoting t n = n∆, n ∈ {0, . . . , N } each point of the time discretization. For each step of discretization ∆, we consider the function defined for all t ∈ [0, T ] and

x ∈ R d u ∆ (t, x) =    u n (x) if t = t n R(t, t n )u n (x) if t ∈]t n , t n+1 [,
where the sequence (u n ) n∈N is defined by

   u 0 (x) = u 0 (x) u n+1 (x) = S(∆)R(t n+1 , t n )u n (x).
Notations: ∀n ∈ {0, . . . , N -1}, t ∈ [0, T ] and x ∈ R d :

.

u n+1 -(x) := R(t n+1 , t n )u n (x). . u(t, x) := S(t -t n )R(t n+1 , t n )u n (x) = S(t -t n )u n+1 -(x).
Proposition 1. (A priori estimate) There exists a constant M 1 independent of 195 n and ∆ such that P-a.s in Ω and for all t ∈ [0, T ]

u ∆ (t) L ∞ (R d ) M 1 := max(M, u 0 L ∞ (R d ) ).
Proof. Let us mention that the construction of u ∆ is done by induction, so the proofs of the associated results also rely on inductive reasoning. Consider n ∈ {0, . . . , N -1}, and u n+1 = S(∆)u n+1 -. Thanks to Lemma 3.3 i),

u n+1 L ∞ (R d ) u n+1 - L ∞ (R d ) , P -a.s.
Moreover, thanks to Lemma 3.1, P-a.s and ∀t ∈

[t n , t n+1 ] 200 R(t, t n )u n L ∞ (R d ) max(M, u n L ∞ (R d ) )
and particularly for t = t n+1 , one has P-a.s

u n+1 - L ∞ (R d ) = R(t n+1 , t n )u n L ∞ (R d ) max(M, u n L ∞ (R d ) ) max(M, u 0 L ∞ (R d ) ) := M 1 .
Notice that the construction of u ∆ is countable, so P -a.s, for all t ∈ [0, T ] and all possible discretization parameter N ∈ N * :

u ∆ (t, .) L ∞ (R d ) M 1 ,
where M 1 does not depend on ∆ and the result holds.

Proposition 2. E[T V x (u i )] T V x (u 0 ), for every i ∈ {0, . . . , N }. 205 Proof. Consider i ∈ {0, . . . , N -1}. As u i = S(∆)u i -, and
u i -= R(t i , t i-1 )u i-1 , using Lemma 3.3 then Lemma 3.2 one gets E[T V x (u i )] E[T V x (u i -)] E[T V x (u i-1 )],
a reasoning by induction gives us the result.

210 E R d |u ∆ (t n+1 , x) -u ∆ (t, x)|.|φ(x)|dx C∆T V x (u 0 ) + C √ ∆,
where C and C are independent of ∆.

Proof. Let n ∈ {1, . . . , N } and consider t ∈ [t n , t n+1 [. For all x ∈ R d , u ∆ (t, x) = R(t, t n )u n (x) = u n (x) + t tn h(u ∆ (σ))dW (σ) u ∆ (t n+1 , x) = u n+1 (x).
Thus,

E R d |u ∆ (t n+1 , x) -u ∆ (t, x)|.|φ(x)|dx E R d |u n+1 (x) -u n (x)|.|φ(x)|dx +E R d | t tn h(u ∆ (σ))dW (σ)|.|φ(x)|dx
Thanks to Lemma 3.3 ii) and Proposition 2 one shows that

E R d |u n+1 (x) -u n (x)|dx E R d |u n+1 (x) -u n+1 -(x)| + |u n+1 -(x) -u n (x)|.|φ(x)|dx = E R d |S(∆)u n+1 -(x) -u n+1 -(x)|.|φ(x)| + |R(t n+1 , t n )u n (x) -u n (x)|.|φ(x)|dx C∆.E[T V x (u n+1 -)] + E R d | tn+1 tn h(u ∆ (s, x))dW (s)|.|φ(x)|dx C∆.T V x (u 0 ) + E R d | tn+1 tn h(u ∆ (s, x))dW (s)|.|φ(x)|dx.
Consider K a compact subset of R d such that suppφ ⊂ K and notice that 215 |t n -t| ∆. Thus by using Cauchy-Schwarz inequality on Ω × K and then Itô isometry, one gets

E R d | t tn h(u ∆ (s, x))dW (s)|.|φ(x)|dx φ L ∞ (R d ) E K | t tn h(u ∆ (s, x))dW (s)|dx c E K | t tn h(u ∆ (s, x))dW (s)| 2 dx 1 2 = c E K t tn h 2 (u ∆ (s, x))dsdx 1 2 c √ ∆. Similarly E R d | tn+1 tn h(u ∆ (s, x)dW (s)|.|φ(x)|dx c
√ ∆, and so C = 2 c.

Entropy formulation

We follow the idea of Peyroutet [START_REF] Peyroutet | Etude d'une méthode de splitting pour des lois de conservation scalaires avec terme de source[END_REF] for introducing the entropy formulation 220 satisfied by the approximate solution. In order to do this, consider

u(t, x) = S(t -t n )u n+1 -(x), t ∈ [t n , t n + 1].
As a weak entropy solution of a conservation law, u satisfies the following condition, for any η ∈ E and any

(k, ϕ) ∈ R × D + ([0, T ] × R d ) : R d η( u(t n ) -k)ϕ(t n )dx - R d η( u(t n+1 ) -k)ϕ(t n+1 )dx + R d tn+1 tn η( u -k)∂ t ϕ + F η ( u, k)∇ϕdtdx 0. Consider (k, ϕ, η) ∈ R × D + ([0, T ] × R d ) × E, K a compact set of R d such that suppϕ(t, .) ⊂ K and denote for s ∈ [t n , t n+1 ], v(s) := R(s, t n )u n the solution in 225 [t n , t n+1 ] of the stochastic differential equation    dv = h(v)dW v(t = t n ) = u n .
Applying the Itô formula to the process v and the regular function

Ψ(t, λ) = η(λ -k)
, one gets P -a.s:

η(v(t n+1 ) -k) = η(v(t n ) -k) + tn+1 tn η (v(t) -k)h(v(t))dW (t) + 1 2 tn+1 tn η (v(t) -k)h 2 (v(t))dt. Remark that v(t) = u ∆ (t) for all t ∈ [t n , t n+1 [ and v(t n+1 ) = u(t n ), in this way, P -a.s: 230 R d η( u(t n , x) -k)ϕ(t n , x)dx - R d η(u ∆ (t n , x) -k)ϕ(t n , x)dx = R d tn+1 tn η (u ∆ (t, x) -k)h(u ∆ (t, x))dW (t)ϕ(t n , x)dx + 1 2 R d tn+1 tn η (u ∆ (t, x) -k)h 2 (u ∆ (t, x))dtϕ(t n , x)dx.
Moreover,

R d η( u(t n+1 , x) -k)ϕ(t n+1 , x)dx = R d η(u ∆ (t n+1 , x) -k)ϕ(t n+1 , x)dx.
Thus one first gets, for any P-measurable set

A E R d η(u ∆ (t n , x) -k)ϕ(t n )dx1 A - R d η(u ∆ (t n+1 , x) -k)ϕ(t n+1 , x)dx1 A +E R d tn+1 tn η (u ∆ (t, x) -k)h(u ∆ (t, x))dW (t)ϕ(t n , x)dx1 A + 1 2 E R d tn+1 tn η (u ∆ (t, x) -k)h 2 (u ∆ (t, x))dtϕ(t n , x)dx1 A +E R d tn+1 tn η( u(t, x) -k)ϕ t (t, x) + F η ( u(t, x), k)∇ϕ(t, x)dtdx1 A 0.
We propose to approximate E(

R d tn+1 tn η( u(t, x) -k)ϕ t (t, x)dtdx1 A ) by E( R d tn+1 tn η(u n+1 -k)ϕ t (t, x)dtdx1 A )
making an error only of order ∆ 2 . Indeed, thanks to Lemma 3.3 ii) and Proposition 2 235 E(

R d tn+1 tn η( u(t) -k)ϕ t dtdx - R d tn+1 tn η(u n+1 -k)ϕ t dtdx1 A ) CE R d tn+1 tn |η( u(t) -k) -η(u n+1 -k)|.|ϕ t |dtdx C ϕ t ∞ E K tn+1 tn | u(t) -u n+1 |dtdx. C tn+1 tn E[T V x (u n+1 -)]|t -t n+1 |dt C∆ 2 T V x (u 0 ).
In the same way, one shows by using the Lipschitz-continuity of F η (., k) that

E( R d tn+1 tn F η (u n+1 (x), k)∇ϕdtdx1 A ) is an approximation of E( R d tn+1 tn
F η ( u(t, x), k)∇ϕ(t, x)dtdx1 A ) with an error of order ∆ 2 .

Finally we obtain by summing over n

E N -1 n=0 R d tn+1 tn η(u ∆ (t n+1 , x) -k)ϕ t (t, x)dtdx1 A +E N -1 n=0 R d tn+1 tn F η (u ∆ (t n+1 , x), k)∇ϕ(t, x)dtdx1 A +E N -1 n=0 R d tn+1 tn η (u ∆ (t, x) -k)h(u ∆ (t, x))dW (t)ϕ(t n , x)dx1 A + 1 2 E N -1 n=0 R d tn+1 tn η (u ∆ (t, x) -k)h 2 (u ∆ (t, x))dtϕ(t n , x)dx1 A + mes(A) R d η(u 0 (x) -k)ϕ(0, x)dx -E R d η(u ∆ (T, x) -k)ϕ(T, x)dx1 A
-∆, where ∆ → 0 when ∆ → 0.

Convergence of the approximate solution 240

Consider A a P -measurable set, (k, ϕ, η) ∈ R × D + ([0, T ] × R d ) × E and denote by K a compact set of R d such that suppϕ(t, .) ⊂ K. Our aim is to pass to the limit in:

E N -1 n=0 R d tn+1 tn η (u ∆ (t, x) -k)h(u ∆ (t, x))dW (t)ϕ(t n , x)dx1 A := I ∆ 1 + 1 2 E N -1 n=0 R d tn+1 tn η (u ∆ (t, x) -k)h 2 (u ∆ (t, x))dtϕ(t n , x)dx1 A := I ∆ 2 +E N -1 n=0 R d tn+1 tn η(u ∆ (t n+1 , x) -k)ϕ t (t, x)dtdx1 A := I ∆ 3 +E N -1 n=0 R d tn+1 tn F η (u ∆ (t n+1 , x), k)∇ϕ(t, x)dtdx1 A := I ∆ 4 +mes(A) R d η(u 0 (x) -k)ϕ(0, x)dx -∆, (8)
Due to the random variable, even if strong estimates with respect to variables t and x hold, we are not able to use classical results of compactness. The one given by the concept of Young measures is appropriate here and the technique is based on the notion of narrow convergence of Young measures (or entropy processes). We refer to Eymard-Gallouët-Herbin [START_REF] Eymard | Existence and uniqueness of the entropy solution to a nonlinear hyperbolic equation[END_REF] and Panov [START_REF] Panov | On measure-valued solutions of the Cauchy problem for a first-order quasilinear equation[END_REF]. Since (u ∆ ) is a bounded sequence in L ∞ (Q × Ω), the associated Young measure sequence (u ∆ ) converges (up to a subsequence still indexed in the same way) to a Young

250 measure denoted u ∈ L ∞ (Q × Ω×]0, 1[).
Furthermore, according to Eymard-Gallouët-Herbin [START_REF] Eymard | Existence and uniqueness of the entropy solution to a nonlinear hyperbolic equation[END_REF], for any Carathéodory function Ψ such that Ψ(., u ∆ ) is uniformly integrable:

E Q Ψ(u ∆ (t, x))dtdx → E Q 1 0 Ψ(u(t, x, α))dαdtdx when ∆ → 0.
Let us analyze separately terms of (8).

.

I ∆ 1 → E R d T 0 1 0 η (u(α) -k)h(u(., α))dαϕdW (t)dx1 A := I 1 . 255 |I ∆ 1 -I 1 | = E N -1 n=0 R d tn+1 tn η (u ∆ -k)h(u ∆ )[ϕ(t n ) -ϕ(t)]dW (t)dx1 A +E R d T 0 η (u ∆ -k)h(u ∆ )- 1 0 η (u(., α) -k)h(u(., α))dα ϕ(t)dW (t)dx1 A := |I ∆ 1,1 + I ∆ 1,2 |.
Using Cauchy-Schwarz inequality on Ω × K and Itô isometry one gets

|I ∆ 1,1 | = E N -1 n=0 K tn+1 tn η (u ∆ -k)h(u ∆ )[ϕ(t n ) -ϕ(t)]dW (t)dx1 A C N -1 n=0 E K tn+1 tn η (u ∆ -k)h(u ∆ )[ϕ(t n ) -ϕ(t)]dW (t) 2 dx 1 2 = C N -1 n=0 E K tn+1 tn η (u ∆ -k)h(u ∆ )[ϕ(t n ) -ϕ(t)] 2 dtdx 1 2 C N -1 n=0 E tn+1 tn mes(K) × ∆ 2 dt 1 2 C N -1 n=0 ∆ 3 2 = C √ ∆ → 0 Let us show that I ∆ 1,2 → 0. Denote v ∆ = η (u ∆ -k)h(u ∆ )ϕ. Thanks to Propo- sition 1, v ∆ is bounded in L 2 (Q × Ω) and there exists v ∈ L 2 (Q × Ω) such that v ∆
v in the same space. Moreover, Ψ : (t, x, ω, λ) → η (λ -k)h(λ)ϕ(t, x),

(t, x, ω, λ) ∈ Q × Ω × R is a Carathéodory function and Ψ(., u ∆ ) is uniformly integrable as it is bounded in L 2 (Q×Ω). By identification, v = 1 0 Ψ(u(., α))dα. Furthermore, for all t ∈ [0, T ], I t : L 2 (Q × Ω) → L 2 (R d × Ω) u → t 0 u(t, x, ω)dW (t)
is a linear continuous function, and so it is a weakly continuous function from Hence u is a measure-valued entropy solution in the sense of Definition 2.2.

L 2 (Q × Ω) to L 2 (R d × Ω). E R d T 0 η (u ∆ -k)h(u ∆ )ϕdW (t)dx1 A → E R d T 0 1 0 η (u(., α) -k)h(u(., α))dαϕdW (t)dx1 A and |I ∆ 1,2 | → 0. . I ∆ 2 → 1 2 E Q 1 0 η (u(., α) -k)h 2 (u(., α))dαϕdtdx1 A := I 2 . |I ∆ 2 -I 2 | = 1 2 E N -1 n=0 R d tn+1 tn η (u ∆ -k)h 2 (u ∆ )[ϕ(t n ) -ϕ(t)]dtdx1 A +E Q η (u ∆ -k)h 2 (u ∆ )ϕ(t)dtdx1 A -E Q 1 0 η (u(., α) -k)h 2 (u(., α))dαϕ(t)dtdx1 A := 1 2 |I ∆ 2,1 + I ∆ 2,2 |. |I ∆ 2,1 | E N -1 n=0 K tn+1 tn η (u ∆ -k)h 2 (u ∆ )[ϕ(t n ) -ϕ(t)] dtdx C N -1 n=0 ∆ 2 → 0. Note that Ψ(t, x, ω, λ) = η (λ -k)h 2 (λ)ϕ(t,
Thanks to Theorem 2.3, u is the unique stochastic entropy solution in the sense of Definition 2.1 and we denote it by u. Hence, all the sequence of approximate solution u ∆ converges strongly to u in L 1 loc (Ω × Q). In addition, since u ∆ is bounded in L ∞ (Ω × Q), all the sequence converges strongly in L p loc (Ω × Q) for any finite p and the proof of Theorem 1.1 is complete. The algorithm of discretization is the following one: with an Euler-Maruyama method, we solve the stochastic differential equation ( 2) and, for solving the conservation law (3), we use a Godunov scheme. We implement simulations with the following initial condition:

u 0 (x) =    1 2 if x < 0 0 else. (9)
To illustrate our proposal, we give a simulation of the solution in the deterministic case (i.e. when λ = 0) and for various values of the noise (respectively for λ equal to 0.1, 0.3 and 0.8). We get the following graphics in the (x, t) plane when x varies between -1 and 1, with ∆ x = 0.005 and ∆ t = ∆x 6 .

Lemma 3 . 1 .

 31 Consider s ∈ [0, T ]. Then P-a.s in Ω and for all t ∈ [s, T ], R(t, s) will take [-M, M ] into itself and be the identity outside this interval, where M > 0 is defined in H 4 .

Lemma 3 . 4 .

 34 Let n ∈ {1, . . . , N } and consider t ∈ [t n , t n+1 [. Then for any φ ∈ D(R d ):

270 1 0Fηη 1 0

 11 Using the same techniques we show the following convergences. (., α) -k)dαϕ t dtdx1 A := I 3 .Q η (u(., α), k)dα∇ϕdtdx1 A := I 4 . Finally, for all (k, ϕ, η) ∈ R × D + ([0, T ] × R d ) × E and any P -measurable set A: (u(α) -k)h(u(., α))dαϕdW (t)dx1 A (u(., α) -k)h 2 (u(., α))dαϕdtdx1 A +E Q [η(u(., α) -k)ϕ t + F η (u(., α), k)∇ϕ]dαdtdx1 A + mes(A) R dη(u 0 (x) -k)ϕ(0, x)dx 0.

280 4 .Remark 3 .

 43 Numerical experimentsWe propose here an application of this splitting method to the stochastic burgers' equation in the one-dimensional case:du + f (u) x dt = λh(u)dw in Ω×]0, 1[×R,where λ ∈ R is a parameter, f (u) = u 2 and h : R → R is defined byh(x) = (x + 1)(1 -x) if -1 < x < 1 0 else.As the flux function f is locally Lipschitz-continuous in R and as we work with solution explicitly bounded by constant independent of f , following Remark 1 we are in the framework presented in the previous section.

Figure 1 :

 1 Figure 1: Determinist case : λ = 0

Figure 2 : 1 25Figure 3 :

 213 Figure 2: Stochastic case : λ = 0.1

Figure 4 :

 4 Figure 4: Stochastic case : λ = 0.8

  x)1 A is a Carathéodory function such that Ψ(., u ∆ ) is uniformly integrable, thus I ∆ 2,2 → 0 and the result holds.

In this manner, Remark 4. Note that we conserve in the stochastic case the propagation of a single choc wave and that the stochastic perturbation seems to act only on the slope coefficient of such a choc. These simulations have been implemented with the free software Scilab.