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

Yakov Nekrich
email: yakov.nekrich@googlemail.com

Tatiana Starikovskaya
email: tat.starikovskaya@gmail.com

Computing Discriminating and Generic Words

We study the following three problems of computing generic or discriminating words for a given collection of documents. Given a pattern P and a threshold d, we want to report (i) all longest extensions of P which occur in at least d documents, (ii) all shortest extensions of P which occur in less than d documents, and (iii) all shortest extensions of P which occur only in d selected documents. For these problems, we propose efficient algorithms based on suffix trees and using advanced data structure techniques. For problem (i), we propose an optimal solution with constant running time per output word.

Introduction

Many text processing applications raise different variants of the following problem: given a collection of sequences, that we call documents, one wants to compute words (strings) that occur in a certain subset of these documents only, and therefore discriminate these documents against the others. Such words are called discriminating or distinguishing for the corresponding set of documents. A complementary problem is to compute words that are common to a selected subset of documents. Such words are called generic or characteristic for the corresponding subset.

In computational biology, for example, identifying words occurring exclusively in the genomic sequence of one species (or a family of species) is of interest (see e.g. [START_REF] Fadiel | Remarkable sequence signatures in archaeal genomes[END_REF]). Words common to a subset of biologically related DNA sequences (and preferably not occurring in other sequences under consideration) often carry a biological function related, in particular, to regulation, repair or evolutionary mechanisms. As a prominent illustration, the problem of identifying genomic words occurring in a given collection of upstream sequences of orthologous genes and absent in a set of upstream sequences of unrelated genes is one of the classical problems in computational biology [START_REF] Tompa | Assessing computational tools for the discovery of transcription factor binding sites[END_REF]. Other applications include the identification of genomic markers, or probe design for DNA microarrays. Besides computational biology applications, many methods of automated text categorization and text mining are based on discriminating and generic words.

In this paper, we study three problems related to discriminating and generic words. In all of them, we will be looking for strings which are extensions of a given pattern P (which may be the empty word), i.e. for strings which have P as a prefix. Assume we are given a collection of strings (documents) T 1 , T 2 , . . . , T m of total length n.

The first problem is to compute all maximal generic words: given a pattern P and a threshold d ≤ m, we want to report all maximal extensions P of P occurring in at least d distinct documents. Maximal here means that any extension of P should occurs in less than d documents.

In the second problem, called minimal discriminating words, we need to report, given a pattern P and a threshold d ≤ m, all extensions P of P which occur in at most d documents and which are minimal, i.e. any prefix of P occurs in more than d documents.

Finally, the third problem computes all the minimal extensions P of P which occur only in documents within a given subset T i 1 , T i 2 , . . . , T i d . Minimality condition means that any prefix of P must occur in documents other than T i 1 , . . . , T i d .

As an example, consider T 1 = ababa, T 2 = aabbba, T 3 = bbabcb. The maximal generic words for d = 2 (and P = ε) are ab, bab and bba. Note that ab occurs in the three strings, but any of its extensions occurs in one string only. Minimal discriminating extensions of P = b for d = 2 are bab and bb, where bab discriminates {T 1 , T 3 } and bb discriminates {T 2 , T 3 }.

We are primarily interested in linear-space solutions to our problems. All our solutions are based on the generalized suffix tree of T 1 , T 2 , . . . , T m , denoted GST , that can be viewed as the suffix tree for the string T 1 $ 1 T 2 $ 2 . . . T m $ m . A leaf in the generalized suffix tree is associated with a suffix of some document T i together with the index i of this document. It is well-known that GST can be computed in O(n) time.

A summary of our results is as follows. For the first problem we propose a solution with the optimal time bound O(|P | + output), based on a result for a variant of the orthogonal range reporting problem. Hereafter, output denotes the number of reported words. We consider a special type of three-dimensional orthogonal range queries over a set S of points (x, y, z) such that 1 ≤ x ≤ |S| and 1 ≤ y, z ≤ log n, i.e. two of the three coordinates are logarithmically bounded in n. We call it the extended one-dimensional range reporting. For this case, we show that a range query

Q = [a, b] × [0, c] × [0, d] can be answered in optimal time O(1 + npoints),
where npoints is the number of reported points, using a data structure of O(|S|) space and a universal table of o(n) space.

For the second problem, we propose a solution with running time O(|P | + log log n + output). The solution is based on a reduction to a problem from computational geometry. For the third problem, we propose a solution with time complexity

O(|P | + d log log m • (1 + output)).
To obtain this, we consider a special variant of weighted ancestor queries problem, to which we propose an optimal solution inspired by the one proposed in [START_REF] Kucherov | Cross-document pattern matching[END_REF] for a similar problem.

It is important to note that all our algorithms output the resulting words by reporting their loci in GST , rather then spelling the words themselves. This is because the latter may cost up to Ω(n 2 ) time, which is prohibitive, while the number of loci is obviously O(n). On the other hand, an enumeration of the set of loci may be sufficient for many applications (possibly as a basis for further analysis, see, e.g., [START_REF] Kucherov | Cross-document pattern matching[END_REF]). Note also that for the second and third problems, the additive term |P | that appears in our complexity bounds comes from locating the locus of P in GST and can be deleted if P itself is specified by its locus in GST .

We assume familiarity with suffix trees. Given a suffix tree, the locus of a string P is defined as the highest explicit node labeled by an extension of P . The string depth of a node is the length of its label. For each node v of the generalized suffix tree GST , we store its weight weight(v) defined as the number of distinct documents whose suffixes occur in the subtree rooted at v. Values weight(v) can be computed in O(n) time [START_REF] Hui | Color set size problem with applications to string matching[END_REF].

