Franck Sueur

On the inviscid limit for the compressible Navier-Stokes system in an impermeable bounded domain

In this paper we investigate the issue of the inviscid limit for the compressible Navier-Stokes system in an impermeable fixed bounded domain. We consider two kinds of boundary conditions.

 obtained by Kato in the homogeneous incompressible case. Kato proved that if the energy dissipation rate of the viscous flow in a boundary layer of width proportional to the viscosity vanishes then the solutions of the incompressible Navier-Stokes equations converge to some solutions of the incompressible Euler equations in the energy space. We provide here a natural extension of this result to the compressible case.

The other case is the Navier condition which encodes that the fluid slips with some friction on the boundary. In this case we show that the convergence to the Euler equations holds true in the energy space, as least when the friction is not too large.

.

Introduction

In this paper we investigate the issue of the inviscid limit for the compressible Navier-Stokes system in a fixed bounded domain. Formally dropping the viscous terms the system degenerates into the compressible Euler system. Yet the rigorous justification is intricate because of the appearance of boundary layers, particularly in the case of an impermeable boundary, the so-called characteristic case.

A longstanding approach follows the seminal work of Prandtl which predicts, in the case of the homogeneous incompressible Navier-Stokes system in an impermeable bounded domain with no-slip condition, a sharp variation of the fluid velocity in a boundary strip of width proportional to the square of the viscosity factor. Yet this approach seems to fail to justify the inviscid limit in general, see [START_REF] Gérard-Varet | On the ill-posedness of the Prandtl equation[END_REF][START_REF] Guo | A note on the Prandtl boundary layers[END_REF] and the references therein.

On the other hand Kato proved in [START_REF] Kato | Remarks on zero viscosity limit for nonstationary Navier-Stokes flows with boundary[END_REF] the following conditional result: if the energy dissipation rate of the viscous flow in a boundary layer of width proportional to the viscosity vanishes then the solutions of the incompressible Navier-Stokes equations converge to some solutions of the incompressible Euler equations in the energy space. This width is much smaller than the one given by Prandtl's theory, what seems to indicate that one has to go beyond Prandtl's description to understand the inviscid limit.

As mentioned in the survey [START_REF]Boundary layer theory and the zero-viscosity limit of the Navier-Stokes equation[END_REF] by E, not much is known about the compressible case. Nevertheless let us mention the paper [START_REF] Xin | Zero-viscosity limit of the linearized Navier-Stokes equations for a compressible viscous fluid in the half-plane[END_REF] which tackles the linearized Navier-Stokes equations for a compressible viscous fluid in the half-plane, the paper [START_REF] Rousset | Characteristic boundary layers in real vanishing viscosity limits[END_REF] which deals with the one-dimensional case and the paper [START_REF] Guès | Existence and stability of noncharacteristic boundary layers for the compressible Navier-Stokes and viscous MHD equations[END_REF] which treats the noncharacteristic case.

The first main result of this paper is an extension of Kato's result to the compressible case. The second result deals with the case where a Navier condition is prescribed on the boundary. This condition encodes that the fluid slips with some friction on the boundary. In this case we prove that if the friction is not too large with respect to the viscosity then the solutions of the compressible Navier-Stokes equations converge to some solutions of the compressible Euler equations in the energy space in the inviscid limit. This extends some earlier results obtained by [START_REF] Bardos | The incompressible Euler limit of the Boltzmann equation with accommodation boundary condition[END_REF][START_REF] Iftimie | Inviscid limits for the Navier-Stokes equations with Navier friction boundary conditions[END_REF][START_REF] Paddick | Stability and instability of Navier boundary layers[END_REF][START_REF] Wang | Vanishing viscous limits for 3D Navier-Stokes equations with a Navier-slip boundary conditions[END_REF] in the incompressible case.

Let us now say a few words about the technics employed in this paper. In both cases we start with the observation that the results obtained in the incompressible case hinted above (i.e. [START_REF] Kato | Remarks on zero viscosity limit for nonstationary Navier-Stokes flows with boundary[END_REF][START_REF] Iftimie | Inviscid limits for the Navier-Stokes equations with Navier friction boundary conditions[END_REF][START_REF] Paddick | Stability and instability of Navier boundary layers[END_REF][START_REF] Bardos | The incompressible Euler limit of the Boltzmann equation with accommodation boundary condition[END_REF][START_REF] Wang | Vanishing viscous limits for 3D Navier-Stokes equations with a Navier-slip boundary conditions[END_REF]) use a strategy somehow related to the issue of weak-strong uniqueness, where one compares two solutions of the same equation, only one of which being smooth. In the results [START_REF] Kato | Remarks on zero viscosity limit for nonstationary Navier-Stokes flows with boundary[END_REF][START_REF] Iftimie | Inviscid limits for the Navier-Stokes equations with Navier friction boundary conditions[END_REF][START_REF] Paddick | Stability and instability of Navier boundary layers[END_REF][START_REF] Bardos | The incompressible Euler limit of the Boltzmann equation with accommodation boundary condition[END_REF][START_REF] Wang | Vanishing viscous limits for 3D Navier-Stokes equations with a Navier-slip boundary conditions[END_REF] there is also a comparison between a weak and a strong solution but the word "solution" does not not refer to the same equation. Indeed they consider a smooth solution of the Euler equations and a weak solution of the Navier-Stokes equations. Here "weak solution" refers to the solution constructed by Leray in [START_REF] Leray | Sur le mouvement d'un liquide visqueux emplissant l'espace[END_REF][START_REF] Leray | Étude de diverses équations intégrales non linéaires et de quelques problèmes de l'hydrodynamique[END_REF], whereas local in time existence and uniqueness of classical solutions of the Euler equations is known since the work [START_REF] Wolibner | Un théorème sur l'existence du mouvement plan d'un fluide parfait[END_REF] of Wolibner. One may wish to apply the weak formulation of the Navier-Stokes equations with the solution of the Euler equations as a test function. However, in the case of the no-slip condition, the Euler solution does not satisfy all the boundary condition required to be an admissible test function. In order to overcome this difficulty Kato introduced a corrector which, added to the Euler solution, provided a smooth test function which satisfies the no-slip condition and yet quite close to the Euler solution. This corrector is referred to as a "fake" layer, as there is no reason that it describes what really happens in the boundary's neighbourhood. Then a few standard manipulations provide an estimate of the difference between the Navier-Stokes and the Euler solutions in the energy space.

In the sequel we adapt this strategy to the compressible case. In this setting the existence of global weak solutions of the Navier-Stokes equations is known since the pioneering work [START_REF] Lions | Mathematical topics in fluid mechanics[END_REF] of Lions, later improved by Feireisl, Novotný and Petzeltová in [START_REF] Feireisl | On the existence of globally defined weak solutions to the Navier-Stokes equations[END_REF], see also [START_REF] Feireisl | Dynamics of viscous compressible fluids[END_REF][START_REF] Feireisl | Singular limits in thermodynamics of viscous fluids[END_REF], for various boundary conditions. On the other hand the local in time existence of strong solutions of the compressible Euler equations is well-known since the works [START_REF] Agemi | The initial-boundary value problem for inviscid barotropic fluid motion[END_REF][START_REF] Beirão | On the barotropic motion of compressible perfect fluids[END_REF][START_REF] Ebin | The initial-boundary value problem for subsonic fluid motion[END_REF][START_REF] Ebin | Motion of slightly compressible fluids in a bounded domain[END_REF][START_REF] Schochet | The compressible Euler equations in a bounded domain: existence of solutions and the incompressible limit[END_REF]. Here, we will also get inspired by some recent breakthroughs in the issue of weak-strong uniqueness of the compressible Navier-Stokes equations, in particular by using some relative energy estimates recently proved by Feireisl, Ja Jin and Novotný in [START_REF] Feireisl | Relative entropies, suitable weak solutions, and weak-strong uniqueness for the compressible Navier-Stokes system[END_REF]. This result is somehow reminiscent of the pioneering papers [START_REF] Dafermos | The second law of thermodynamics and stability[END_REF][START_REF] Diperna | Uniqueness of solutions to hyperbolic conservation laws[END_REF][START_REF] Yau | Relative entropy and hydrodynamics of Ginzburg-Landau models[END_REF]. Let us also refer to the recent works [START_REF] Gallay | Stability and interaction of vortices in two-dimensional viscous flows[END_REF][START_REF] Saint-Raymond | Hydrodynamic limits: some improvements of the relative entropy method[END_REF][START_REF] Vasseur | Recent results on hydrodynamic limits[END_REF] and the references therein. Unlike the energy method used in the incompressible case this will provide a non-symmetric "measure" of the difference between the Euler and the Navier-Stokes solutions. Yet, as in the weak formulations, the relative energy estimates involve some test functions which satisfy some boundary conditions; and as in the incompressible case the no-slip condition is more intricate than the Navier condition as the test functions also have to satisfy the no-slip conditions, which are not satisfied by the Euler solution. We will therefore adapt, in this case, Kato's corrector construction in order to fit with the compressible setting.

The compressible Navier-Stokes system

In this paper we consider the compressible Navier-Stokes system:

∂ t ρ + div(ρu) = 0, (1)
∂ t (ρu) + div(ρu ⊗ u) + ∇ x p(ρ) = ε div S(∇ x u), (2)
where

S(∇ x u) := µ ∇ x u + (∇ x u) T ) - 2 3 (div u) Id + η(div u) Id, (3)
in a bounded regular domain Ω ⊂ R 3 .

Above, the unknowns are the fluid density ρ(t, x), defined on [0, +∞)×Ω with values in [0, +∞) and the fluid velocity u(t, x), defined on [0, +∞) × Ω with values in R 3 , whereas µ > 0 and η 0 are two viscosity coefficients, and ε > 0 is a scaling factor. In (3) the notation ∇ x u stands for the Jacobian matrix of the vector field u and (∇ x u) T denotes its transpose. Let us stress that the lower bounds on µ and η entail that the tensor product

S(∇ x u) : ∇ x u = 1 i,j 3 µ 2 (∂ i u j + ∂ j u i ) 2 + (η - 2 3 µ)| div u| 2 (4)
is a positively definite quadratic form with respect to (∂ i u j ) 1 i,j 3 .

We assume that there exists γ > 3 2 such that the pressure p(ρ) is the following function of the density

p(ρ) = ρ γ . (5)
Observe that this class of pressure laws includes in particular the case of a monoatomic gas for which the adiabiatic constant γ is 5 3 . We prescribe the initial conditions:

ρ| t=0 = ρ 0 , (ρu)| t=0 = ρ 0 u 0 .
In this setting the existence of global weak solutions is now well understood thanks to the pioneering work [START_REF] Lions | Mathematical topics in fluid mechanics[END_REF] of Lions, later improved by Feireisl, Novotný and Petzeltová in [START_REF] Feireisl | On the existence of globally defined weak solutions to the Navier-Stokes equations[END_REF], see also [START_REF] Feireisl | Dynamics of viscous compressible fluids[END_REF][START_REF] Feireisl | Singular limits in thermodynamics of viscous fluids[END_REF], for various boundary conditions.

In this paper we are interested in the limit ε → 0 which is quite sensitive to the boundary conditions prescribed on the boundary ∂Ω. In the sequel we consider two kinds of boundary conditions.

No-slip conditions

In this section we prescribe on the boundary ∂Ω of the fluid domain the following no-slip condition:

u| ∂Ω = 0. ( 6
)
Let us recall that we mean by weak solution in this case.

Definition 1. Let be given some initial data (ρ 0 , u 0 ) such that ρ 0 0,

ρ 0 ∈ L γ (Ω), ρ 0 u 2 0 ∈ L 1 (Ω). Let q 0 := ρ 0 u 0 which is in L 2γ γ+1
(Ω) and let T > 0. We say that (ρ, u) is a finite energy weak solution of the compressible Navier-Stokes system on [0, T ] associated to the initial data (ρ 0 , u 0 ) if

