Two sequences of integers x and z of the same length m 2 are shape-isomorphic if, up to a positive proportional factor, the sequences of the distances between consecutive elements of x and z are the same, i.e., if for some > 0 one has x[i + 1] x[i] = (z[i + 1] z[i]), for each 1 i m 1. In this paper we present two linear-time algorithms which, given a text y and a pattern x over an integer alphabet, nds all the factors of y that are shape-isomorphic to x. Our rst solution is a two steps algorithm based on a reduction to the standard exact string matching problem, while our second solution is an online algorithm based on the well-known Knuth-Morris-Pratt string matching algorithm. We call this problem shape-preserving pattern-matching problem.
Given a pattern x of length m and a text y of length n, both over a common alphabet , the exact string matching problem consists in nding all occurrences of the string x in y. String matching is a very important subject in the wider domain of text processing. Algorithmic solutions for it, both in its exact and approximation versions, are basic components of the implementations of practical softwares available under most operating systems.
Among the di erent approximation variants of the string matching problem,
the order-preserving pattern-matching problem [
The rst solution to the OPPM problem was presented by Kubica et al. [
However, for applications such as time series analysis, weather data analysis, music melody matching, etc., OPPM is not adequate, as order-occurrences do not retain enough information to catch up the shape features of interest. Consider for instance the sequences shown in Fig. 1, where y may represent the price variation of some goods throughout a period of time. In this context, the pattern x = h8; 6; 4; 7i could be interpreted as follows: when the price decreases twice the same amount , then one expects a subsequent increase of the price of 23 . Observe that the given pattern has two order-occurrences in y, the rst one at position 4 and the second one at position 11. However, despite of the fact that x and h18; 12; 11; 13i share the same relative order, the two sequences are far from being similar. On the other hand, the second occurrence, h22; 18; 14; 20i, perfectly catches up the features of the pattern x.
In this paper we shall consider a restricted variant of the OPPM problem, that we call shape-preserving pattern-matching problem.
We say that two non-constant strings x and z of the same length m 2, over an integer alphabet = f1; 2; : : : ; g,1 are shape-isomorphic if, for some positive factor > 0, we have x[i+1] x[i] = (z[i+1] z[i]), for 1 i m 1. Concerning constant strings of the same length, we agree that they are shape-isomorphic with proportionality factor = 0. Then, the shape-preserving pattern-matching 1 For notational convenience, we shall restrict our presentation to integer alphabets of the form = f1; 2; : : : ; g only. However, all our considerations can be immediately generalized to any nite linearly ordered alphabet, by just identifying each character with its position in the alphabet. problem (SPPM, for short) is the problem of nding all the factors of a given text y that are shape-isomorphic to a given pattern x, where x and y are strings over an integer alphabet.
We observe that in many practical cases a xed ratio of proportionality is rare, thus a more practical approach would be to consider an approximate version of the problem or allowing the ratios to belong to some bounded interval. However the restricted problem accounted in this paper is a rst step towards a more suitable method for comparing two numeric strings.
Speci cally we shall provide two linear-time algorithms for the SPPM problem, based on (1) a reduction to the exact string matching problem and (2) on a simple, yet non trivial, modi cation of the Knuth-Morris-Pratt algorithm.
The paper is organized as follows. In Section 2, after some preliminary notions, we formally de ne the concept of shape-isomorphism, and state some of its properties. Then in Section 3 we present a linear-time algorithm for the SPPM problem based on a simple reduction to the exact string matching problem, while in Section 4 we present a linear-time KMP based algorithm, proving also its correctness. We draw our conclusions in Section 5. 2
Let = f1; 2; : : : ; g be a nite integer alphabet of size . A string x over is a sequence of elements in . We denote by jxj the length of x and by x[i], for 1 i jxj, the i-th element of x. In addition, for 1 i j jxj, we denote by x[i :: j] the substring of x of length (j i + 1), starting with the element of x at position i and ending with the element of x at position j. By x:y we denote the concatenation of x and y. We write + for the collection of all nonnull nite strings over .
Two sequences x; y 2 + of the same length are said to be order-isomorphic if their elements have the same relative order. More formally, we have: De nition 1 (Order-Isomorphism). Two sequences x; y 2 + of the same length are order-isomorphic, and we write x y, if the following condition holds: x[i] x[j] if and only if y[i] y[j] , for 1 i; j jxj : It is immediate to check that order-isomorphism is an equivalence relation.
We say that two sequences x; y 2 + of the same length m 2 are shapeisomorphic if, up to a positive factor, the sequences of the distances between consecutive elements of x and y are the same. We also agree that any two sequences of length 1 are always regarded as shape-isomorphic. More formally, we have: De nition 2 (Shape-Isomorphism). Two non-constant sequences x; y 2 + of the same length m 2 are said to be shape-isomorphic with proportionality factor > 0 (or, more simply, -isomorphic), and we write x y, if the following condition holds: x[i + 1] x[i] = (y[i + 1] y[i]), for all 1 i m 1 . If x; y 2 + are constant sequences of the same length m 1, we agree that they are shape-isomorphic with proportionality factor = 0, and write x 0 y. We say that two sequences x; y 2 + are shape-isomorphic, and write x y, if they are -isomorphic, for some factor 0.
The following lemma lists some very elementary facts concerning shape- and order-isomorphism. In particular, it states that shape-isomorphism is a hereditary equivalence relation which is ner than order-isomorphism.
Lemma 1. Let x; y; z 2 +, where 0. Then the following properties hold: = f1; 2; : : : ; g, and let > 0 and 1; 2 (a) either x 0 x or x 1 x (b) if x y, then y 1 x; (c) if x 1 y and y 2 z, then x 1 2 z; (d) if x 1 y, then either x[i :: j] 1 y[i :: j] or x[i :: j] 0 y[i :: j], for all 1 i j jxj 1; (e) is an equivalence relation over +; (f ) if x y, then x y, i.e., shape-isomorphism is ner than order-isomorphism; (g) if x y, then x[i :: j] y[i :: j], for all 1 i j jxj 1, i.e., shapeisomorphism is hereditary on substrings.
By exploiting the characterization contained in the following straightforward lemma, one can easily test in linear time whether two given sequences of the same length are shape-isomorphic.
Lemma 2. Let x; z 2 + be two sequences of the same length m. Then x z if and only if either x and z are both constant sequences, or x z, where = xz[[ii++11]] zx[[ii]] , for any 1 i m 1 such that z[i] 6= z[i + 1]. 2.1
The Shape-Preserving Pattern-Matching Problem Next, we formally de ne the shape-preserving pattern-matching problem. De nition 3 (Shape-Preserving Pattern-Matching Problem). Let x; y 2 +, where = f1; 2; : : : ; g, be sequences of length m and n, respectively, such that m n. The shape-preserving pattern-matching problem consists in nding all shape-occurrences of x in y, namely all positions 1 i n m + 1 such that y[i :: i + m 1] x. In this context, x is the pattern and y is the text.
By Lemma 1(f), any algorithm for the OPPM problem can be used as a lter to locate all candidate shape-occurrences of a pattern x in a text y. When an order-occurrence of x is found in y, a O(jxj)-time veri cation procedure based on Lemma 2 can be run to check whether such an order-occurrence is shapeisomorphic to x. Since, for a pattern of length m and a text of length n, the OPPM problem can be solved in time O(n), the algorithm just outlined for the SPPM problem will run in O(n + km)-time, where k is the number of orderoccurrences of x in y.
In the next sections we present two linear algorithms for the SPPM problem. Our rst solution, presented in Section 3, is a two steps algorithm based on a reduction of the SPPM problem to the standard exact string matching problem. Our second solution, presented in Section 4, is a single step algorithm modeled after the well-known Knuth-Morris-Pratt algorithm, whose running time does not dependent on the number of order-occurrences. 3
In this section we present a rst linear algorithms for solving the SPPM problem. Our solution is straightforward and assume that the proportionality ratio between the pattern and its occurrence in the text is a xed constant 0. We observe that in this case the problem can be easily reduced, after some suitable transformations of the input strings, to the ordinary string matching problem. To begin we give some additional de nitions.
De nition 4 (Delta Function). The Delta Function () is the fucntion which associates a given input string x with the corresponding sequence of the di erences between adjacent characters in x. Formally, for a given string x 2 , with jxj = m, we de ne (x) as the numeric sequence of length jxj 1 such that, for 1 i m 1, (x)[i] := x[i + 1] x[i].
De nition 5 (Last Non-Zero Function). The last non-zero function () is the function which associates a given input string x with the sequence of the last non zero element up to each position of x. Formally, for a given string x 2 , with jxj = m, we have that (x) is a sequence of length m 1, such that, for 1 i m 1, (x)[i] := x[j] where j = max(f1
h < i + 1 : x[h] 6= 0g [ f0g)
Observe that (x)[
De nition 6 (Ratios Function). The ratios-function () is the function which associates a given input string x with the sequence of the ratios between its (almost) adjacent characters. Formally, for a string x 2 of length jxj = m we have, for 1 i m 1 (x)[i] := x[i + 1]
(x)[i]
Our algorithm is based on a reduction of the SPPM problem to the exact string matching problem. Such reduction is inspired by the following straightforward technical lemmas. Speci cally the following elementary Lemma 3 describes how to compute shape-isomorphic occurrences for a constant string, while Lemma 5 describes how to compute shape-isomorphic occurrences for a non-constant string.
Lemma 3. Let x be a constant string of length m and let y be a text of length n, both strings over the same alphabet . Then we have that x has a shapeisomorphic occurrence at position i of the text, i.e. x y[i::i + m 1], if and only if (x)[j] = (y)[i + j] for 1 j m 1.
Lemma 4. Let x and y be two non constant strings over the same alphabet ,
with jxj = jyj = m and such that x y with a proportionality factor > 0.
Then we have that ( (x))[i] = ( (y))[i], for all 1 i < m 1.
Lemma 5. Le x and y be two strings of length m > 2 over the same alphabet
, and assume x[
Based on Lemma 5, Algorithm1 depicted in Fig.4 nds all shape-isomorphic
occurrences of a given pattern x of length m in a given text y of length n.
During the preprocessing phase the algorithm performs a partition of the pattern x
into two strings, x1 and x2, where x1 is the constant pre x of the pattern with
maximal length, while x2 is the su x of the pattern with maximal length such
that x2[
More formally we compute an index k, such that
k = max(fj : j > 0 and x[j] 6= x[j + 1]g [ f0g); and set x1 = x[1 : : : k] and x2 = x[k : : : m]. The value of k can be computed in linear time in the size of x.
In a rst step the algorithm computes all shape-isomorphic occurrences of x1 in y. Since x1 is a constant sequence all such occurrences are simply computed (based on Lemma 3) by running a linear exact string matching algorithm in order to search (y) for all occurrences of (x1). We indicate with 1 the set of such occurrences. In the event that jx1j = 1 we skip this step and set 1 = fi : 1 i n mg.
In a second step the algorithm searches for all shape-isomorphic occurrences of x2 in y by running (based on Lemma 5) a linear exact string matching algorithm in order to search ( (y)) for all occurrences of ( (x2)). We indicate with 2 the set of such occurrences. In the event that jx2j < 2 we skip this step and set 2 = fi : 1 i n mg.
The last step of the algorithm the two sets of occurrences 1 and 2 are
combined in order to nd the set of all positions i such that x y[i::i + m 1].
We keep out from 2 all values i such that (x)[
( (y)); k + 2) 2 1) then output(i k + 2);
If we use a linear worst case time exact string matching algorithm for the two steps, then it is trivial to observe that Algorithm1 achieves an O(n + m) worst case time complexity. Observe, however, that the last step of the algorithm depends on the number of occurrences of x1 and x2, which is always bounded by O(n). 4
The Knuth-Morris-Pratt algorithm [
Much in the same way, for the SPPM problem of our interest we shall use a shape-border table, which associates to each position i of a given pattern x the length of the longest proper su x of x[1 :: i] that is shape-isomorphic to a pre x of x[1 :: i].
The shape-border table for a nite integer sequence x is de ned as follows. De nition 7 (Shape-Border Table). Let x be an integer sequence of length m 1. The shape-border table for x is the map x : f0; 1; : : : ; mg ! N de ned by x[i] =Def max j : 1 j < i and x[1 :: j] x[i j + 1 :: i] [ f0g : Plainly, for 2 i m, we have 1 x[i] < i and x 1 :: x[i] x i x[i]+1 :: i . The latter relationship allows us to readily de ne a related proportionality factor map %x : f2; 3; : : : ; mg ! N such that, for 2 i m, x 1 :: x[i] %x[i] x i x[i] + 1 :: i :
(1) Let 1
i < m and let When the sequence x is understood from the context, we shall simply write and % in place of x and %x.
Using the notation ( )j for map iteration,2 by induction (1) generalizes to
x 1 :: j [i]
for all j 1 such that j 1[i] 2. We also notice that since [i] < i (for
2 i m) and [
Next we show that the shape-border table satis es the following recursive relation, for 1 i < m, which, together with (2), will yield to a linear algorithm for computing : [i + 1] = maxn j [i] + 1 : x 1 :: j [i] + 1 j 1 x i j [i] + 1 :: i + 1 o: (3) Ai =Def j [i] + 1 : j 1 and x 1 :: j [i] + 1 x i j [i] + 1 :: i + 1 : By the very de nition of , it follows easily that max Ai [i + 1] [i] + 1. Thus, to prove the correctness of (3), it is enough to show that [i + 1] 2 Ai, which we do as follows. If [i + 1] = 1, then we plainly have [i + 1] 2 Ai. Thus, let us assume that [i + 1] 2. If [i + 1] = [i] + 1, we are done; otherwise, let j be the largest index j 1 such that [i + 1] 1 < j [i], so that j+1[i] By (2) x 1 :: j [i] x i j [i] + 1 :: i , and since x 1 :: [i + 1] 1 x i [i + 1] + 2 :: i and we have [i + 1] 1 < j [i], by the hereditarity and transitivity of shape-isomorphism it follows that x[1 :: [i + 1] 1] is shape-isomorphic to a proper su x of x[1 :: j [i]]. Hence, [i + 1] 1 j+1[i] which, by (4), implies [i + 1] = j+1[i] + 1, proving that [i + 1] 2 Ai, and in turn completing the proof of correctness of (3).
From (3), [i + 1] = ji [i] + 1 [i] ji + 2, where ji is the smallest j 1
such that x 1 :: j [i] + 1 x i j [i] + 1 :: i + 1 . Thus, to compute [i + 1], it
is enough to test the latter condition ji times, yielding a linear number of tests
in m = jxj, since
m 1
X ji
i=1
m 1
X
i=1
[i]
[i + 1] + 2 = [
If the values of the proportionality factor map % are also tabulated during the computation of the shape-border table , it is possible to make each of the tests x 1 :: j [i] + 1 x i j [i] + 1 :: i + 1 ; (5) for j = 1; 2; : : : ; ji, in constant time by means of the following procedure call ExtShapeIso x 1 :: j [i] ; x i j [i] + 1 :: i ; x j [i] + 1 ; x[i + 1]; %[ j 1[i]] (cf. Fig. 4). If the condition (5) is true, then such a call will return the proportionality factor %[i + 1] of (5), otherwise it will return the value 1.
The above considerations leads to the O(m)-time procedure Compute-ShapeBorder-Table reported in Fig. 4 for computing the shape-border table and the proportional factor map for a pattern x of length m. Table 1 reports the shape-border table and the proportionality factor map for the pattern x = h4; 2; 10; 6; 22; 14; 13; 17i.
Much in the style of the Knuth-Morris-Pratt algorithm, we show next how to nd all shape-occurrences of a pattern x (of length m) in a text y (of length n, with n m) in time O(n), using the shape-border table and the proportionality factor map for x. The complete algorithm, called Algorithm2, is reported in Fig. 5. Line references in the following discussion are intended to point out to its pseudo-code, even if not explicitly stated.
Let us assume that it is known that x[1 :: j] y[i :: i + j 1] holds, for some 0, i n m, and j m, and that no further progress in the search for a shape-occurrence of x at position i in y is possible. This means that either j = m, in which case a shape-occurrence of x at position i in y has been found (cf. line 9), or j < m and x[1 :: j + 1] 6 y[i :: i + j]. In any case, one needs to examine a new position i0 > i to nd a (new) shape-occurrence of x. We claim that if ` > i is any position in y of a shape-occurrence of x, then ` i + j [j], so that it is safe to move to position i0 = i + j [j] (cf. line 11). Indeed, if ` < i + j [j], then x[1 :: i + j `] y[` :: i + j 1], so that, by the hereditarity and transitivity of shape-isomorphism, we would have x[1 :: i + j `] x[` i + 1 :: j]. Hence, by the very de nition of [j], it would follow that i + j ` [j], a contradiction.
Notice that once we move to position i0 = i + j [j] in y, we already know that x[1 :: [j]] y[i + j [j] :: i + j 1] (for some proportionality factor; see below). Hence, the matching phase relative to position i0 does not need to reconsider again the positions from 1 to [j] of the pattern x and related positions from i0 to i0 + [j] 1 of the text y (cf. line 11). However, to execute e ciently the matching phase by repeated calls to the procedure ExtShapeIso in Fig. 4 (cf. line 5), at each step (even at the rst one) one needs to know the proportionality factor of the shape-isomorphic substrings which have been matched so far. From the initial assumption x[1 :: j] y[i :: i + j 1], we can infer that x[1 :: [j]] y[i+j [j] :: i+j 1] holds only when x[1 :: [j]] is not a constant sequence. Otherwise, we would have x[1 :: [j]] 0 y[i+j [j] :: i+j 1]. Plainly, x[1 :: [j]] is a constant sequence if and only if %[j] = 0 (cf. line 10). Finally, we point out that the procedure ExtShapeIso, called at line 5, not only allows one to make progress in the matching phase, but it also takes care of updating, if needed, the proportionality factor .
The above discussion highlighted the key points needed in a more formal proof of the correctness of the Algorithm2 in Fig. 5 for the SPPM problem. Complexity issues Next we show that the overall time complexity of the while-loop at lines 3{11 of Algorithm2 is O(n), where, as usual, n is the size of the text. Since, as already shown, the call to procedure Compute-Shape-Border-Table at line 1 takes O(m) time, where, again, m is the size of the pattern, and since m n, it will follow that the total time complexity of Algorithm2 is O(n).
Plainly, the time complexity of the while-loop at lines 3{11 is dominated by the number N of calls to procedure ExtShapeIso at line 5 (each of which takes constant time). Let us associate to each such a call
ExtShapeIso x[1 :: j]; y[i :: i + j Algorithm2(x; y) 1. ( ; %) Compute-Shape-Border-Table(x) 2. i 1; j 1; 0; 3. while i jyj jxj do 4. repeat 5. 0 6. if 0 7. 8. 9. 10. 11.
ExtShapeIso x[1 :: j]; y[i :: i + j
0 then j j + 1; 0; until j = jxj or 0 = 1; if j = jxj then write i; //a shape-occurrence has been found if %[j] = 0 then 0; i i + j [j]; j [j]; the pair (i; j) of the values of the parameters i and j when the call is made, and form their sequence (i1; j1); (i2; j2); : : : ; (iN ; jN ); (6) following the same ordering of the calls (so that (i1; j1) = (1; 1)).
By a simple inspection of the pseudo-code of Algorithm2, it is easy to see that the sequence (6) enjoys the following two properties: (a) i1 + j1 i2 + j2 iN + jN n; (b) j` 1, for all 1 ` N .
To ease presentation, let us refer to any pair h(i; j); (i0; j0)i of consecutive pairs (i; j), (i0; j0) in (6) as a transition, and distinguish between increasing transitions, when j0 = j + 1, and decreasing transitions, when j0 < j. Let I and D be, respectively, the number of increasing and of decreasing transitions in (6). We plainly have N = I + D + 1, as any transition is either increasing or decreasing. In addition, since j1 = 1, we have D I, so that N 2D+1. Finally, for any increasing transition h(i; j); (i0; j0)i, we have 2 i + j < i0 + j0 n, so that I n 2. From the latter inequality, we obtain N 2n 3, yielding the linear bound O(n) seeked for for the time complexity of our Algorithm2. 5
In this paper we introduced a restricted variant of the Order Preserving Pattern Matching problem, called Shape Preserving Pattern Matching. Speci cally we say that two non-constant strings x and z of the same length m 2 are shapeisomorphic if, for some positive factor > 0, we have x[i + 1] x[i] = (z[i + 1) z[i]), for 1 i m 1. In most practical applications this restricted variant turns out to be more e ective then the original problem. We also provided two linear-time algorithms for such problem, based on a simple, yet non trivial, modi cation of the Knuth-Morris-Pratt algorithm.
Although a xed ratio between two sequences is rare in practice, this paper presents a rst step towards a more suitable way to compare two numeric sequences. A more practical approach would be considering a k-approximate version of the problem or allowing the ratios to belong to some bounded interval. Moreover, we are also interested to extend the dependency of di erences in the occurrence from the di erences in the pattern not only for a linear function but also for an arbitrary function.