Maximal Generic Words

Consider a set of documents T 1 , . . . , T m of total length n. Our first problem problem is to efficiently answer the following queries: given a pattern P and a threshold d ≤ m, enumerate all extensions P of P occurring in at least d documents and such that any extension of P occurs in less than d documents. We seek a solution using O(n) space.

We present our solution in two parts. First, we reduce the solution to a special kind of three-dimensional orthogonal range reporting queries in which two of the three coordinates of the involved points are logarithmically bounded. We call these queries extended one-dimensional range reporting. The data structure supporting these queries will be described separately in the second part.

Main algorithm

For a node u of GST , we denote by maxchild (u) the child node of u with maximum weight. For j ∈ [1..m], we say that a node u is a j-node if weight(u) ≥ j and weight(maxchild (u)) < j. It is easily seen that for a given d, the loci of maximal generic words are precisely the d-nodes.

Consider sets L i for i = 0, 1, . . . , m/s and s = ⌈log n⌉, where L i contains all j-nodes for j ∈ [is + 1..(i + 1)s]. We further define trees T i , i = 0, 1, . . . , m/s. Essentially, T i is a compacted trie on labels of nodes from L i . Nodes of T i are the root of GST , nodes of L i , and all nodes of GST which have at least two children containing a node from L i in their subtrees. We connect nodes u, v with an edge if there is no other node of T i on the path connecting u and v in GST . Furthermore, we label this edge with the string written along this path. Note that T i contains at most 2L i nodes and therefore occupies O(|L i |) space.

For every node u ∈ T i we store its rank preord i (u) in the pre-order traversal of T i , and the range [minord i (u), maxord i (u)] where minord i (u) and maxord i (u) are respectively the minimal and the maximal ranks of nodes in the subtree of T i rooted at u.

For each L i , i = 0, 1, . . . , m/s, we maintain a data structure E i storing a set of three-dimensional points. For every node u of L i , E i contains a point p u , where p u .x = preord i (u), p u .y = min(s, weight(u)i • s), and

p u .z = max(0, weight(maxchild (u)) -i • s).
Observe that x-coordinates of all points in E i are distinct integers bounded by 2|L i |, and that y-and z-coordinates belong to the interval [0, ⌈log n⌉]. E i will be defined in Section 2.2, it takes space O(|L i |).

Computing all maximal generic extensions of a query pattern P is done as follows. First we find the locus of P , denoted v, in the tree T d ′ with d ′ = ⌊d/s⌋ (i.e., the node of T d ′ of minimal depth with the label starting with P ). This takes time O(|P |). Then, we compute all points p u ∈ E d ′ belonging to the three-dimensional range

[minord d ′ (v), maxord d ′ (v)] × [d -d ′ s, s] × [0, d -d ′ s -1]. ( * )
We will show in Section 2.2 how such queries will be answered in time O(1 + output), where output is the number of reported points, on the data structure

E d ′ . A node u is a d-node if and only if p u .y ≥ d -d ′ s and p u .z ≤ d -d ′ s -1.
Therefore, answering the above query provides all the d-nodes located in the subtree rooted at v, that are loci of the desired maximal extensions of P .

To show that the data structures

E i take space O(n) altogether, it is sufficient to show that i |L i | = O(n).
First note that this sum is equal to u∈GST ⌈(weight(u)weight(maxchild (u)))/s⌉ since every node u participates in ⌈weight(u)weight(maxchild (u)))/s⌉ sets L i . On the other hand, u∈GST (weight(u)weight(maxchild (u))) is equal to the total number of j-nodes for all j ∈ [1..m]. Since each j-node has at least j leaves in its subtree and no j-node is an ancestor of another one, the number of j-nodes is at most n/j for any fixed j.

Therefore i |L i | = 1 s m j=1 (n/j) + O(n) = O(n).
We also have to explain how trees T i are constructed. Recall that a node u of GST belongs to L i if weight(maxchild (u)) < (i + 1)s and weight(u) ≥ is + 1. Furthermore, u belongs to T i if either it belongs to L i or the weight of at least two children of u is bigger than (is + 1), which means that u has at least two children each containing a node from L i in its subtree. Therefore, given a node u, each index i of a tree T i that u belongs to is retrieved in constant time. Thus, we can perform one postorder traversal of GST and build all T i , i = 0, 1, . . . , m/s, in time O(n).

Once the trees are built, we need O(n) time to assign the rank preord i (u) and the interval [minord i (u), maxord i (u)] to every node u of every tree T i . Observe also that the label of an edge of T i connecting nodes u, v of GST can be computed in O(1) time if we know string depths of u, v and the label of the last edge on the path connecting u and v in GST . Therefore, edge labels can be computed in O(n) time as well.

We conclude with the final result of Section 2. Its proof follows from the previous discussion, subject to the description of data structures E i that will be given in the next section.

Extended One-Dimensional Range Reporting Queries

We now describe the data structures E i that allow queries ( * ) to be answered in constant time per output point. We reformulate the problem as follows. Suppose that a set S of 3D integer points is given and for each point p ∈ S, we have 1 ≤ p.x ≤ |S| ≤ n, 0 ≤ p.y, p.z ≤ log n. Our goal is to report all points of S within a 3D range