• ρ ∈ C w ([0, T ]; L γ (Ω)), ρu ∈ C w ([0, T ]; L 2γ γ+1 (Ω)), u ∈ L 2 (0, T ; H 1 0 (Ω)), ρu 2 ∈ C w ([0, T ]; L 1 (Ω)), • the identity Ω ρ(T, •)φ(T, •)dx - Ω ρ 0 φ(0, •)dx = T 0 Ω (ρ∂ t φ + ρu • ∇ x φ)dxdt holds for any φ ∈ C ∞ c ([0, T ] × Ω; R), • the identity Ω ρ(T, •)u(T, •) • φ(T, •)dx - Ω q 0 • φ(0, •)dx = T 0 Ω ρu • ∂ t φ + ρu ⊗ u : ∇ x φ + p(ρ) div φ -εS(∇ x u) : ∇ x φ dxdt holds for any φ ∈ C ∞ c ([0, T ] × Ω; R 3 ), • the energy inequality: E(ρ(τ, •), u(τ, •)) + ε τ 0 Ω S(∇ x u) : ∇ x u dxdt E(ρ 0 , u 0 ) ( 7
)
holds true for almost every τ ∈ [0, T ], where

E(ρ, u) := Ω E(ρ, u)dx, with E(ρ, u) := 1 2 ρ|u| 2 + H(ρ) and H(ρ) := ρ γ γ -1 . ( 8
)
Let us stress that the two terms in the left hand side of (7) are nonnegative. In particular it follows from (4) that there exists a constant C 0 > 0 such that for any u ∈ H 1 (Ω),

Ω S(∇ x u) : ∇ x u dx C 0 Ω |∇ x u| 2 dx. (9)
Let us now state the result of global existence of weak solutions hinted above.

Theorem 1 ([33], [START_REF] Feireisl | On the existence of globally defined weak solutions to the Navier-Stokes equations[END_REF]). Let be given some initial data (ρ 0 , u 0 ) such that ρ 0

0, ρ 0 ∈ L γ (Ω), ρ 0 u 2 0 ∈ L 1 (Ω). Let T > 0.
Then there exists a finite energy weak solution of the compressible Navier-Stokes system on [0, T ] associated to the initial data (ρ 0 , u 0 ).

Let us now investigate the issue of the inviscid limit. Formally when the coefficient ε is set equal to zero in (1)-( 3) one obtains the following compressible Euler system:

∂ t ρ E + div(ρ E u E ) = 0, ( 10
)
∂ t (ρ E u E ) + div(ρ E u E ⊗ u E ) + ∇ x p(ρ E ) = 0, (11)
for which one prescribes the following initial condition:

ρ E | t=0 = ρ E 0 , (ρ E u E )| t=0 = ρ E 0 u E 0 . ( 12
)
and the following boundary condition:

u E • n| ∂Ω = 0, ( 13
)
where n is the unit outward normal to the domain Ω. Let us stress in particular the loss of information about the tangential components from ( 6) to [START_REF] Feireisl | Weak-strong uniqueness property for the full Navier-Stokes-Fourier system[END_REF]. For this system the local existence of strong solutions is well-known, cf. [START_REF] Agemi | The initial-boundary value problem for inviscid barotropic fluid motion[END_REF][START_REF] Beirão | On the barotropic motion of compressible perfect fluids[END_REF][START_REF] Ebin | The initial-boundary value problem for subsonic fluid motion[END_REF][START_REF] Ebin | Motion of slightly compressible fluids in a bounded domain[END_REF][START_REF] Schochet | The compressible Euler equations in a bounded domain: existence of solutions and the incompressible limit[END_REF]. [START_REF] Agemi | The initial-boundary value problem for inviscid barotropic fluid motion[END_REF][START_REF] Beirão | On the barotropic motion of compressible perfect fluids[END_REF][START_REF] Ebin | The initial-boundary value problem for subsonic fluid motion[END_REF][START_REF] Ebin | Motion of slightly compressible fluids in a bounded domain[END_REF][START_REF] Schochet | The compressible Euler equations in a bounded domain: existence of solutions and the incompressible limit[END_REF]). Let be given (ρ E 0 , u E 0 ) be some smooth and compatible initial data with 0 < inf Ω ρ E 0 and sup Ω ρ E 0 (x) < ∞. Then there exists T > 0 and a unique smooth solution (ρ E , u E ) of ( 10)-( 13) such that