Q = [a, b] × [0, c] × [0, d] in O(|Q ∩ S| + 1) time using space O(|S|)
. Moreover, we will also use a universal look-up table of size o(n) shared by the instances of our data structure (i.e. by different E i ). We assume that all points of S have different x-coordinates, which is the case in our setting. Our approach is similar to the solution of the external memory point location problem from [START_REF] Nekrich | I/O-efficient point location in a set of rectangles[END_REF]. Similar problems for d ≥ 2 dimensions were studied in e.g. [START_REF] Jájá | Space-efficient and fast algorithms for multidimensional dominance reporting and counting[END_REF] We first describe data structures for a small set of points in Proposition 1 and Lemmas 1, 2, that are used in the final result (Lemma 3). Proof. We can assume w.l.o.g. that coordinates of points in S belong to the rank space, i.e., coordinates are integers and 0 ≤ p.x, p.y, p.z ≤ log 2/3 n -1 for all p. If points are arbitrary integers, we can apply the reduction to rank space technique [START_REF] Gabow | Scaling and related techniques for geometry problems[END_REF] and obtain a set of points that satisfies this condition. Answers to all possible queries for all such S are stored in a lookup table. There are less than (3 log 2/3 n) log 2/3 n different sets S, log 8/3 n queries can be asked, and the answer to a query contains O(log

Q = [a, b] × [0, c] × [0, d] in time O(|S ∩ Q| + 1).
Proof. We divide S into blocks W i such that each W i contains ⌊log 2/3 n⌋ points except possibly for the last block that may contain less. For any p i ∈ W i and p j ∈ W j , p j .x > p i .x iff j > i. For every pair 0 ≤ i, j ≤ log 1/3 n, we store the list L ij . If a block W t contains points p such that p.y ≤ i and p.z ≤ j, then L ij contains one representative point p t ∈ W t , p t .y ≤ i and p t .z ≤ j. Let m t denote the minimal x-coordinate of a point p ∈ W t . Since there are O(log 4/3 n) blocks, we can search among m i and find the biggest m i ≤ a for any a in O(1) time using a Q-heap data structure [START_REF] Fredman | Trans-dichotomous algorithms for minimum spanning trees and shortest paths[END_REF]. Furthermore, we can find all points in W t ∩ Q for any query

Q using Proposition 1. Consider a query Q = [a, b] × [0, c] × [0, d].
We find the largest m l ≤ a, the largest m h ≤ b, and report all points in Q ∩ W h and Q ∩ W l . Then we find all points p ∈ L cd such that m l+1 ≤ p.x ≤ m h . For every such p we examine the block W p containing p and report all points from Q∩W p . ⊓ ⊔ Lemma 2. Suppose that for every point p ∈ S, 1 ≤ p.x ≤ log 2 n, 0 ≤ p.y ≤ log n, and 0 ≤ p.z ≤ log n. There exists a data structure that uses

O(|S|) space and a universal table of size o(n) while answering a query

Q = [a, b] × [0, c] × [0, d] in time O(|S ∩ Q| + 1).
Proof. First, we consider the case when p.x ≤ log 2 n, p.y ≤ log n, and p.z ≤ log 1/3 n. Our data structure is a range tree [START_REF] Bentley | Multidimensional divide-and-conquer[END_REF] T y on y-coordinates. Each leaf of T y contains one point and each internal node has log 1/3 n children. Every internal node v ∈ T y contains a data structure F v . For each point p in the range of v, F v contains a point p ′ with coordinates p ′ .x = p.x, p ′ .z = p.z, and p ′ .y = i so that p also belongs to the range of the i-th child v i of v. In other words, the y-coordinate of p is replaced with the index of the child of v that also contains p. F v is implemented according to Lemma 1.

Consider

a query Q = [a, b] × [0, c] × [0, d].
We can find O(1) nodes u 1 , . . . , u t such that some children u 1 i 1 , . . . , u

[i f , j f ] × [0, d] using the data structure F u f .
The case when 1 ≤ p.x ≤ log 2 n, 0 ≤ p.y ≤ log n, and 0 ≤ p.z ≤ log n is handled using the same method. We construct a range tree T on zcoordinates. Each internal node u of T has degree log 1/3 n. Again, we replace the z-coordinate of each point p in the range of u with the index of the child of u that also contains p and then build a tree T u y on those points. Proof. We divide the points into blocks according to their x-coordinates. Each block B k , k = 1, . . . , ⌈|S|/ log 2 n⌉, contains all points p satisfying (k -1)⌈log 2 n⌉ < p.x ≤ k⌈log 2 n⌉. For every block B s and each pair 0 ≤ c, d ≤ log n, we store a pointer to the last block B r , r < s, that contains at least one point p such that p.y ≤ c and p.z ≤ d. Since there are O(log 2 n) pointers in every block, all pointers use linear space. For each 1 ≤ k ≤ ⌈|S|/ log 2 n⌉, we also store a data structure

T k that supports queries [a, b] × [0, c] × [0, d] on points that belong to a block B k ; T k is implemented as described in Lemma 2. To answer a query [a, b] × [0, c] × [0, d],
we report points in B l ∩ Q and B r ∩ Q using T l and T r , where l = ⌈a/ log 2 n⌉ and r = ⌈b/ log 2 n⌉. If r > l + 1, we examine all blocks B i , l < i < r, that contain at least one point p, p.y ≤ c and p.z ≤ d. In every such B i , we report all p ∈ B i ∩Q. Our search procedure visits every block B i such that B i ∩Q = ∅. By Lemma 2, we spend O(|Q ∩ B i | + 1) time in every visited block B i . Every visited B i , except of B l and B r , contains at least one point p ∈ Q. Therefore the total query time is

O( |Q ∩ B i | + 1) = O(|Q ∩ S| + 1).
⊓ ⊔

Minimal Discriminating Words

We now turn to the problem of computing words that discriminate a subset of documents. Given a pattern P and a threshold d ≤ m, we want to find all minimal extensions P of P which occur in at most d distinct documents. "Minimal" here means that no prefix of P satisfies this property. We describe a linear-space data structure for this problem. Consider the generalized suffix tree GST . We start with locating the locus of P in GST in O(|P |) time in the usual way. If v does not exist or weight(v) < then, obviously, P has no desired extensions. Otherwise, we have to find all nodes u in the subtree rooted at v such that weight(u) ≤ d and weight(p(u)) > d, where p(u) is the parent of u. Then, the desired extension of P will be the label of p(u) extended by the first letter of the label of edge (p(u), u).

Unfortunately, applying the solution of Section 2 to this task would take too much space. To illustrate this, let each of the documents T 1 , T 2 , . . . , T m be a distinct letter of the alphabet. Then GST has a root of weight m and n leaves of weight one (here m = n). If we consider j-nodes as nodes of GST such that weight(u) ≤ j ≤ weight(p(u)), then each leave is a j-node for j ∈ [1..m], and, therefore, each set L i , i = 0, 1, . . . , m/ log n, contains all n leaves of GST . That is, the total number of nodes in L i , i = 0, 1, . . . , m/ log n, will be O(nm/ log n).

We then take a different approach and reduce the problem to the orthogonal segment intersection problem.

To each node u of GST , we associate a horizontal segment [weight(u), weight(p(u)) -1] placed on the two-dimensional quarter-plane with y-coordinate preord(u), where preord(u) is the rank of u in the preorder traversal of GST . Furthermore, for each node u, we store minord(u) and maxord(u) which are respectively the minimal and the maximal ranks of nodes of the subtree of GST rooted at u in the preorder sequence of GST . All nodes of the subtree rooted at u appear then in the interval [minord(u), maxord(u)] of the preorder sequence. Let (x s , [y 1 , y 2 ]) denote the vertical segment with endpoints (x s , y 1 ) and (x s , y 2 ). Our problem is then to identify all horizontal segments that intersect with the vertical segment (d, [minord(v), maxord(v)]). These horizontal segments can be found in time O(log log n + output) and space O(n) [START_REF] Chan | Persistent Predecessor Search and Orthogonal Point Location on the Word RAM[END_REF]. Therefore, the following theorem holds.

Discriminating Words for Specified Documents

In Section 3, we showed how to compute words that discriminate d documents from among m documents, without prior knowledge of what these documents are. In many applications, we need to compute words that discriminate documents from a given sample. Consider a set of documents T 1 , . . . , T m . Given a set of indices {i 1 , i 2 , . . . , i d } and a pattern P , we want to find all extensions of P occurring only in documents T i 1 , T i 2 , . . . , T i d and such that any of their prefixes has at least one occurrence in a document which does not belong to this subset.

In this section, we propose a linear space data structure which allows to compute these extensions in time

O(|P | + d log log m • (1 + output)),
where output is the number of such extensions.

We will need the following variant of the weighted level ancestor problem [START_REF] Farach | Perfect hashing for strings: Formalization and algorithms[END_REF]. Given a tree T of size n, assume that each node u of T is assigned a positive integer weight(u) ∈ n O (1) decreasing along every root-to-leaf path: if u is an ancestor of v, then weight(v) ≤ weight(u). The answer to an approximate weighted ancestor query (u, d), for a node u and an integer d ≥ weight(u), is an ancestor w of u satisfying d ≤ weight(w) < 2d.

Lemma 4. T can be stored in a linear space data structure so that approximate weighted ancestor queries on T can be answered in O(1) time.

Proof. The data structure is similar to the one from the proof of Theorem 1 in [START_REF] Kucherov | Cross-document pattern matching[END_REF]. The only difference is that the data structure E(π j ) that finds a predecessor on a path π j is replaced by the structure of [START_REF] Matias | Approximate data structures with applications[END_REF] that answers approximate predecessor queries: for any integer d, we can find a node u ∈ π j such that d ≤ weight(u) < 2d in O(1) time.

⊓ ⊔

We now describe the data structures we use for reporting the minimal extensions for specified documents. Consider the generalized suffix tree GST for T 1 , T 2 , . . . , T m . For each vertex v of GST , we store L(v) and R(v) defined to be the rank of respectively the leftmost and the rightmost leaf in the subtree of v. These ranks can be computed in O(n) time by post-processing GST . Moreover, for each leaf v of GST , we pre-compute its ancestor u of minimal depth such that L(u) = v (u can coincide with v). Finally, we augment GST with a data structure that answers lowest common ancestor queries in constant time [START_REF] Schieber | On finding lowest common ancestors: Simplification and parallelization[END_REF].

Each leaf of GST is associated with a suffix of some document T k and the index k of this document. We store these document indices in an array D, called the document array, such that D[i] = k if the i-th leaf of GST in the left-to-right order corresponds to a suffix coming from T k .

We augment D with two data structures. The first one is an O(n)space data structure that answers queries rank(k, i) (number of entries storing k before position i in D) and select(k, i) (i-th entry from the left storing k). Using the result of [START_REF] Golynski | Rank/select operations on large alphabets: a tool for text indexing[END_REF], we can support such rank and select queries in O(log log m) and O(1) time respectively. The second one is the linear-space data structure from [START_REF] Muthukrishnan | Efficient algorithms for document retrieval problems[END_REF]. It allows us to report all distinct document indices in an interval of D in time O(1) per each output index.

We are now ready to describe the algorithm. We start with locating the locus v of P in GST in time O(|P |) and retrieving the interval [L(v)..R(v)]. Starting from ℓ (0) = L(v), the algorithm will process the interval [ℓ (i) ..R(v)] and compute a desired extension covering the leftmost subrange of suffixes of this interval, then it will iteratively proceed to a smaller interval [ℓ (i+1) ..R(v)], ℓ (i+1) > ℓ (i) .

To process an interval [ℓ (i) ..R(v)], we first check if it contains any of document indices i 1 , i 2 , . . . , i d , and locate the smallest of them as follows. Using d rank queries and d select queries on D we find the minimum rank minrank of any of i 1 , i 2 , . . . , i d in D[ℓ (i) ..R(v)]. This costs O(d log log m) time. If no index of i 1 , i 2 , . . . , i d occurs in D[ℓ (i) ..R(v)], the whole algorithm terminates.

Let s be the leaf of GST with rank minrank . Then the suffix corresponding to this leaf must have a prefix which is an extension we are looking for, whose locus is an ancestor x of s. We will find x in two steps: first, we find the longest interval of D starting at minrank and containing only indices i 1 , i 2 , . . . , i d , and then we will find the highest ancestor of s such that the ranks of all the suffixes in its subtree belong to this interval. This ancestor will be x.

First step. Using approximate weighted ancestor we can find an ancestor u of s such that [START_REF] Muthukrishnan | Efficient algorithms for document retrieval problems[END_REF]. For each of these documents which is not among i 1 , i 2 , . . . , i d , we compute the smallest rank greater than minrank using one rank and one select queries, and then take the minimum of them, denoted minrank ′ . We set minrank ′ = R(u) if D[minrank ..R(u)] contains only indices i 1 , i 2 , . . . , i d . This step takes O(d log log m) time.

[minrank , minrank ′ -1] is the longest segment of D starting at minrank and containing only indices i 1 , i 2 , . . . , i d .

Second step. We now compute x which is the ancestor of s of minimal depth such that (i) L(x) = s, and (ii) R(x) < minrank ′ . We first retrieve the ancestor u ′ of s of minimal depth such that L(u ′ ) = s. Let u ′′ denote the node with greater depth among u and u ′ . If R(u ′′ ) < minrank ′ , then x = u ′′ and we are done. Otherwise, compute the lowest common ancestor w of s and s ′ , where s ′ is the leaf of rank (minrank ′ -1). If R(w) = s ′ , then x = w. Otherwise, x = w 1 , where w 1 is the leftmost child of w. The second step takes O(1) time.

We then proceed to the next iteration with the interval [ℓ (i+1) ..R(v)], where ℓ (i+1) = R(x) + 1. Each iteration takes O(d log log m) time; each iteration, except of possibly the last one, outputs at least one desired locus. This leads to the final result:

Concluding Remarks

Our solution to the first problem (Section 2) is optimal: it takes a linear space and a constant time per output item. It is an interesting question if the second problem can admit an optimal solution too. Improving the bound for the third problem is another interesting direction to study.

Theorem 1 .

 1 For any pattern P and an integer d, the loci of all maximal extensions of P can be found in time O(|P | + output), where output is the number of such extensions. The underlying indexing structure takes O(n) space and can be constructed in O(n) time, where n = |T 1 | + |T 2 | + . . . + |T m |.

Proposition 1 .

 1 If |S| ≤ log 2/3 n, we can store a set S in an O(|S|)space data structure so that for any Q = [a, b] × [0, c] × [0, d] all points in Q ∩ S can be answered in O(|S ∩ Q| + 1) time. The data structure uses a universal lookup table of size o(n).

Lemma 3 .

 3 A query is answered by reducing it to O(1) queries on data structures T u y as described above. ⊓ ⊔ Suppose that for every point p ∈ S, 1 ≤ p.x ≤ |S|, 0 ≤ p.y ≤ log n and 0 ≤ p.z ≤ log n. There exists a data structure that uses O(|S|) space and a universal table of size o(n) and allows queries Q = [a, b] × [0, c] × [0, d] to be answered in time O(|S ∩ Q| + 1).

Theorem 2 .

 2 Given a pattern P and an integer d, the loci of all minimal discriminating extensions of P can be found in time O(|P | + log log n + output). The underlying indexing structure takes O(n) space and can be constructed in O(n log n) time, where n = |T 1 | + |T 2 | + . . . + |T m |.

3 2 d

 2 ≤ weight(u) < 3d in O(1) time. (If u is an ancestor of v, we set u = v.) The interval D[minrank ..R(u)] includes the longest interval starting at minrank which contains only indices i 1 , i 2 , . . . , i d . On the other hand, interval D[minrank ..R(u)] contains indices of less than 3d different documents, and we output these indices in time O(d) using the data structure of

Theorem 3 .

 3 Given a subset of indices {i 1 , i 2 , . . . , i d } and a pattern P , all minimal extensions of P which occur only in the documents T i 1 , T i 2 , . . . , T i d can be computed in time O(|P |+d log log m•(1+output)), where m is the total number of documents. The underlying indexing data structure occupies O(n) space and can be constructed in O(n) time, where n = |T 1 | + |T 2 | + . . . + |T m |.

  2/3 n) points. Therefore the lookup table has o(n) entries and can be stored in o(n) space.

⊓ ⊔ Lemma 1. Suppose that for every point p ∈ S, 1 ≤ p.x ≤ log 2 n, 0 ≤ p.y, p.z ≤ log 1/3 n. There exists a data structure that uses O(|S|) space and a universal table of size o(n) while answering a query

  1 j 1 , . . . , u t it . . . , u t jt of u 1 , . . . , u t respectively cover [0, c]. For every such u f we answer a query [a, b] ×

Acknowledgments: G.Kucherov has been partly supported by the Marie-Curie Intra-European Fellowship for Career Development. T.Starikovskaya has been supported by the mobility grant funded by the French Ministry of Foreign Affairs through the EGIDE agency and by a grant 10-01-93109-CNRS-a of the Russian Foundation for Basic Research. Part of this work has been done during a stay of Y.Nekrich at the Marne-la-Vallée University supported by the BEZOUT grant of the French government.


Damien Roque
email: damien.roque@gipsa-lab.grenoble-inp.fr

Cyrille Siclet
email: cyrille.siclet@gipsa-lab.grenoble-inp.fr

Jean-Marc Brossier
email: jean-marc.brossier@gipsa-lab.grenoble-inp.fr

Pierre Siohan
email: pierre.siohan@orange.com

Weighted Cyclic Prefix OFDM: PAPR Analysis and Performances Comparison with DFT-Precoding