Theorem 2 ([
0 < inf (0,T )×Ω ρ E and sup (0,T )×Ω ρ E < ∞. (14)
Above "compatible" refers to some conditions satisfied by the initial data on the boundary ∂Ω which are necessary for the existence of a strong solution. We refer here to [START_REF] Rauch | Differentiability of solutions to hyperbolic initial-boundary value problems[END_REF][START_REF] Schochet | The compressible Euler equations in a bounded domain: existence of solutions and the incompressible limit[END_REF] for more information on this subject.

We can now state the first main result of the paper. Let us denote

d Ω (x) := dist(x, ∂Ω) and Γ ε := {x ∈ Ω/ d Ω (x) < ε}, (15)
which is well defined for ε > 0 small enough.

Theorem 3. Let be given c > 0.

Let be given T > 0 and (ρ E , u E ) the strong solution of the Euler equations corresponding to an initial data (ρ E 0 , u E 0 ) as in Theorem 2.

For any ε ∈ (0, 1), let (ρ 0 , u 0 ) := (ρ ε 0 , u ε 0 ) be an initial data such that ρ 0 0, ρ 0 ∈ L γ (Ω), ρ 0 u 2 0 ∈ L 1 (Ω), and consider (ρ, u) := (ρ ε , u ε ) an associated weak solution of the compressible Navier-Stokes system on [0, T ] as given by Theorem 1.

Assume that

ρ 0 -ρ E 0 L γ (Ω) + Ω ρ 0 |u 0 -u E 0 | 2 dx → 0 when ε → 0. ( 16
)
Assume moreover that

ε (0,T )×Γcε ρ|u| 2 d 2 Ω + ρ 2 (u • n) 2 d 2 Ω + |∇ x u| 2 dxdt → 0, when ε → 0. ( 17
)
Then sup

t∈(0,T ) ρ -ρ E L γ (Ω) + Ω ρ|u -u E | 2 dx (t) → 0 when ε → 0. ( 18
)
Let us stress that [START_REF] Grenier | Boundary layers[END_REF] implies in particular that sup

(0,T ) ρu -ρ E u E L 1 (Ω) → 0 when ε → 0, since ρu -ρ E u E = (ρ -ρ E )u E + √ ρ √ ρ(u -u E ).
Theorem 3 extends to the compressible case the earlier result [START_REF] Kato | Remarks on zero viscosity limit for nonstationary Navier-Stokes flows with boundary[END_REF] obtained by Kato in the homogeneous incompressible case. Observe in particular the condition [START_REF] Gérard-Varet | On the ill-posedness of the Prandtl equation[END_REF] can be simplified when the density ρ is constant thanks to Hardy's inequality into the condition

ε (0,T )×Γcε |∇ x u| 2 dxdt → 0 when ε → 0,
which is the condition used by Kato in [START_REF] Kato | Remarks on zero viscosity limit for nonstationary Navier-Stokes flows with boundary[END_REF] in the incompressible case.

Let us mention that Theorem 3 can be easily extended to the slightly more general pressure laws as described in [14, Eq. (2.1)]. We choose here to deal with the law (5) for the sake of clarity. Actually we plan to address in a forthcoming work the case of the full Navier-Stokes-Fourier system, for which Feireisl and Novotný have recently established in [START_REF] Feireisl | Weak-strong uniqueness property for the full Navier-Stokes-Fourier system[END_REF] some relative energy estimates and weak-strong uniqueness.

Furthermore there exists many variants of Kato's argument: see for instance [START_REF] Wang | A Kato type theorem on zero viscosity limit of Navier-Stokes flows[END_REF][START_REF] Masmoudi | The Euler limit of the Navier-Stokes equations, and rotating fluids with boundary[END_REF]21]. In particular let us stress that the two last ones consider some settings where a Kato type analysis provides an unconditional theorem. Indeed [START_REF] Masmoudi | The Euler limit of the Navier-Stokes equations, and rotating fluids with boundary[END_REF] considers different horizontal and vertical viscosities, going to zero with different speeds whereas [21] considers an obstacle whose size goes to zero with the viscosity. We therefore hope that the analysis performed in this paper could be useful to extend some of these works in the compressible case.

Navier conditions

In this section we prescribe on the boundary ∂Ω of the fluid domain the following Navier condition:

u • n = 0 and ε(S(∇ x u)n) tan = βu tan on ∂Ω, (19)
where β 0 is the friction coefficient and u tan denotes the tangential component of a vector field u : Ω → R 3 on the boundary ∂Ω. For these boundary conditions the definition of weak solutions is adapted as follows.

Definition 2. Let (ρ 0 , u 0 ) be an initial data such that ρ 0 0, ρ 0 ∈ L γ (Ω), ρ 0 u 2 0 ∈ L 1 (Ω). Let q 0 := ρ 0 u 0 and T > 0. We say that (ρ, u) is a finite energy weak solution of the compressible Navier-Stokes system on [0, T ] associated to the initial data (ρ 0 , u 0 ) if

• ρ ∈ C w ([0, T ]; L γ (Ω)), ρu ∈ C w ([0, T ]; L 2γ γ+1 (Ω)), ∇ x u ∈ L 2 (0, T ; L 2 (Ω)), ρu 2 ∈ C w ([0, T ]; L 1 (Ω)),
• the identity

Ω ρ(T, •)φ(T, •) dx - Ω ρ 0 φ(0, •) dx = T 0 Ω (ρ∂ t φ + ρu • ∇ x φ)dxdt holds for any φ ∈ C ∞ c ([0, T ] × Ω; R), • the identity Ω ρ(T, •)u(T, •) • φ(T, •) dx - Ω q 0 • φ(0, •) dx = -β T 0 ∂Ω u • φ dσdt + T 0 Ω ρu • ∂ t φ + ρu ⊗ u : ∇ x φ + p(ρ) div φ -εS(∇ x u) : ∇ x φ dxdt holds for any φ ∈ C ∞ c ([0, T ] × Ω; R 3 ) such that φ • n = 0 on ∂Ω,
• the energy inequality:

E(ρ(τ, •), u(τ, •)) + ε τ 0 Ω S(∇ x u) : ∇ x u dxdt + β τ 0 ∂Ω |u| 2 dσdt E(ρ 0 , u 0 ).
holds for almost every τ ∈ [0, T ].

Above the integration element dσ refers to the surface measure on ∂Ω.

Let us now state the second main result of this paper.

Theorem 4. Let be given T > 0 and (ρ E , u E ) the strong solution of the Euler equations corresponding to an initial data (ρ E 0 , u E 0 ) as in Theorem 2. For any ε ∈ (0, 1), let (ρ 0 , u 0 ) := (ρ ε 0 , u ε 0 ) be an initial data such that ρ 0 0, ρ 0 ∈ L γ (Ω), ρ 0 u 2 0 ∈ L 1 (Ω) and consider (ρ, u) := (ρ ε , u ε ) a corresponding weak solution on [0, T ] in the sense of Definition 2.

Assume that (ρ 0 , u 0 ) converges to (ρ E 0 , u E 0 ) when ε converges to 0 in the sense of [START_REF] Gallay | Stability and interaction of vortices in two-dimensional viscous flows[END_REF]. Assume that β := β ε converges to 0 when ε converges to 0. Then,

sup (0,T ) ρ -ρ E L γ (Ω) + Ω 1 2 ρ|u -u E | 2 dx (t) → 0 when ε → 0.
Theorem 4 extends to the compressible case the earlier results [START_REF] Iftimie | Inviscid limits for the Navier-Stokes equations with Navier friction boundary conditions[END_REF][START_REF] Paddick | Stability and instability of Navier boundary layers[END_REF][START_REF] Bardos | The incompressible Euler limit of the Boltzmann equation with accommodation boundary condition[END_REF][START_REF] Wang | Vanishing viscous limits for 3D Navier-Stokes equations with a Navier-slip boundary conditions[END_REF] which tackled the homogeneous incompressible case. As in these works Theorem 4 fails to tackle the case where β is a O(1) when ε converges to 0, which seems of special interest in view of the kinetic derivation of the Navier condition performed in [START_REF] Masmoudi | From the Boltzmann equation to the Stokes-Fourier system in a bounded domain[END_REF][START_REF] Bardos | The incompressible Euler limit of the Boltzmann equation with accommodation boundary condition[END_REF].

Proof of Theorem 3

In this section we prove Theorem 3. We will proceed in three steps. First we will recall the recent result [START_REF] Feireisl | Suitable weak solutions to the Navier-Stokes equations of compressible viscous fluids[END_REF] about some relative energy inequalities satisfied by the weak solutions of the compressible Navier-Stokes system. These inequalities provide a non-symmetric "measure" of the difference between a weak solution of the compressible Navier-Stokes system and a smooth test function satisfying the no-slip condition. As the smooth solutions of the Euler equations do not satisfy the tangential part of the no-slip condition, one cannot apply directly these relative energy inequalities. In order to overcome this difficulty we will follow a strategy used by Kato in the incompressible setting, see [START_REF] Kato | Remarks on zero viscosity limit for nonstationary Navier-Stokes flows with boundary[END_REF], by constructing a "fake" layer which, added to the Euler solution, provided a smooth test function which satisfies the no-slip condition and yet quite close to the Euler solution.

Relative energy inequality

Let us recall first a quite general definition of the notion of relative entropy. Let be given an integer N 1 and V an open subset of R N . Given a smooth function f : V → R and v, w ∈ V the relative entropy f (v|w) is defined by

f (v|w) := f (v) -f ′ (w) • (v -w) -f (w).
Applying this definition to the energy defined in (8) leads to the introduction of the following relative energy E([ρ, u]|[r, U ]) of (ρ, u) with respect to (r, U ):

E([ρ, u]|[r, U ]) := Ω E([ρ, u]|[r, U ]) dx, with E([ρ, u]|[r, U ]) := 1 2 ρ|u -U | 2 + H(ρ|r),
where H(ρ|r

) := ρ γ γ -1 - γ(ρ -r)r γ-1 γ -1 - r γ γ -1 .
Note that, since p is strictly convex, the quantity H(ρ|r) is nonnegative and vanishes only when ρ = r. Indeed H(ρ|r) provides a nice control of the difference between ρ and r, since according to [15, Eq. (4.15)], for any compact K ⊂ (0, +∞) there exists two positive constants c 1 and c 2 such that for any ρ 0 and for any r ∈ K,

c 1 |ρ -r| 2 1 |ρ-r|<1 + |ρ -r| γ 1 |ρ-r| 1 H(ρ|r) c 2 |ρ -r| 2 1 |ρ-r|<1 + |ρ -r| γ 1 |ρ-r| 1 . (20)
In particular, using that the domain Ω is bounded, we infer that for any compact K ⊂ (0, +∞) there exists a constant C > 0 such that for any functions ρ : Ω → [0, ∞) and r :

Ω → K, C ρ -r γ L γ (Ω) Ω H(ρ|r)dx γ + Ω H(ρ|r)dx, C Ω H(ρ|r)dx ρ -r γ L γ (Ω) + ρ -r 2 L γ (Ω) . (21)
Let us now recall the following nice recent result which is a slight rephrasing of [14, Th. 2.1].

Theorem 5 ([14]). Let T > 0 and (ρ, u) be a finite energy weak solution of the compressible Navier-Stokes system on [0, T ] associated to an initial data (ρ 0 , u 0 ) as in Theorem 1. Then, for any smooth test functions (r, U ) : [0, T ] × Ω → (0, +∞) × R 3 satisfying the no-slip condition U | ∂Ω = 0, we have the following relative energy inequality:

E([ρ, u]|[r, U ])(τ ) + τ 0 Ω εS(∇ x u) : ∇ x u dxdt E 0 + τ 0 R(ρ, u, r, U )dt, ( 22
)
for almost every τ ∈ (0, T ), where

E 0 := E([ρ 0 , u 0 ]|[r(0, •), U (0, •)]), (23)
and

R(ρ, u, r, U ) := Ω ρ ∂ t U + (u • ∇ x )U • (U -u)dx + Ω εS(∇ x u) : ∇ x U dx (24)
+

Ω (r -ρ)∂ t H ′ (r) + ∇ x H ′ (r) • (rU -ρu) dx - Ω (div U ) p(ρ) -p(r) dx.
Let us stress that Theorem 5 can be thought as a counterpart of [6, Proposition 1] which establishes that finite energy weak solutions of the incompressible Euler equations are dissipative in the sense of Lions.

A Kato type "fake" layer

The goal of this section is to prove the following result, where we make use of the Landau notations o(1) and O(1) for quantities respectively converging to 0 and bounded with respect to the limit ε → 0 + .

Proposition 1. Under the assumptions of Theorem 3 there exists v

F := v ε F ∈ C([0, T ] × Ω; R 3 ), supported in Γ cε , such that v F = O(1) in C([0, T ] × Ω), (25)
u E -v F = 0 on ∂Ω, (26)
v F = O(ε 1 p ) in C([0, T ]; L p (Ω)), for 1 p < +∞, (27)
∂ t v F = O(ε 1 p ) in C([0, T ]; L p (Ω)), for 1 p < +∞, (28)
∇ x v F L ∞ ([0,T ];L 2 (Γcε)) = O(ε -1 2 ), ( 29
)
d Ω ∇ x v F = O(ε 1 2 ) in L ∞ ([0, T ]; L 2 (Ω)), ( 30
)
d 2 Ω ∇ x v F = O(ε) in C([0, T ] × Ω), ( 31
) div v F = O(1) in C([0, T ] × Ω), ( 32
) div v F = O(ε 1 p ) in C([0, T ]; L p (Ω)), for 1 p < +∞. ( 33
)
Let us recall that d Ω and Γ cε are defined in [START_REF] Feireisl | Suitable weak solutions to the Navier-Stokes equations of compressible viscous fluids[END_REF].

Proof. Let ξ : [0, +∞) → [0, +∞) be a smooth cut-off function such that ξ(0) = 1 and ξ(r) = 0 for r 1. We define

z(x) := ξ( d Ω (x) cε ), ξ(r) := rξ ′ (r), z(x) := ξ( d Ω (x) cε ), ξ(r) := r 2 ξ ′ (r), ẑ(x) := ξ( d Ω (x) cε ) and v F := zu E . ( 34
)
We easily see that ( 25)-( 29) are satisfied. In particular let us stress that the leading order term of ∇ x v F is given by the normal derivative

n • ∇ x v F = zn • ∇ x u E + 1 cε ξ ′ ( d Ω (x) cε )u E .
Thus the leading order term of d Ω ∇ x v F and d 2 Ω ∇ x v F are given by the respective contributions of the second term in the right hand side above, which can be recast as zu E and cεẑu E , from which we infer [START_REF] Rousset | Characteristic boundary layers in real vanishing viscosity limits[END_REF] and [START_REF] Saint-Raymond | Hydrodynamic limits: some improvements of the relative entropy method[END_REF].

Finally let us introduce the function φ := u E •n dΩ which is smooth up to the boundary because of ( 13). Then we observe that div

v F = z div u E + u E • ∇ x z = z div u E + φz,
which yields ( 32) and (33).

Core of the proof of Theorem 3

First using ( 7), ( 9) and ( 16) we easily obtain that the norms

ρ L ∞ (0,T ;L γ (Ω)) + ρu 2 L ∞ (0,T ;L 1 (Ω)) + √ ε ∇ x u L 2 ((0,T )×Ω) = O(1), (35)
with respect to ε → 0. Let us also say immediately that we will make use several times of ( 20) and (21) with the compact K := [inf (0,T )×Ω ρ E , sup (0,T )×Ω ρ E ] (see [START_REF] Feireisl | Relative entropies, suitable weak solutions, and weak-strong uniqueness for the compressible Navier-Stokes system[END_REF]).

Now the basic idea is to apply [START_REF] Iftimie | Inviscid limits for the Navier-Stokes equations with Navier friction boundary conditions[END_REF] to (r, U ) = (ρ E , u E -v F ). The following lemma isolates what exactly we expect from this idea. Lemma 1. If almost everywhere in [0, T ], there holds

|R(ρ, u, ρ E , U )| E([ρ, u]|[ρ E , u E ]) + o(1), (36)
where the o( 1) is with respect to L 1 (0, T ), then Theorem 3 holds true.

Proof. Let us first observe that

1 2 E([ρ, u]|[ρ E , u E ]) E([ρ, u]|[r, U ]) + 1 2 Ω ρ|v F | 2 dx = E([ρ, u]|[r, U ]) + o(1)
in L 1 (0, T ), thanks to Holder's inequality, ( 35) and ( 27). Now, using ( 16) and the second inequality in (21) we obtain that

E([ρ 0 , u 0 ]|[ρ E 0 , u E 0 ]) → 0 when ε → 0.
Then it is sufficient to apply the Gronwall lemma to [START_REF] Iftimie | Inviscid limits for the Navier-Stokes equations with Navier friction boundary conditions[END_REF]

applied to (r, U ) = (ρ E , u E -v F ) taking into account (36) to conclude that sup t∈(0,T ) E([ρ, u]|[ρ E , u E ]) (t) → 0 when ε → 0.
Finally it remains to use the first inequality in (21) to complete the proof of Lemma (1).

Let us point out that the proof of Lemma 1 above makes no use of the second term of the left hand side of [START_REF] Iftimie | Inviscid limits for the Navier-Stokes equations with Navier friction boundary conditions[END_REF].

We now prove an estimate of the form [START_REF] Wolibner | Un théorème sur l'existence du mouvement plan d'un fluide parfait[END_REF]. We first decompose the first term of the right hand side in [START_REF] Leray | Sur le mouvement d'un liquide visqueux emplissant l'espace[END_REF] to get

R(ρ, u, ρ E , U ) = Ω ρ ∂ t u E + (u E • ∇ x )u E • (U -u)dx + Ω ρ ((u -u E ) • ∇ x )u E • (U -u)dx - Ω ρ ∂ t v F + (u • ∇ x )v F • (U -u) dx + Ω εS(∇ x u) : ∇ x U dx + Ω (ρ E -ρ)∂ t H ′ (ρ E ) + ∇ x H ′ (ρ E ) • (ρ E U -ρu) dx - Ω (div U ) p(ρ) -p(ρ E ) dx.
Then we deduce from ( 10)-( 11) that

∂ t u E + (u E • ∇ x )u E = -∇ x H ′ (ρ E ), ( 37
) so that R(ρ, u, ρ E , U ) = Ω ρ ((u -u E ) • ∇ x )u E • (U -u)dx - Ω ρ ∂ t v F + (u • ∇ x )v F • (U -u)dx + Ω εS(∇ x u) : ∇ x U dx + Ω (ρ E -ρ) ∂ t H ′ (ρ E ) + U • ∇ x H ′ (ρ E ) dx - Ω (div U ) p(ρ) -p(ρ E ) dx.
Let us decompose the two last terms into

Ω (ρ E -ρ) ∂ t H ′ (ρ E ) + U • ∇ x H ′ (ρ E ) dx - Ω (div U ) p(ρ) -p(ρ E ) dx = Ω (ρ E -ρ) ∂ t H ′ (ρ E ) + u E • ∇ x H ′ (ρ E ) dx - Ω (div u E ) p(ρ) -p(ρ E ) dx - Ω (ρ E -ρ) v F • ∇ x H ′ (ρ E ) dx + Ω (div v F ) p(ρ) -p(ρ E ) dx.
Moreover using again [START_REF] Feireisl | On the existence of globally defined weak solutions to the Navier-Stokes equations[END_REF] we obtain that

∂ t H ′ (ρ E ) + u E • ∇ x H ′ (ρ E ) = -(div u E )p ′ (ρ E ), (38)
so that

R(ρ, u, ρ E , U ) = Ω ρ ((u -u E ) • ∇ x )u E • (U -u)dx - Ω ρ ∂ t v F + (u • ∇ x )v F • (U -u)dx + Ω εS(∇ x u) : ∇ x U dx - Ω (div u E ) p(ρ) -p(ρ E ) -p ′ (ρ E )(ρ -ρ E ) dx - Ω (ρ E -ρ) v F • ∇ x H ′ (ρ E ) dx + Ω (div v F ) p(ρ) -p(ρ E ) dx =: R 1 + . . . + R 6 .
We decompose R 1 into

R 1 = - Ω ρ((u -u E ) ⊗ (u -u E )) : ∇ x u E dx - Ω ρ ((u -u E ) • ∇ x )u E • v F dx.
Therefore, using the Cauchy-Schwarz inequality, we obtain that there exists a constant C > 0 such that

|R 1 | C Ω ρ|u -u E | 2 dx + C Ω ρ|u -u E | 2 dx 1 2 Ω ρ|v F | 2 dx 1 2 , C Ω ρ|u -u E | 2 dx + C Ω ρ|u -u E | 2 dx 1 2 ε γ γ-1 ,
thanks to Holder's inequality, [START_REF] Wang | A Kato type theorem on zero viscosity limit of Navier-Stokes flows[END_REF] and [START_REF] Masmoudi | From the Boltzmann equation to the Stokes-Fourier system in a bounded domain[END_REF]. Then using Young's inequality, we get that there exists a constant C > 0 such that

|R 1 | C Ω ρ|u -u E | 2 dx + Cε 2γ γ-1 CE([ρ, u]|[ρ E , u E ]) + o(1). (39)
We decompose R 2 into

R 2 = - Ω ρ∂ t v F •(u E -u)dx+ Ω ρ∂ t v F •v F dx- Ω ρ (u•∇ x )v F •U dx+ Ω ρ(u⊗u) : ∇ x v F dx =: R 2,a +R 2,b +R 2,c +R 2,d .
Using the Cauchy-Schwarz inequality, we get

|R 2,a | Ω ρ|∂ t v F | 2 dx 1 2 Ω ρ|u -u E | 2 dx 1 2 .
Then using Holder's inequality, [START_REF] Paddick | Stability and instability of Navier boundary layers[END_REF], [START_REF] Wang | A Kato type theorem on zero viscosity limit of Navier-Stokes flows[END_REF] and Young's inequality, we get that R 2,a can be bounded as R 1 in [START_REF] Xin | Zero-viscosity limit of the linearized Navier-Stokes equations for a compressible viscous fluid in the half-plane[END_REF].

Using again Holder's inequality, ( 27), [START_REF] Paddick | Stability and instability of Navier boundary layers[END_REF] and [START_REF] Wang | A Kato type theorem on zero viscosity limit of Navier-Stokes flows[END_REF] we obtain that R 2,b = o(1) in L 1 (0, T ). Next, using [START_REF] Vasseur | Recent results on hydrodynamic limits[END_REF], we decompose R 2,c as

R 2,c = - Ω √ ρzU • √ ρu • ∇ x )u E dx - Ω ρu • n d Ω z(U • u E ).
We bound the first term of the right hand side above thanks to Holder's inequality, [START_REF] Wang | A Kato type theorem on zero viscosity limit of Navier-Stokes flows[END_REF] and the uniform boundedness of ∇ x u E and of U (see [START_REF] Leray | Étude de diverses équations intégrales non linéaires et de quelques problèmes de l'hydrodynamique[END_REF]) by C z