In this paper, we present a weighted cyclic prefix orthogonal frequency-division multiplexing (WCP-OFDM) transceiver as a generalization of traditional cyclic prefix (CP)-OFDM. In time-variant channels, this multicarrier transmission scheme may mitigate inter-channel interference (ICI) thanks to the use of non-rectangular pulse shapes. A precoding step may be required in order to reduce the peak-to-average power ratio (PAPR) at the transmitter output. For instance, a discrete Fourier transform (DFT) precoder leads to a single carrier transmission scheme with frequency domain equalization. We analyze the consequences of such a precoding, in terms of performances, in the context of a time-frequency selective channel.

I. INTRODUCTION

Cyclic prefix orthogonal frequency-division multiplexing (CP-OFDM) diagonalizes multipath time-invariant channels if the guard interval is longer than the channel impulse response. As a consequence, perfect reconstruction may be obtained by means of a single-tap per sub-channel equalizer [START_REF] Wang | Wireless multicarrier communications[END_REF]. Furthermore, the fast Fourier transform (FFT) algorithm ensures a low-complexity implementation. However, the Doppler spread introduced by time-variant channels breaks the orthogonality between sub-channels and inter-carrier interference (ICI) appears [2, p. 753].

Filter bank based multicarrier (FBMC) systems offer a more general transmission framework, providing non-rectangular pulse-shape. The purpose of this approach is to design matched prototype filters to time-frequency selective channels in order to yield better performance results [START_REF] Kozek | Nonorthogonal pulseshapes for multicarrier communications in doubly dispersive channels[END_REF]- [START_REF] Jung | Pulse shaping, localization and the approximate eigenstructure of LTV channels (special paper)[END_REF]. Despite attractive performances, FBMC systems are not yet standardized because of their computational complexity. Indeed, they require the use of polyphase matrix filtering whose complexity increases with the length of the prototype filters [START_REF] Siclet | Application de la théorie des bancs de filtres à l'analyse et à la conception de modulations multiporteuses orthogonales et biorthogonales[END_REF].

In this work, we focus on short prototype filters that ensure a low-complexity implementation. Thus, we consider here the case of filters with the same length as rectangular pulses used in CP-OFDM. The difference with CP-OFDM is that the pulses do not need to be rectangular. Such a generalization of CP-OFDM is referred to as weighted cyclic prefix (WCP)-OFDM.

As a multicarrier transmission scheme, WCP-OFDM is characterized by its high peak-to-average power ratio (PAPR) wich is a major drawback for its hardware implementation.

In this study, we compare the PAPR of CP-OFDM with a time-frequency optimized WCP-OFDM. We also define a DFT-precoding block which leads to a single carrier (SC) block transmission scheme with frequency domain equalization. We compare the performances of both systems with LDPC channel coding and assuming a time-frequency selective channel.

II. WEIGHTED CYCLIC PREFIX OFDM TRANSCEIVER: STRUCTURE AND PERFECT RECONSTRUCTION CONDITIONS

We want to transmit a sequence of complex symbols denoted {c m,n } (m,n)∈Λ where Λ = {0, . . . , M -1} × Z. The symbols are assumed to be independent and identically distributed. Their mean power is denoted σ 2 c = E{|c m,n | 2 }. Each c m,n is placed in the time-frequency plane at coordinates (m/M, nN ) where M is the number of sub-channels and N represents the number of sample per sub-channel symbol period. The oversampling ratio is given by N/M . The transmitted signal can be written

s[k] = (m,n)∈Λ c m,n γ m,n [k], k ∈ Z (1)
where γ m,n [k] is a time-frequency shifted version of the prototype pulse γ[k] defined as

γ m,n [k] = 1 √ M γ[k -nN ]e j2π m M k , γ[k] ∈ R. (2)
And the complex symbols can be estimated thanks to a projection over a demodulation basis γm,n

[k] = 1 √ M γ[k - nN ]e j2π m M k , with γ[k] ∈ R: ĉp,q = (q+1)N -1 k=qN r[k]γ * p,q [k] (3) = 1 √ M (q+1)N -1 k=qN r[k]γ[k -qN ]e -j2π p M k (4)
with r[k] the received signal. The resulting transmission scheme can be efficiently realized thanks to the use of fast alogrithms [START_REF] Roque | Modulations multiporteuses WCP-OFDM : évaluation des performances en environnement radiomobile[END_REF]. This leads to the scheme depicted in fig. 1 in which we have added an optional precoding step (Q block). Thus, this generalizes the CP-OFDM