L 2γ γ-1 (Ω)
which is o(1) in L 1 (0, T ). In order to bound the second term we use again that U is bounded in C([0, T ]×R 3 ), as well as the condition on the support of z, the Cauchy-Schwarz inequality, [START_REF] Gérard-Varet | On the ill-posedness of the Prandtl equation[END_REF] and that z L 2 (Ω) = O(ε

). Thus we obtain R 2,c = o(1) in L 1 (0, T ). Regarding the term R 2,d , we use that

R 2,d = Ω ( √ ρ d Ω u ⊗ √ ρ d Ω u) : d 2 Ω ∇ x v F dx,
the condition on the support of v F , the condition (17) and the estimate (31) to obtain R 2,d = o(1) in L 1 (0, T ). We decompose R 3 into

R 3 = - Ω εS(∇ x u) : ∇ x v F dx + Ω εS(∇ x u) : ∇ x u E dx
so that, by the Cauchy-Schwarz inequality, [START_REF] Rauch | Differentiability of solutions to hyperbolic initial-boundary value problems[END_REF], the condition on the support of v F , ( 35) and ( 17) we obtain

R 3 = o(1) in L 1 (0, T ).
Now, we observe that

R 4 = -(γ -1) Ω (div u E )H(ρ|ρ E )dx.
Therefore,

|R 4 | C Ω H(ρ|ρ E )dx.
We decompose R 5 into

R 5 = - Ω∩{|ρ-ρ E |<1} (ρ E -ρ) v F • ∇ x H ′ (ρ E ) dx - Ω∩{|ρ-ρ E | 1} (ρ E -ρ) v F • ∇ x H ′ (ρ E ) dx.
Using Holder's inequality, ( 27) and ( 20), we obtain that there exists a constant c > 0 such that

c|R 5 | ε + Ω H(ρ|ρ E )dx.
We decompose R 6 into

R 6 = Ω (div v F ) p(ρ) -p(ρ E ) -p ′ (ρ E )(ρ -ρ E ) dx + Ω∩{|ρ-ρ E |<1} (div v F )p ′ (ρ E )(ρ -ρ E )dx + Ω∩{|ρ-ρ E | 1} (div v F )p ′ (ρ E )(ρ -ρ E )dx.
Thus, using Holder's inequality and (20), we obtain that there exists a constant c > 0 such that

c|R 6 | div v F L ∞ (Ω) Ω H(ρ|ρ E )dx + div v F L 2 (Ω) ( Ω H(ρ|ρ E )dx) 1 2 + div v F L γ γ-1 (Ω) ( Ω H(ρ|ρ E )dx) 1 γ .
Using now (32), ( 33) and Young's inequality, we get that there exists a constant c > 0 such that

c|R 6 | ε + Ω H(ρ|ρ E )dx.
Summing the previous estimates provides an estimate of the form [START_REF] Wolibner | Un théorème sur l'existence du mouvement plan d'un fluide parfait[END_REF] and therefore concludes the proof of Theorem 3.

Proof of Theorem 4

In this section we prove Theorem 4. We proceed as in the previous section. Actually it is even a little bit more simple since we will not need any fake layer here. The reason is that the relative energy inequality is valid, in this case, for any smooth test function whose normal velocity vanishes on the boundary. We will therefore apply this inequality directly to the Euler solution.

Relative energy inequality

In the case of the Navier boundary conditions the finite energy weak solutions of the compressible Navier-Stokes system enjoy the following relative energy inequality which is a slight rephrasing of [START_REF] Feireisl | Relative entropies, suitable weak solutions, and weak-strong uniqueness for the compressible Navier-Stokes system[END_REF]Eq. (3.11)-(3.12)].

Theorem 6 ([14]

). Let T > 0 and (ρ, u) be a finite energy weak solution of the compressible Navier-Stokes system associated to an initial data (ρ 0 , u 0 ) such that ρ 0 0, ρ 0 ∈ L γ (Ω), ρ 0 u 2 0 ∈ L 1 (Ω) in the sense of Definition 2. Then, for any smooth test functions (r, U ) : [0, T ] × Ω → (0, +∞) × R 3 satisfying U • n| ∂Ω = 0, we have the following relative energy inequality:

Proof of Theorem 4

We apply (40) to (r, U ) = (ρ E , u E ) and we use [START_REF] Wang | Vanishing viscous limits for 3D Navier-Stokes equations with a Navier-slip boundary conditions[END_REF] and then [START_REF] Yau | Relative entropy and hydrodynamics of Ginzburg-Landau models[END_REF] to get

R(ρ, u, ρ E , u E ) = Ω ρ ((u -u E ) • ∇ x )u E • (u E -u)dx + β ∂Ω u • u E dσ + ε Ω S(∇ x u) : ∇ x u E dx + Ω (ρ E -ρ) ∂ t H ′ (ρ E ) + u E • ∇ x H ′ (ρ E ) dx - Ω (div u E ) p(ρ) -p(ρ E ) dx, = - Ω ρ((u -u E ) ⊗ (u -u E )) : ∇ x u E dx + β ∂Ω u • u E dσ + ε Ω S(∇ x u) : ∇ x u E dx - Ω (div u E ) p(ρ) -p(ρ E ) -p ′ (ρ E )(ρ -ρ E ) dx =: R1 + . . . R4 .
We have

| R1 | C Ω ρ|u -u E | 2 . ( 41
)
On the other hand, we have:

| R2 | 1 2 β ∂Ω |u| 2 dσ + 1 2 β ∂Ω |u E | 2 dσ. (42)
Therefore the term produced in the right hand side of (40) by the first term of the right hand side above can be absorbed by the third term of the left hand side of (40), whereas the other term goes to zero as β goes to 0 when ε goes to 0. Regarding the term R3 , we use the Cauchy-Schwarz inequality and the Young inequality in order to get

| R3 | C 0 ε 2 Ω |∇ x u| 2 dx + Cε, (43)
where C 0 is the constant appearing in [START_REF] Ebin | Motion of slightly compressible fluids in a bounded domain[END_REF]. Therefore the term produced in the right hand side of (40) by the first term of the right hand side above can be absorbed by the second term of the left hand side of (40), whereas the other term goes to zero when ε goes to 0. Finally, we have

| R4 | CE([ρ, u]|[ρ E , u E ]). ( 44
)
Therefore it is sufficient to sum the estimates (41)-(44) and to use the Gronwall lemma to conclude the proof of Theorem 4.

E 0 R

 0 ([ρ, u]|[r, U ])(τ ) + ε τ 0 Ω S(∇ x u) : ∇ x u dx + β τ 0 ∂Ω |u| 2 dσdt E 0 + τ (ρ, u, r, U ) dt,(40)for almost every τ , where E 0 is given by[START_REF] Kato | Remarks on zero viscosity limit for nonstationary Navier-Stokes flows with boundary[END_REF] andR(ρ, u, r, U ) := Ω ρ ∂ t U + (u • ∇ x )U • (U -u) dx + ε Ω S(∇ x u) : ∇ x U dx + β ∂Ω u • U dσ + Ω (r -ρ)∂ t H ′ (r) + ∇ x H ′ (r) • (rU -ρu) dx -Ω (div U ) p(ρ) -p(r) dx.

Acknowledgements. The author is partially supported by the Agence Nationale de la Recherche, Project CISIFS, grant ANR-09-BLAN-0213-02.


Roman Kolpakov

Gregory Kucherov
email: gregory.kucherov@univ-mlv.fr

Tatiana Starikovskaya
email: tat.starikovskaya@gmail.com

Pattern matching on sparse suffix trees

. Such a tree is defined by partitioning the text into blocks of equal size and constructing the suffix tree only for those suffixes that start at block boundaries. We propose a new pattern matching algorithm on this structure. The algorithm is based on a notion of suffix links different from that of [9] and on the packing of several letters into one computer word.

I. INTRODUCTION

Many application areas, such as genomics or computer security for example, face a sharp growth of volumes of available data. Even with the spectacular development of hardware capacities, data size often remains a bottleneck for its efficient processing, which requires new algorithmic solutions allowing for both a compact representation and efficient querying of data.

Suffix trees remain a very popular and commonly used data structure for text indexing, that are known, however, to be rather space-consuming in practice. A way to save space, that we study in this paper, is to partition the text T into blocks of r characters and to use a suffix tree which stores only those suffixes that start at the block boundaries. Then the suffix tree has no more than n/r leaves and then no more than n/r internal nodes, where n is the length of T . Such a suffix tree, called an evenly spaced sparse suffix tree (hereafter sparse suffix tree for short), has been first introduced in [START_REF] Kärkkäinen | Sparse suffix trees[END_REF]. Figure 1 provides an example of a sparse suffix tree. The definition of sparse suffix tree has been generalized to an arbitrary text partition into words [START_REF] Andersson | Suffix trees on words[END_REF], and a corresponding notion of suffix arrays on words has also been studied [START_REF] Ferragina | Suffix arrays on words[END_REF].

A sparse suffix tree allows one to easily search for the occurrences of a pattern P that start at block boundaries. However, efficiently identifying occurrences of P starting inside blocks is a more complicated task. The first solution to it has been proposed in the original paper [START_REF] Kärkkäinen | Sparse suffix trees[END_REF], which takes time O(rn) in the worst case to compute all occurrences of P in T .

Recently, the idea of sparse suffix tree has been used in [START_REF] Chien | Geometric burrows-wheeler transform: Linking range searching and text indexing[END_REF] to build a succinct index of a text. Indeed, if r is of order log σ n, where σ is the alphabet size, then the sparse suffix tree takes space O(n/ log σ n) which is the minimal space needed to store the text itself. On the other hand, if r < log σ n then it is possible to compress T into a string T ′ by packing each block into a machine word, and to use a regular suffix tree for T ′ instead of a sparse suffix tree for T .