Q c 0,n c M -1,n IDFT CP γ[0] γ[N -1] P/S H s[k] z[k] S/P r[k] γ[0] γ[N -1] CP -1 DFT EQ ĉ0,n ĉM-1,n Q -1 c0,n cM-1,n
Fig. 1: Efficient implementation of a precoded WCP-OFDM transmultiplexer.

transceiver by allowing non-rectangular pulse shapes while preserving a low-complexity. This transmission scheme is thus referred to as weighted cyclic prefix (WCP)-OFDM. The transmission process consists in a projection of M complex symbols over an exponential basis (IDFT block) after an optional precoding step (Q block). This projection is followed by a cyclic extension of the data block (CP block) defined by the following:

if we denote x[k] the entries of CP block, 0 ≤ k ≤ M -1, and y[k], 0 ≤ k ≤ N -1, its outputs, then we have y[k] = x[2M -N + k] for 0 ≤ k ≤ N -M -1 and y[k] = x[M -N + k] for N -M ≤ k ≤ N -1.
The resulting N samples are weighted by γ

[k], 0 ≤ k ≤ N -1.
At the receiver side, the dual operation is performed in order to ensure perfect reconstruction (PR) of the transmitted symbols, that is to say ĉm

,n = c m,n if r[k] = s[k].
In particular, CP -1 block is defined by the following: if we denote x[k] the entries of the CP -1 block, 0 ≤ k ≤ N -1, and y[k], 0 ≤ k ≤ M -1, its outputs, then we have

y[k] = x[N -M + k] for 0 ≤ k ≤ 2M -N -1 and y[k] = x[k -(2M -N )]+x[p-(M -N )] for 2M -N ≤ k ≤ M -1.
As shown in [?], if the received signal r[k] is equal to the transmitted signal s[k], then the complex symbols {c m,n } (m,n)∈Λ can be exactly reconstructed provided that the following Perfect Reconstruction (PR) conditions are fulfilled:

• γ[k]γ[k]+γ[k+M ]γ[k+M ] = 1 for 0 ≤ k ≤ N -M -1, • γ[k]γ[k] = 1 for N -M ≤ k ≤ N -1.
Through this relation, one may recover the expression of rectangular filters used for CP-OFDM: if γ[k] = 1 for 0 ≤ k ≤ N -1 and 0 otherwise then PR conditions are satisfied when γ[k] = 1 for N -M ≤ k ≤ N -1 and 0 otherwise.

Apart from the cyclic prefix case, PR conditions may be particularized in the linear phase orthogonal case, such that γ

[k] = γ[k] = γ[N -1 -k] [2, p. 160].
In this context, the work presented in [START_REF] Pinchon | Closed-form expressions of optimal short PR FMT prototype filters[END_REF] provides closed-form expressions for optimized prototypes filters. Optimization criteria include time-frequency localization (TFL) maximization (fig. 2).

We have shown in [START_REF] Roque | A performance comparison of FBMC modulation schemes with short perfect reconstruction filters[END_REF] that the TFL filter discussed above outperforms CP-OFDM in several multipath time-variant environments, using a single-tap per sub-channel equalizer. One may notice that WCP-OFDM offers a good trade-off between complexity 1 and ICI mitigation, unlike more general filtered multitone setups [START_REF] Moret | Design of orthogonal filtered multitone modulation systems and comparison among efficient realizations[END_REF].

0 500 1,000 0 0.5 1 Sequence index [k] Amplitude γ CP [k] γ TFL [k] 0 5 10 -60 -40 -20 0 Frequency [M ν] Normalized gain [dB] |Γ CP | 2 |Γ TFL | 2

III. WCP-OFDM AND PAPR ISSUE

Multicarrier modulations are characterized by their high peak-to-average power ratio (PAPR) defined by

PAPR = max 0≤t≤T0 {|s(t)| 2 } 1 T0 T0 0 |s(t)| 2 dt (5)
where -k) with B representing the transmission bandwidth. Linear power amplification is difficult to achieve in presence of high PAPR. As a consequence, the clipping probability may be estimated thanks to the PAPR complementary cumulative distribution function (CCDF): F c (PAPR 0 ) = Pr{PAPR > PAPR 0 }, as presented in figure 3. Since the TFL pulse exhibits a nonconstant impulse response, the overlying transmission scheme experiences a greater PAPR than traditional rectangular filters (CP) [START_REF] Skrzypczak | Analysis of the peak-toaverage power ratio of the oversampled OFDM[END_REF]. In both cases, PAPR is greater than 8 dB.