Based on these ideas, the algorithm of [START_REF] Chien | Geometric burrows-wheeler transform: Linking range searching and text indexing[END_REF] computes all occurrences of a pattern in a text in time O(m + (log n)(log σ n) + occ log n), where m is the pattern length and occ the number of occurrences of the pattern in the text. The idea of using a suffix tree for a compressed string has been further developed in [START_REF] Hon | On entropy-compressed text indexing in external memory[END_REF] to provide entropy-efficient indexes.

In this paper, we turn to the original approach based on the sparse suffix tree for the input text T . To make an efficient pattern matching possible, we augment the tree with suffix links defined differently from those of [START_REF] Kärkkäinen | Sparse suffix trees[END_REF]. Our algorithm computes all occurrences of a pattern of length m ≥ r in a text in O(m • max{1, r log σ w } + max{occ, r} • log n/ log log n)) time and O( n r ) space. Similar to [START_REF] Chien | Geometric burrows-wheeler transform: Linking range searching and text indexing[END_REF], [START_REF] Hon | On entropy-compressed text indexing in external memory[END_REF] we assume a unit-cost RAM model and take advantage of unit-cost comparisons of blocks of letters to speed up the algorithm.

Using sparse suffix trees over the alphabet of letters (as opposed to the meta-alphabet of blocks of letters stored in a computer word) has several advantages. Our construction works for any r and we avoid the use of perfect hashing in navigating over the suffix tree (under the assumption of constant-size alphabet). Furthermore, time and space bounds of [START_REF] Chien | Geometric burrows-wheeler transform: Linking range searching and text indexing[END_REF] and [START_REF] Hon | On entropy-compressed text indexing in external memory[END_REF] (for the index for internal memory model) can be obtained from our results by an appropriate choice of the block size r without any additional compressed text index data structure. Finally, our suffix links allow to locate all pattern suffixes P [k + 1..m], k = 0..r -1, occurring at block boundaries in a single traversal of the suffix tree, rather than locating them independently (as it is done in the previous works), which we believe to be more elegant.

The paper is organized as follows. We first define sparse suffix trees and associated suffix links, then explain how to compute occurrences of a pattern using this data structure and finally describe how this data structure can be constructed.

II. EVENLY SPACED SPARSE SUFFIX TREE

Let Σ denote an alphabet, i.e. a set of letters or characters, of cardinality σ. We assume a lexicographic order < on Σ, naturally extended to the set of all strings over Σ. Positions in strings are numbered from 1. For a string α, α[i..j] denotes substring α[i] . . . α[j], and α[j..] is a shorthand for the suffix α[j.. |α|] respectively.

We consider evenly spaced sparse suffix trees as defined in [START_REF] Kärkkäinen | Sparse suffix trees[END_REF]. Consider a string T [1..n]. Let Suf r be the set of suffixes {T [rj + 1..]|j = 0, 1, . . . , n r -1} (assume for simplicity that n is a multiple of r).

An r-spaced suffix tree of T , denoted ST r , is a compacted trie for the set Suf r . For r = 1, the r-spaced suffix tree is the usual suffix tree. Edges of an r-spaced suffix tree are labelled by substrings T [i..j] of T , represented by a pair (i, j). We define explicit and implicit nodes of ST r in the same way as for the regular suffix trees. An implicit node will be specified by a pair (v, ℓ), where v is the closest explicit ancestor node and ℓ is the offset with reference to v. Note that by definition of the tree, the labels of the outgoing edges of any explicit node have different first letters.

Assuming that the last letter of T is unique, ST r has n r leaves and then no more than n r explicit internal nodes. Therefore, ST r takes O( n r ) space. By default, a node may refer to either an explicit or an implicit node. A string α is represented in ST r if α is a prefix of one of the suffixes of Suf r , i.e. if α is a substring of T starting at a position rj + 1 for some j. In this case, α is the label of some node v of ST r , and we say that α is represented by v, and |α| is the string depth of v.

Consider the lexicographic order on suffixes Suf r . Note that each leaf of the tree ST r represents some suffix of Suf r , and we call the rank of a leaf v the rank of the suffix represented by v in the lexicographic order on Suf r .

For a node v, we define M inRank(v) and M axRank(v) to be respectively the minimal and the maximal rank of leaves in a subtree of ST r rooted at v. The ranks of all leaves of the subtree rooted at v form the rank interval

[M inRank(v), M axRank(v)].
If α is a word corresponding to v, then the ranks of suffixes of Suf r starting with α are specified by the interval

[M inRank(v), M axRank(v)].
We assume that for each explicit node v of ST r , M inRank(v) and M axRank(v), as well as its string depth d(v) can be recovered in constant time. This can be trivially achieved by post-processing the tree and storing this information explicitly.

We extend the r-spaced suffix tree ST r with suffix links: for each explicit node v representing a string α, a suffix link s(v) maps v to a (not necessarily explicit) node labelled with the longest proper suffix α[i+1..] represented in the tree (see Fig. 2). Offset i will be called the type of the suffix link. It follows easily that 1 ≤ i ≤ r. Note that this definition of suffix links is different from that of [START_REF] Kärkkäinen | Sparse suffix trees[END_REF] which sets s(v) to be the node, always explicit, representing the suffix α[r + 1..].

For each explicit node v of ST r , we store the target node s(v) together with the type of the suffix link.

III. PATTERN MATCHING ALGORITHM

Consider a pattern P [1..m], where m ≥ r. To find the occurrences of P in T we use the following general idea. Based on the sparse suffix tree, we first locate all occurrences of the pattern suffixes P [1..], P [2..], . . . , P [r..] starting at block boundaries with the procedure RIGHTSEARCH that we describe in Section III-A. Secondly, we locate all occurrences of P [1..k], for k = 1..r -1, ending at block boundaries using another procedure LEFTSEARCH. Finally, procedure SELECTION computes those boundaries that are both preceded by P [1..k] and followed by P [k + 1..] for the same k, and thus correspond to occurrences of the entire pattern. Procedure SELECTION is essentially the same as in [START_REF] Hon | On entropy-compressed text indexing in external memory[END_REF], but we still provide its description in Section III-B for the sake of completeness. . We use bit-vector operations to speed up the algorithms and we assume that both strings P and T are given in a packed form, namely that they are divided into blocks of t = w log σ characters, where w is the size of a machine word, and each block is packed into one machine word. When following an edge in the tree, its label T [i..j] is divided into blocks of t letters, except for possibly a smaller last block, and each block is compared by a single operation.

Assume that RIGHTSEARCH arrives at some (generally implicit) node (v, ℓ) reaching the end of P [k + 1..m] (line 14 of Algorithm 1). Then the algorithm retrieves the rank interval [M inRank(v ′ ), M axRank(v ′ )], where v ′ is the closest explicit descendant node, which specifies all the occurrences of P [k + 1..] at block boundaries. After that, the traversal jumps to s(v) and proceeds with the prefix

P [k + i + 1, m -ℓ + 1] of the current suffix P [k + i + 1..],
where i is the type of suffix link s(v) (lines 20-22).

Assume now that RIGHTSEARCH reaches a mismatch while processing current suffix P [k + 1..] (line 8). Assume that the mismatch occurred when visiting a node (v, ℓ) and processing a prefix P [k + 1..p] of P [k + 1..]. Similarly to the previous case, the algorithm jumps to s(v) and proceeds with the prefix

P [k + i + 1, p -ℓ + 1] of the new current suffix P [k + i + 1..],
where i is the type of suffix link s(v). The procedure is illustrated on Fig. 3.

Importantly, the described procedure does not miss any occurrences:

Algorithm 1 RIGHTSEARCH 1: k ← 1 2: p ← 1 3: Node ← root 4: NodeOffset ← 0 5: while k ≤ r do 6:
while p ≤ m do 7:

starting from position p in P , follow down the current edge of ST r by comparing blocks of up to t characters at once 8:

if mismatch occurred then 9:

break the while-loop (Node, NodeOffset) ← s(Node)

22:

k ← k + type of the suffix link (Node, s(Node)) 23: end while Lemma 1. RIGHTSEARCH correctly identifies all suffixes P [k + 1..], 0 ≤ k ≤ r -1, occurring at block boundaries of T .

Proof: It is easy to see by induction that once a suffix P [k +1..] is found (line 11 of Algorithm 1), it is represented in the tree and therefore occurs starting at a block boundary.

A key point is that the procedure does not miss any such suffixes. This is due to the definition of suffix links: when following a suffix link (lines 20-22), the algorithm switches from processing the suffix P [k + 1..] to the suffix P [k + i + 1..], where i is the type of the suffix link. It follows that no suffix P [k + i ′ + 1..] for i ′ < i can be represented in the tree. This is because the suffix link points to the longest suffix represented in the tree.

Let us now turn to the analysis of the running time of RIGHTSEARCH. The algorithm navigates over the suffix tree ST r by following edges downwards. We analyse separately the traversal of two types of edges: completely traversed edges (hereafter traversed edges), and incompletely traversed edges (hereafter dead-end edges), either due to a mismatch or due to a found suffix.

The number of dead-end edges is at most r, as each of them terminates the processing of some suffix P [k + 1..].

On each such edge, the algorithms makes no more that m/t block comparisons. Therefore, the whole time spent on deadend edges is O( mr t ). The number of all comparisons made along the traversed edges is bounded by m, as these comparisons compare different portions of the pattern. In other words, the sequence of these comparisons can be associated with moving a pointer in the pattern left-to-right by blocks of letters. The whole time spent on these comparisons is thus O(m).

Theorem 1. RIGHTSEARCH computes the rank intervals of all suffixes

P [k + 1..], 0 ≤ k ≤ r -1, occurring at block boundaries of T in time O(m • max{1, r t }) = O(m • max{1, r log σ w }).

B. LEFTSEARCH and SELECTION

LEFTSEARCH locates all occurrences of P [1.

.k] ending at block boundaries of T . Let RevBlocks r be a set of the reversed blocks T [r(j -1) + 1..rj], for j = 1, . . . , n r . We build a compacted trie for RevBlocks r . Each leaf v of the trie is associated with the indices of the blocks it represents, namely with the set {j|1 ≤ j ≤ n r -1 and v represents the reversal of T [r(j -1) + 1..rj]}.

We augment the trie with suffix links and rank intervals defined in the same way as in RIGHTSEARCH. Then we run the procedure described in RIGHTSEARCH, but we use the trie instead of the sparse suffix tree and a pattern P From Section IV it is obvious that the trie for RevBlocks r and suffix links for it can be constructed in O(nr) time.

We now show how SELECTION can be reduced to 2D range reporting problem. Consider a rank interval I k right output by RIGHTSEARCH for some k (line 18 of Algorithm 1). We have to compute all j, 1 ≤ j ≤ n r , such that the rank of T [rj + 1..] in the lexicographical order on Suf r belongs to I k right and the rank of the reversal of T [r(j -1) + 1..rj] in lexicographical order on RevBlocks r belongs to I k lef t . Each such j will correspond to an occurrence of P [1..m] starting at position rj -k + 1 in T .

Consider a set Q of n r points, where a point j has the first coordinate equal to the rank of T [jr + 1..] in the lexicographical order on Suf r , and the second coordinate equal to the rank of the reversal of T [r(j -1) + 1..rj] in lexicographical order on RevBlocks r . It can be easily seen that Q can be constructed in linear time. Then the desired output is the points of Q which lie inside the rectangle I k lef t × I k right (see Fig. 4). The problem of selecting points lying inside a given rectangle within some larger set of points has been studied in the literature under the name of 2D range reporting problem. We can use several linear-space solutions to this problem that have different trade-offs between preprocessing and query time. Let occ k be the number of points inside the rectangle I k lef t × I k right (or, alternatively, the number of occurrences of P in T crossing a block border at position k + 1).

The most recent and efficient linear 2D range reporting data structure [START_REF] Chan | Orthogonal range searching on the ram, revisited[END_REF] has O(max{occ k , 1} log ǫ n) query time, where ǫ is an arbitrary positive constant, however, no bound for construction time of the data structure has been given in the paper. The data structure of [START_REF] Nekrich | Orthogonal range searching in linear and almost-linear space[END_REF] has O(log n + occ k log ǫ n) query time and O( n r log 3 n) construction time in our case.

In our solution we use generalized wavelet trees ( [START_REF] Ferragina | Compressed representations of sequences and full-text indexes[END_REF], [START_REF] Mäkinen | Position-restricted substring searching[END_REF], [START_REF] Hon | Ordered pattern matching: Towards full-text retrieval[END_REF], [START_REF] Yu | Efficient data structures for the orthogonal range successor problem[END_REF]), which have O( n r log n) construction time in our case. With wavelet trees, SELECTION can be solved in O( n r ) space and in O((occ k + 1) log n/ log log n) time.

C. Resulting bound

We summarize the complexity bounds in the following theorem. Sparse suffix tree for T and suffix links take O( n r ) space, and same holds for the trie for RevBlocks r . The wavelet tree for Q takes O( n r ) space. Note that in the case when w = Θ(log n) (natural assumption under the RAM model) and r = Θ(log σ n), we obtain a fully linear pattern matching algorithm with respect to the pattern length running in O( n r ) space, which is the same performance as for the algorithm presented in [START_REF] Chien | Geometric burrows-wheeler transform: Linking range searching and text indexing[END_REF]. When r = log 2 n, we achieve query time and additional space of the index for the internal memory model describe in [START_REF] Hon | On entropy-compressed text indexing in external memory[END_REF].

Note for completeness that we have always assumed that the pattern length m is larger than r and, therefore, must cross at least one block boundary. In case m < r < log σ n, all occurrences of P located inside blocks can be reported in O(m + occ) time and O( n r ) space with the method of [START_REF] Chien | Geometric burrows-wheeler transform: Linking range searching and text indexing[END_REF]. IV. CONSTRUCTION OF ST r Ukkonen and Kärkkäinen [START_REF] Kärkkäinen | Sparse suffix trees[END_REF] described how to construct the sparse suffix tree in time O(n) and space O(n/r) (see also [START_REF] Andersson | Suffix trees on words[END_REF], [START_REF] Inenaga | On-line linear-time construction of word suffix trees[END_REF], [START_REF] Uemura | Sparse and truncated suffix trees on variable-length codes[END_REF]). Denote by l(v) the string represented by a node v in ST r . The construction of [START_REF] Kärkkäinen | Sparse suffix trees[END_REF] uses suffix links defined as follows: for an explicit node v of ST r representing a string α = l(v), the suffix link of v points to the node representing α[r+1..]. We call such suffix links r-suffix links. The definition is well-founded, as if a string α, |α| > r, is represented in ST r , then the string α[r + 1..] is represented in ST r too. Moreover, if α is represented by an explicit node, then so is α[r + 1..].

Since our construction of sparse suffix tree differs from that of [START_REF] Kärkkäinen | Sparse suffix trees[END_REF] only in the definition of suffix links, we assume that we already have the tree constructed by the algorithm of [START_REF] Kärkkäinen | Sparse suffix trees[END_REF] equipped by r-suffix links and we have to set the suffix links as defined in Section II. We will consecutively set suffix links of type 1, 2, . . . , r.

For each explicit node v of ST r , we fix an arbitrary occurrence of l(v) in T starting at a block boundary. We then compile an array A of n r lists of nodes of ST r . A node v belongs to the i-th list iff the fixed occurrence of l(v) starts at position ir + 1 in T . We assume that nodes in each list of A occur in the increasing order of string depths. A can be compiled by one breadth-first traversal of ST r in O( n r ) time.

Consider some i, 0 ≤ i ≤ r -1. Let β j i , where 0 ≤ j ≤ n r -1 be the longest prefix of T [rj + i + 1..] represented in ST r . First, the algorithm locates the (possibly implicit) nodes v 0 , v 1 , . . . , v n r -1 of ST r representing β 0 i , β 1 i , . . . , β r-1 i respectively. Locating v 0 , v 1 , . . . , v n r -1 is done by simultaneously traversing ST r and comparing characters of T from left to right, similarly to the algorithm of RIGHTSEARCH. Suppose that we reach a (generally implicit) node v j representing β j i . If |β j i | ≤ r, then we start over from the root and continue to follow T from character T [r(j + 1) + i + 1]. Otherwise we move up to the closest explicit ancestor v of v j representing β j i [..ℓ] and follow the r-suffix link to get to a node u representing β j i [r + 1..ℓ]. As previously noted, this node exists and is explicit. We then proceed moving down from node u and comparing only the first characters of labels of edges with corresponding characters of β j i [ℓ + 1..]. When no move is possible any more, we have arrived at the node representing the longest prefix of T [1 + i + rj + r..] represented in ST r , which is β j+1 i .

The following lemma can be proved: Lemma 2. The algorithm above correctly locates the nodes v 0 , v 1 , . . . , v n r -1 in time O(n). Secondly, the algorithm builds suffix links of type i using the nodes v 0 , v 1 , . . . , v n r -1 . Lemma 3. Let u and v be two explicit nodes such that u is an ancestor of v (that is, l(u) is a prefix of l(v)). Then the type of the suffix link of u is not larger than the type of the suffix link of v.

The Lemma will insure that all nodes with suffix links of type i occur consecutively in the initial part of lists A[j] (note that by induction, the nodes with suffix links of type smaller than i have been deleted from lists A[j], see below) and if the head element of some A[j] does not have a suffix link of type i, then no other element of A[j] has one. Note also that a suffix link of type i of some node v in A[j] must point to a node on the path from the root to v j .

Hence, the main idea is to maintain a stack of nodes on the path from the root of ST r to v j to compute suffix links of type i for nodes of A[j]. Note that v j 's are implicit nodes in general, therefore some additional care is needed for this procedure.

In more details, we traverse ST r depth-first and maintain a stack V (implemented as an array, i.e. allowing access to all stored elements) of size O( n r ) storing explicit nodes on the path from the root to the the current node of ST r .

Assume that we are in a node v j representing β j i , 0 ≤ j ≤ n r -1. We check the head element v of the list A[j]. If the string depth d(v) is less than d(v j ), then the type of a suffix link from v is i. We find the first node u on the path from the root of ST r to v j with string depth bigger than d(v) by a binary search on the elements of V . Obviously, the target node s(v) is a (possibly implicit) node (u, d(u) -d(v)).

After computing s(v), v is deleted from A[j]. We repeat this procedure while string depth of the head element is less than d(v j ) and then continue the tree traversal.

Let us now turn to time and space analysis. Recall that ST r with r-suffix links is computed in O( n r ) time. To locate nodes v 0 , v 1 , . . . , v n r -1 we need O(n) time for a fixed i, and therefore O(nr) time altogether. To compute all suffix links, we need O( n r • log n r + n) time. Finally, to store V and A during tree traversals we need O( n r ) space.

V. CONCLUDING REMARKS

In this paper, we introduced a new definition of suffix links in evenly spaced sparse suffix trees. Based on this structure, we proposed a new pattern matching algorithm that applies to any partitioning of the text into blocks of equal size. Assuming that a computer word is Θ(log n) bits, we obtain essentially the same time and space bounds as those of [START_REF] Chien | Geometric burrows-wheeler transform: Linking range searching and text indexing[END_REF], [START_REF] Hon | On entropy-compressed text indexing in external memory[END_REF].

We believe that our definition of suffix links could bring further improvements to the pattern matching algorithm. In particular, we conjecture that one could completely avoid using an "external" data structure for orthogonal range queries and design an efficient algorithm based on the sparse suffix tree alone. Another challenging problem for future research is to get rid of the multiplicative factor depending on n in the occ term of the time bound (see Theorem 2).

Figure 1 .

 1 Figure 1. A sparse suffix tree for string T = abb baa aba aaa bab and r = 3.

Figure 2 .

 2 Figure 2. A sparse suffix tree for string T = abb baa aba aaa bab and r = 3 with suffix links and ranks of leaves shown.

Figure 3 .

 3 Figure 3. Right search for pattern P = abaa in string T = abb baa aba aaa bab, r = 3. During the procedure the algorithm goes along the path is ABCDCEF GF BK (the path is shown by dashes)

  A. RIGHTSEARCH The procedure RIGHTSEARCH (Algorithm 1) proceeds by navigating through ST r trying to locate all nodes representing P [1..], P [2..], . . . , P [r..]. Starting at the root with P [1..], RIGHTSEARCH follows down the current suffix P [k + 1..] in the tree as long as possible.

  [r -1]P [r -2] . . . P [1]. So, for each k = 1, . . . , r -1, LEFTSEARCH locates the closest explicit descendant of the node representing P [k]P [k -1] . . . P [1] and retrieves the rank interval I k lef t corresponding to that node. Obviously, I k lef t contains starting positions of reversed blocks starting with P [k]P [k -1] . . . P [1]. All the intervals I k lef t , for k = 1, . . . , r -1, can be computed in O(r max{1, r log σ w }) time (time analysis is exactly the same as in RIGHTSEARCH).

Figure 4 .

 4 Figure 4. Selection on Q.

Theorem 2 .

 2 Identifying all occurrences of a pattern P of length m ≥ r in T takes O(m • max{1, r log σ w } + max{occ, r}•log n/ log log n)) time and O( n r ) space, where occ is the total number of output occurrences. • max{1, r log σ w }). Time taken by LEFT-SEARCH is O(r max{1, r log σ w }). SELECTION takes O((occ k + 1) log n/ log log n) time for each k, and therefore O(max{occ, r} • log n/ log log n) time overall.

Acknowledgment: The authors are grateful to Djamal Belazzougui for very helpful discussions. R.Kolpakov and T.Starikovskaya were partly supported respectively by grants 11-01-00508 and 10-01-93109-CNRS-a of the Russian Foundation for Basic Research.


Gregory Kucherov
email: gregory.kucherov@univ-mlv.fr

On-line construction of position heaps

 in that it considers the suffixes ordered in the descending order of length. Our construction is based on classic suffix pointers and resembles the Ukkonen's algorithm for suffix trees [Ukk95]. Using suffix pointers, the position heap can be extended into the augmented position heap that allows for a linear-time string matching algorithm [EMOW11].

Introduction