T 0 = N/B and s(t) = k s[k]sinc(Bt
Many studies focus on PAPR reduction techniques for multicarrier modulations [START_REF] Han | An overview of peak-to-average power ratio reduction techniques for multicarrier transmission[END_REF] (e.g. clipping and filtering, coding, tone reservation, tone injection, selected mapping, interleaving...). However, the techniques listed above may either distort the pulse shapes, require extra transmission power, decrease the spectral efficiency and they often bring prohibitive computational complexity.

A particular precoding technique consists in a simple discrete Fourier transform (DFT) at the transmitter side and an inverse DFT (IDFT) after the equalizer. It results in a single carrier transmission scheme with frequency domain equalization (SC-FDE). Indeed, DFT precoding followed by IDFT leads to an equivalent SC modulation without precoding nor IDFT. CP-OFDM and SC-FDE have been compared in several studies [START_REF] Falconer | Frequency domain equalization for single-carrier broadband wireless systems[END_REF]- [START_REF] Filho | A hybrid single-carrier/multicarrier transmission scheme with power allocation[END_REF]. Obviously, it turns out that SC-FDE has a lower PAPR than CP-OFDM. However, multicarrier modulations allow a per sub-channel bit-loading and power allocation, leading to better throughput than single carrier modulations for a given bit-error-rate (BER). We also notice that CP-OFDM remains sensitive to frequency offsets such as Doppler shifts.

IV. SIMULATIONS : BER PERFORMANCE RESULTS

In this simulation framework, we consider a land mobile transmission system, using a band B = 8, centered around a frequency f c = 1 GHz. We assume that the transmission takes place in an outdoor urban environment. Such a propagation may be fitted by a 6-path WSSUS channel model where the last path occurs at 5 µs (COST 207 TUx6 [START_REF] Failli | COST 207 digital land mobile radio communications[END_REF]) and whose impulse response is truncated to L = 45 coefficients. We develop here two mobility scenarios:

• low speed, with v max = 3 km/h ; • high speed, with v max = 350 km/h. At the transmitter side, the low-density parity check (LDPC) encoder uses 32400 bit codewords and operates at coding rate R c = 3/4. Each codeword is randomly interleaved and split into 8 data blocks of M = 2048 quadrature phase shift keying (QPSK) symbols. The oversampling factor is set to N/M = 5/4 so that a transmitted block is made of N = 2560 symbols. We consider than each block is transmitted over independent channel realizations in order to ensure the best diversity scenario. In practice, symbols should be spaced by a period greater than the coherence time of the channel. In a similar way, sub-channels should be spaced by a band greater than the coherence bandwidth of the channel. Unfortunately, these requirements are usually difficult to achieve, considering various application constraints (e.g. spectral efficiency, interactivity, medium access control).

At the receiver side, a single-tap per sub-channel equalizer is used. After the deinterleaver, a LDPC decoder performs 10 iterations over each codeword without parity check2 . We compare the performances of WCP-OFDM with or without DFT-precoding. In the first case, the transmission system leads to a single carrier (SC) block scheme. In the second case, the system leads to a regular multicarrier (OFDM). For both precoding strategies the transmitter and the receiver are provided with rectangular biorthogonal prototypes (CP) and time-frequency optimized orthogonal prototypes (TFL). Biterror-rate (BER) is plotted as a function of E b /N 0 , where E b = N σ 2 c /2M B and N 0 = σ 2 z /B (fig. 4). First of all, we show that multicarrier schemes obtain better performances results than single carrier schemes (approximately a factor 5 for E b /N 0 = 10 dB), for both low and high mobility scenarios. This result demonstrates that in presence of a random multipath channel, the OFDM technique is useful in order to circumvent the fading phenomenon to a limited number of sub-channels. On the contrary, if the channel experiences fading in a SC system, the whole block is usually lost.

We recall that the oversampling factor leads to N -M ≫ L. As a consequence, cyclic prefix based transmission schemes do not introduce inter-block interference (IBI). However in the orthogonal scenario based on TFL prototypes, IBI remains present.

In the low mobility scenario, regardless of the precoding strategy, we show that the time-frequency localized pulse yields better results than the rectangular pulse. Since the TFL impulse response shows smooth transitions, it justifies a low IBI term and the large number of sub-channel ensures a sufficient partitioning of the band B. As a consequence, the overall interference term is negligible compared to the noise term and the performance curves (fig. 4a) reflect the need of orthogonal signaling in mainly noisy channels. Similar conclusions can be drawn in the high mobility scenario. However Doppler induced inter-carrier interference (ICI) appears and yield lower performances (fig. 4b).

For high values of E b /N 0 , the difference between the BER experienced by CP and TFL pulses tends to increase with the time selectivity of the channel. It confirms the interest of a time-localized pulse in such a scenario.

V. CONCLUSION

Weighted cyclic prefix OFDM systems generalize traditional CP-OFDM, allowing the use of non-rectangular filters. Even if time-frequency localized pulses yields interesting BER performances in time-frequency selective channels, it also introduce a greater PAPR than rectangular pulses, increasing with the oversampling factor. In order to mitigate the PAPR, a DFTprecoding may be used, leading to a single carrier block transmission scheme.

We have shown, through simulation, that best (LDPC coded) BER performance results are achieved by a multicarrier scheme, using TFL pulse, assuming a realistic time-frequency selective channel.

Fig. 2 :

 2 Fig. 2: Time and frequency responses of the prototype filters with Γ(ν) = 1/ γ ∞ N -1 k=0 γ[k] exp(-j2πνk/N ), using M = 1024 and N = 1280.

4 Fig. 3 :

 43 Fig. 3: PAPR CCDF for M = 1024 and N/M ∈ {9/8, 5/4} for cyclic prefix and time-frequency localized pulses in a multicarrier transmission scheme.

  BER performances in low mobility scenario.

  BER performances in high mobility scenario.

Fig. 4 :

 4 Fig. 4: BER performances for two mobility scenarios in a COST 207 TUx6 channel. Comparison between single carrier and multicarrier schemes for M = 2048 and N/M = 5/4.

2N additional multiplications are performed compared to CP-OFDM.

This channel coding configuration (Rc =

3/4, 10 iterations) is chosen in order to achieve a statistically representative simulation with a reasonable computing time.

ACKNOWLEDGMENT

This work has been supported by the French defense procurement agency (DGA) and Orange-Labs. The authors would like to thank D. Pinchon who designed the TFL filter discussed in this article.