The theory of string algorithms developed beautiful data structures for string matching and text indexing. Among them, suffix tree and suffix array are most widely used structures, providing efficient solutions for a wide range of applications [START_REF] Crochemore | Text algorithms[END_REF][START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology[END_REF]. The DAWG (Directed Acyclic Word Graph) [BBH + 85], also known as suffix automaton [START_REF] Crochemore | Transducers and repetitions[END_REF], is another elegant structure that can be used both as a text index [BBH + 85] or as a matching automaton [START_REF] Crochemore | String matching with constraints[END_REF][START_REF] Crochemore | Text algorithms[END_REF].

Recently, a new position heap data structure was proposed [START_REF] Ehrenfeucht | Position heaps: A simple and dynamic text indexing data structure[END_REF]. Similar to the suffix tree, DAWG or suffix array, position heap allows for a pre-processing of a text string in order to efficiently search for patterns in it. As for the above-mentioned data structures, a position heap for a string of length n can be constructed in time O(n). Then all locations of a pattern of length m can be found in time O(m + occ), where occ is the number of occurrences.

The construction algorithm of [START_REF] Ehrenfeucht | Position heaps: A simple and dynamic text indexing data structure[END_REF] processes the string from right to left, like the Weiner's algorithm does for suffix trees [START_REF] Weiner | Linear pattern matching algorithm[END_REF]. Moreover, the construction requires a so-called dual heap, which is an additional trie on the same set of nodes. The position heap and its dual heap are constructed simultaneously.

To obtain a linear-time pattern matching algorithm of [START_REF] Ehrenfeucht | Position heaps: A simple and dynamic text indexing data structure[END_REF], the position heap should be post-processed in order to add some additional information, resulting in the augmented position heap. Most importantly, this information includes socalled maximal-reach pointers assigned to certain nodes. Computing these pointers makes use of the dual heap too.

In this paper, we propose a different construction of the position heap. First, we change the definition of the position heap by reversing the order of suffixes and thus allowing for a left-to-right traversal of the input string. The modified definition, however, preserves good properties of the position heap and does not affect the string matching algorithm proposed in [START_REF] Ehrenfeucht | Position heaps: A simple and dynamic text indexing data structure[END_REF]. For this modified definition, we propose an on-line algorithm for constructing the position heap. Our algorithm does not use the dual heap, replacing it by classic suffix pointers used for constructing suffix trees by the Ukkonen's algorithm [START_REF] Ukkonen | On-line construction of suffix-trees[END_REF] or for constructing the DAWG 1 [BBH + 85]. Our algorithm is simple and has some similarity with the Ukkonen's algorithm for suffix trees, as opposed to the Weiner's algorithm. We deliberately use some terminology of the Ukkonen's algorithm to underline this similarity.

We further show that the augmented position heap can be easily constructed using suffix pointers. Thus, we completely eliminate the use of the dual heap, replacing it by suffix pointers for constructing both the position heap and its augmented version. Even if this replacement does not provide an immediate improvement in space or running time, we believe that our construction is conceptually simpler and more natural.

Throughout the paper, we assume given a constant-size alphabet A. Positions of strings over A are numbered from 1, that is, a string w of length k is w

[1] . . . w[k]. The length k of w is denoted by |w|. w[i..j] denotes substring w[i] . . . w[j].
A trie (term attributed to Fredkin [START_REF] Fredkin | Trie memory[END_REF]) is a simple natural data structure for storing a set of strings. It is a tree with edges labeled by alphabet letters, such that for any internal node, the edges leading to the children nodes are labeled by distinct letters. In this paper, we assume the edges to be directed towards leaves, and call an edge labeled by a letter a an a-edge. A label of a node (path label) is the string formed by the letters labeling the edges of the path from the root to this node. Given a trie, a string w is said to be represented in the trie if it is a path label of some node. The corresponding node will then be denoted by w.

Definition of position heap

To define position heaps, we first need to introduce the sequence hash tree proposed by Coffman and Eve back in 1970 [START_REF] Coffman | File structures using hash functions[END_REF] as a data structure for implementing hash tables. Assume we are given an ordered set of strings W = {w 1 , . . . , w n } and assume for now that no w i is a prefix of w j for any j < i. The sequence hash tree for W , denoted SHT (W ), is a trie defined by the following iterative construction. We start with the tree SHT 0 (W ) consisting of a single root node root1 . We then construct SHT (W ) by processing strings w 1 , . . . , w k in this order and for each w i , adding one node to the tree. By induction, assume that SHT i (W ) is the sequence hash tree for {w 1 , . . . , w i }. To construct SHT i+1 (W ), we find the shortest prefix v of w i+1 which is not represented in SHT i (W ). Note that by our assumption, such a prefix always exists. Let v = v ′ a, a ∈ A, i.e. v ′ is the longest prefix of w i+1 represented in SHT i (W ). Then SHT i+1 (W ) is obtained from SHT i (W ) by adding a new node as a child of v ′ connected to v ′ by an a-edge and pointing to w i+1 . After inserting all strings of W , we obtain SHT (W ), that is SHT (W ) = SHT k (W ). Thus, SHT (W ) is a trie of n + 1 nodes such that a node pointing to w i is labeled by some prefix of w i . Note that the size of the sequence hash tree depends only on the number of strings in the set and does not depend on the length of these words. An example of sequence hash tree is given on Figure 1.

We now define the position heap of a string T . In [START_REF] Ehrenfeucht | Position heaps: A simple and dynamic text indexing data structure[END_REF], the position heap for T is defined as the sequence hash tree for the set of suffixes of T , where the suffixes are ordered in the ascending order of length, i.e. from right to left. This insures, in particular, the condition that no suffix is a prefix of a previously inserted suffix, and then no suffix is already represented in the position heap at the time of its insertion.

In this paper, we define the position heap of T to be the sequence hash tree for the set of suffixes of T , where the suffixes are ordered in the descending order of length, i.e. from left to right. From now on, we stick to this order. An immediate observation is that the assumption of the suffix hash tree does not hold anymore, and it may occur that an inserted suffix is already represented in the position heap by an existing node. One easy way to cope with this is to systematically assume that T is ended by a special sentinel symbol $, like it is generally assumed for the suffix tree.

On the other hand, as we will be interested in an on-line construction of the position heap, we will still need to construct the position heap for strings without the ending sentinel symbol. For that, we have to slightly change the definition of sequence hash tree of a set W , by allowing one node to point to several strings of W . The definition of the position heap extends then to any string, with the only difference that inserting a suffix may no longer lead to the creation of a node, but to inserting a new pointer to an existing node. This feature, however, will be used in a very restricted way, as the following observation shows.

Lemma 1 Let W be a set of distinct strings. Then every node of SHT (W ) points to at most two strings of W .

Proof: Straightforward from the definition of SHT (W ) and the fact that all strings are distinct.

As a consequence of Lemma 1, a position heap contains two types of nodes, pointing respectively to one and two suffixes of T . The former will be called regular nodes and the latter double nodes. We naturally assume that a pointer to a suffix is simply the starting position of that suffix, therefore regular and double nodes store one and two string positions respectively. Hereafter we interchangeably refer to "suffixes" and "positions" when the underlying string is unambiguously defined. Figure 2 provides an example of a position heap.

Properties of position heap

Denote by P H(T ) the position heap for a string T [1.

.n] constructed as defined in the previous section. In the following theorem, we summarize some key properties of the position heap. Property (i) is a straightforward from the definition, and properties (ii)-(iv) have been established in [START_REF] Ehrenfeucht | Position heaps: A simple and dynamic text indexing data structure[END_REF] but remain valid for our definition of position heap when suffixes are inserted from left to right.

Theorem 1 ([EMOW11]

) Consider P H(T [1.

.n]). The following properties hold.

(i) A substring T [i..j] is represented in P H(T ) iff there exist in T occurrences of strings T [i], T [i..i + 1], T [i..i + 2], . . . , T [i..j],
appearing in this order.

(ii) The labels of all nodes of P H(T ) form a factorial set. That is, if a string is represented in P H(T ), all its substrings are represented too. (iii) The depth of P H(T ) is no more than 2h(T ), where h(T ) is the length of the longest substring w of T which occurs |w| times in T (possibly with overlap).

(iv) If a string w occurs in T at least |w| times, then w is represented in P H(T ).

Inversely, if w is not represented in P H(T ) and w ′ is the longest prefix of w which is represented, then w cannot occur in T more than |w ′ | times.

Properties (iii) and (iv) show that the position heap of a string "adapts" to frequencies of its substrings. In particular, if a string is "frequent" (occurs as many times as it is long), then it is necessarily represented in the position heap. On the other hand, if it is not represented, it has less occurrences than its length. The latter property is crucial for obtaining a linear-time string matching algorithm of [START_REF] Ehrenfeucht | Position heaps: A simple and dynamic text indexing data structure[END_REF].

On-line construction algorithm

Let us have a closer look at the properties of double nodes of a position heap P H(T ). Each such node stores two positions i, j of T . Assume i < j, then positions i and j will be called the primary and the secondary positions respectively.

Lemma 2 If j is the secondary position of some node of a position heap, then so is j + 1.

Proof: Consider P H(T ) for some string T [1..n]. Assume i, j, i < j, are respectively primary and secondary positions of some node. This means that by the time the suffix T [j.

.n] is inserted into P H(T ) during its construction, node T [j.

.n] already exists. By Theorem 1(ii), node T [j + 1..n] exists too. A fortiori, node T [j + 1..n] exists when T [j + 1..n] is inserted into P H(T ). Therefore, j + 1 becomes the secondary position of that node after the insertion of suffix T [j + 1. and P H(T [1..k + 1]) and the modifications that need to be made to transform the former into the latter.

Let s be the active position of T [1..k]. First observe that for suffixes 1, . . . , s -1, no changes need to be made. Inserting each suffix T We describe now the algorithm implementing the changes specified by Lemma 3. We augment P H(T ) with suffix pointers f defined in the usual way: Definition 1 For each node T [i..j] of P H(T ), a suffix pointer is defined by

[i..k] for 1 ≤ i ≤ s -1 into P H(T [1..k])
f (T [i..j]) = T [i + 1..j].
Note that the definition is sound, as the node T [i + 1..j] exists whenever the node T [i..j] exists, according to Theorem 1(ii). For the root node, it will be convenient for us to define f (root ) =⊥, where ⊥ is a special node such that there is an a-edge between ⊥ and root for every a ∈ A (cf [START_REF] Ukkonen | On-line construction of suffix-trees[END_REF]). Figure 3 We now begin to describe the on-line construction algorithm for P H(T ), given a text T [1..n]. Consider the node T [s..k] of P H(T [1..k]) storing the active secondary position s, that we call the active node. If the active secondary position does not exist (i.e. there is no secondary positions at all), then the active node is root and the active position is set to k + 1. Observe that the nodes storing the other secondary positions s + 1, s + 2, . . . , n can be reached, in order, by following the chain of suffix pointers f (T [s..n]), f (f (T [s..n])), . . . until the root node is reached. Figure 3 provides an illustration. This leads us to the main trick of our construction: we will not store secondary positions at all, but only memorize the active secondary position and the active node. The secondary positions can be easily recovered by traversing the chain of suffix pointers starting from the active node and incrementing the position counter after traversing each edge. Note also that if the input string T is ended by a unique sentinel symbol, the resulting position heap does not contain any secondary nodes and there is no need to recover them.

Having in mind that the secondary positions are not stored explicitly, the transformation of P H(T [1..k]) into P H(T [1..k + 1]) specified by Lemma 3 is done by the following simple procedure. Starting from the active node, the algorithm traverses the chain of suffix pointers as long as the current node does not have an outgoing T [k + 1]-edge. For each such node, a new node is created linked by a T [k + 1]-edge to the current node. A suffix pointer to this new node is set from the previously created new node. Once the first node with an outgoing T [k + 1]-edge is encountered, the algorithm moves to the node this edge leads to, sets the suffix pointer to this node, and assigns this node to be the active node for the following iteration. The correctness of the last assignment is stated in the following lemma. • since the depth of T [s..k] (s is the active position) in P H(T [1..k]) is k + 1s and a traversal of a suffix link decrements the depth by 1 and increments the current position by 1, it follows that if the traversal of the suffix chain reaches the root node, the active position value becomes k+1, which is exactly what we need to start processing the next letter T [k + 1]. This shows why Algorithm 1 correctly maintains currentsuffix and never needs to reset it at the beginning of the for-loop iteration.

It is easy to see that the running time of Algorithm 1 is linear in the length n of the input string. Since each iteration of the while-loop creates a node, this loop iterates exactly n times over the whole run of the algorithm. Trivially, the for-loop iterates n times too, and all the involved operations are constant time. Thus, the whole algorithm takes O(n) time. The following theorem concludes the construction.

Theorem 2 For an input string T [1..n], Algorithm 1 correctly constructs P H(T ) on-line in time O(n).

Augmented position heap

Assume we have a text T [1..n] for which we constructed the position heap P H(T ). We don't assume that T is ended by a unique letter, and therefore some nodes of P H(T ) are double nodes and store two positions of T , one primary and one secondary. Here we assume that the secondary positions are actually stored (or can be retrieved in constant time for each node). As explained in Section 4, even if the secondary positions are not stored during the construction of P H(T ), they can be easily recovered once the construction is completed.

[EMOW11] proposed a linear-time string matching algorithm using P H(T [1..n]), i.e. an algorithm that computes all occurrences of a pattern string in T in time O(m + occ), where m is the pattern length and occ the number of occurrences. Describing this elegant algorithm is beyond the scope of this paper, we refer the reader to [START_REF] Ehrenfeucht | Position heaps: A simple and dynamic text indexing data structure[END_REF] for its description. Note that the algorithm itself applies without changes to our definition of position heap, as it does not depend in any way on the order that the suffixes of T are inserted.

However, the algorithm of [START_REF] Ehrenfeucht | Position heaps: A simple and dynamic text indexing data structure[END_REF] runs on P H(T ) enriched with some additional information. Let i denote the node of P H(T ) storing position i, 1 ≤ i ≤ n. The extended data structure, called the augmented position heap, should allow the following queries to be answered in constant time:

• given a position i, retrieve the node i,

• given two nodes i and j, is i a (not necessarily immediate) ancestor of j?

• given a position i of T , retrieve the node T [i..i + ℓ], where T [i..i + ℓ] is the longest substring of T starting at position i and represented in P H(T ).

To answer the first query, [START_REF] Ehrenfeucht | Position heaps: A simple and dynamic text indexing data structure[END_REF] simply introduces an auxiliary array storing, for each position i, a pointer to the node i. Maintaining this array during the construction of P H(T ) by Algorithm 1 is trivial: once a position is assigned to a newly created node (line 11 of Algorithm 1), a new entry of the array is created. If T is not ended by a unique symbol and then the final P H(T ) has secondary positions, those are easily recovered by traversing the chain of suffix pointers at the very end of the construction.

The second query can be also easily answered in constant time after a linear-time preprocessing of P H(T ). A solution proposed in [START_REF] Ehrenfeucht | Position heaps: A simple and dynamic text indexing data structure[END_REF] consists in traversing P H(T ) depth-first and storing, for each node, its discovery and finishing times [START_REF] Cormen | Introduction to Algorithms[END_REF]. Then node i is an ancestor of node j if and only if the discovery and finishing time of i is respectively smaller and greater than the discovery and finishing time of j.

A more space-efficient solution would be to use a balanced parenthesis representation of the tree topology of P H(T ), taking 2n bits, and link each node to the corresponding opening parenthesis. Then the corresponding closing parenthesis can be retrieved in constant time by the method of [START_REF] Munro | Succinct representation of balanced parentheses and static trees[END_REF] using o(n) auxiliary bits. This allows ancestor queries to be answered in constant time.

The third type of queries is answered by a precomputed function, called maximalreach pointer [START_REF] Ehrenfeucht | Position heaps: A simple and dynamic text indexing data structure[END_REF]: for a position i of T [1..n], define mrp(i) to be the node T [i..i + ℓ], where T [i..i + ℓ] is the longest prefix of T [i..n] represented in P H(T ). Observe first that if i is a secondary position, then mrp(i) = i. This is because a secondary position i is stored in node T [i..n], which trivially corresponds to the longest prefix starting at i. Therefore, as it is done in [START_REF] Ehrenfeucht | Position heaps: A simple and dynamic text indexing data structure[END_REF], mrp can be represented by pointers from node i to node mrp(i) whenever these nodes are different. In our case, we have then to keep in mind that a maximal-reach pointer from a double node applies to the primary position of this node. Figure 4 In [START_REF] Ehrenfeucht | Position heaps: A simple and dynamic text indexing data structure[END_REF], maximal-reach pointers are computed by an extra traversal of P H(T ), using an auxiliary dual heap structure on top of it (see Introduction).

Here we show that maximal-reach pointers can be easily computed using suffix pointers instead of the dual heap. Thus, we completely get rid of the dual heap for constructing the augmented position heap, replacing it with suffix pointers.

We compute mrp(i) iteratively for i = 1, 2, . . . , s -1, where s is the active secondary position of T [1..n]. Assume we have computed mrp(i) for some i and have to compute mrp(i + 1). Assume mrp(i) = T [i..i + ℓ]. It is easily seen that T [i + 1..i + ℓ] is a prefix of the string represented by mrp(i + 1). To compute mrp(k + 1), we follow the suffix link f (mrp(k)) to reach T [i + 1..i + ℓ] and then keep extending the prefix T [i + 1..i + ℓ] as long as it is represented in P H(T ). The resulting pseudo-code is given in Algorithm 2.

Algorithm 2 Linear-time computation of maximal-reach pointers mrp(i) 1: currentnode ← root 2: readhead ← 1 3: for i = 1 to n do currentnode ← f (currentnode) 10: end for It is very easy to see that Algorithm 2 works in time O(n): the while-loop makes exactly n iterations overall, as each iteration increments the readhead counter.

The following property of Algorithm 2 is useful to observe: as soon as readhead gets the value n+1 (line 6), the node currentnode gets assigned to the active node of P H(T [1..n]) (line 9); at the subsequent iterations, the algorithm simply traverses the chain of suffix links and sets the maximal-reach pointer for each secondary position to be the node storing this position (lines 8-9).

Concluding remarks

We proposed a construction algorithm of a position heap of a string, under a modified definition of position heap compared to [START_REF] Ehrenfeucht | Position heaps: A simple and dynamic text indexing data structure[END_REF]. In contrast with the algorithm of [START_REF] Ehrenfeucht | Position heaps: A simple and dynamic text indexing data structure[END_REF] that processes the text right-to-left, our algorithm reads the string left-to-right and has the on-line property. Drawing a parallel to suffix trees, our algorithm can be compared to the Ukkonen's on-line algorithm [START_REF] Ukkonen | On-line construction of suffix-trees[END_REF], while the algorithm of [START_REF] Ehrenfeucht | Position heaps: A simple and dynamic text indexing data structure[END_REF] can be compared to the Weiner's algorithm [START_REF] Weiner | Linear pattern matching algorithm[END_REF]. The similarity of our algorithm to the Ukkonen's algorithm goes beyond this parallel, as the two algorithms are also somewhat analogous in their design.

The O(n) complexity bounds of both Algorithm 1 (Theorem 2) and Algorithm 2 are stated for a constant-size alphabet, otherwise a correcting factor log |A| should be introduced, similarly to the suffix tree construction.

The position heap is a smaller data structure than the suffix tree: it contains exactly n + 1 nodes whereas the suffix tree has n leaves and then up to 2n nodes. Still, the position heap allows for a linear-time string matching. The authors of [START_REF] Ehrenfeucht | Position heaps: A simple and dynamic text indexing data structure[END_REF] proposed algorithms for updating the position heap when the input string undergoes modifications (character insertions/deletions). These algorithms can be easily applied to our definition of position heap. Other interesting applications of position heap are still to be discovered.

It would be interesting to study further the properties of maximal-reach pointers. Note that their structure differs between our definition of position heap and the definition of [START_REF] Ehrenfeucht | Position heaps: A simple and dynamic text indexing data structure[END_REF]. It would be also interesting to exploit the "adaptiveness" of position heaps to substring frequencies, mentioned in Section 3.

Figure 1 :

 1 Figure 1: Sequence hash tree for the set of words shown on the right. Each node stores the rank of the corresponding word in the set.

Figure 2 :

 2 Figure 2: Position heap for string aababbbaabaab. Double nodes store pairs of positions.

  .n]. Lemma 2 implies that all positions of T [1..n] are split into two intervals: primary positions [1..s -1], for some position s, and secondary positions [s..n]. Position s will be called active secondary position, or active position for short. Assume we have constructed the position heap P H(T [1..k]) for some prefix T [1..k] of the input string T [1..n]. Let us analyze the differences between P H(T [1..k])

  led to the creation of a new node. This means that by the time this suffix was inserted into P H(T [1..k]), some prefix T [i..ℓ] of T [i..k], ℓ ≤ k, was not represented in the position heap, which led to the creation of a new node T [i..ℓ] with the minimal such ℓ. This shows that inserting suffixes 1, . . . , s-1 involve completely identical steps in the construction of both P H(T [1..k]) and P H(T [1..k + 1]).The situation is different for the secondary positions s, . . . , k. Each suffix T [i..k] for s ≤ i ≤ k was already represented in P H(T [1..k]) at the moment of its insertion, and then resulted in the addition of the secondary position i to the node T [i..k]. When inserting the corresponding suffix T [i..k + 1] into the position heap P H(T [1..k + 1]), two cases arise. In the first case, inserting the suffix T [i..k + 1] leads to the creation of the new node T [i..k + 1] if this node does not exist yet. Position i then becomes the primary position of this new node. Observe that this only occurs when P H(T [1..k]) does not contain an T [k + 1]-edge outgoing from the node T [i..k]. It is easily seen that such an edge cannot appear by the time of insertion of T [i..k + 1] into P H(T [1..k + 1]) if it is not already present in P H(T [1..k]). In the second case, node T [i..k] has an outgoing T [k + 1]-edge in P H(T [1..k]), and in the construction of P H(T [1..k + 1]), the secondary position i stored in this node should be "moved" to the child node T [i..k + 1]. It becomes then the secondary position of this node.Observe now that if for a secondary position i, the corresponding node T [i..k] has an outgoing T [k + 1]-edge, then so does the node T [i + 1..k] storing the secondary position i + 1. This can again be seen from the factorial property of the position heap (Theorem 1(ii)). This shows that the above two cases split the interval of secondary positions [s..k] into two subintervals [s..t -1] and [t..k], such that node T [i..k] does not have an outgoing T [k + 1]-edge for i ∈ [s..t -1] and does have such an edge for i ∈ [t..k]. The above discussion is summarized in the following lemma specifying the changes that have to be made to transform P H(T [1..k]) into P H(T [1..k + 1]). Lemma 3 Given T [1..n], consider P H(T [1..k]) for k < n. Let s be the active secondary position, stored in the node T [s..k]. Let t ≥ s be the smallest position such that node T [t..k] has an outgoing T [k+1]-transition. To obtain P H(T [1..k+1]), P H(T [1..k]) should be modified in the following way: (i) for every node T [i..k], s ≤ i ≤ t -1, create a new child linked to T [i..k] by a T [k + 1]-edge. Delete secondary position i from the node T [i..k] and assign it as a primary position to the new node T [i..k + 1], (ii) for every node T [i..k], i ≥ t, move the secondary position i from node T [i..k] to node T [i..k + 1].

  shows the position heap of Figure2supplemented by suffix pointers.

Figure 3 :

 3 Figure 3: Position heap for string aababbbaabaab with suffix pointers (dotted arrows). Secondary positions are shown in italic.

Lemma 4

 4 Consider P H(T [1..k]) and let s be the active position, and t ≥ s be the smallest position such that node T [t..k] has an outgoing T [k + 1]-edge. Then node T [t..k + 1] is the active node of P H(T [1..k + 1]). Proof: As it follows from Lemma 3, t is the largest secondary position of T [1..k+1]. Algorithm 1 provides a pseudo-code of the algorithm. The correctness of Algorithm 1 follows from Lemmas 3, 4 and the discussion above. It is instructive, in addition, to observe the following: Algorithm 1 On-line construction of the position heap P H(T [1..n]) 1: create states root and ⊥ 2: f (root ) ←⊥ 3: for all a ∈ A do 4: set an a-edge from ⊥ to root 5: end for 6: currentnode ← root 7: currentsuffix ← 1 8: for i = 1 to n do 9: lastcreatednode ← undefined 10: while currentnode does not have an outgoing T [i]-edge do 11: create a new node newnode pointing to currentsuffix 12: set a T [i]-edge from currentnode to newnode 13: if lastcreatednode = undefined then move currentnode to the target node of the outgoing T [i]-edge 21: if lastcreatednode = undefined then 22: f (lastcreatednode) ← currentnode 23: end if 24: end for • it is easily seen that the suffix pointers of T [1..k + 1] are correctly updated. Indeed, the algorithm assigns to T [i..k + 1] a suffix pointer to T [i + 1..k + 1] which is obviously correct. Note that for the active position s of T [1..k], the created node T [s..k + 1] does not get pointed to by any suffix pointer, which is correct, as T [s -1..k + 1] is not represented in P H(T [1..k + 1]): the position s -1 is primary in T [1..k] and therefore the node T [s -1..k], if it exists in P H(T [1..k]), does not get extended by a T [k + 1]-edge (cf Lemma 3).

Figure 4 :

 4 Figure 4: Position heap for string aababbbaabaab with suffix pointers and maximalreach pointers mrp (double arrows). Only values for which mrp(i) = i are shown, namely mrp(1) = 11, mrp(8) = 11, mrp(2) = 9, mrp(3) = 7, mrp(7) = 10. Note that maximal reach pointers outgoing from double nodes are unambiguous as for all secondary positions i, we have mrp(i) = i.

4 :

 4 while currentnode has an outgoing T [readhead ]-edge and readhead ≤ n do 5: move currentnode to the target node of the outgoing T [readhead ]-edge

This definition agrees with the definition of[START_REF] Coffman | File structures using hash functions[END_REF] but is slightly different from that of[START_REF] Ehrenfeucht | Position heaps: A simple and dynamic text indexing data structure[END_REF] which defines the root to store w 1 . The difference is insignificant, however.