A Practical Algorithm to Find the Best Episode
Patterns
Masahiro Hirao, Shunsuke Inenaga, Ayumi Shinohara,
Masayuki Takeda, and Setsuo Arikawa
Department of Informatics, Kyushu University 33, Fukuoka 812-8581, JAPAN{hirao, s-ine, ayumi, takeda, arikawa}@i.kyushu-u.ac.jp

Abstract. Episode pattern is a generalized concept of subsequence pattern where the length of substring containing the subsequence is bounded.
Given two sets of strings, consider an optimization problem to find a best
episode pattern that is common to one set but not common in the otherset. The problem is known to be NP-hard. We give a practical algorithm
to solve it exactly.

1Introduction

In these days, a lot of text data or sequential data are available, and it is quite
important to discover useful rules from these data. Finding a good rule to separate
two given sets, often referred as positive examples and negative examples, is a
critical task in Discovery Science as well as Machine Learning.
In [4], Hirao et al. considered subsequence patterns as rules. A subsequence
pattern s matches with a string t if s can be obtained by deleting zero or morecharacters from t. They introduced a practical algorithm to ﬁnd a best subsequence pattern that separates positive examples from negative examples, andshowed some experimental results. A drawback of subsequence patterns is thatthey are not suitable for classifying long strings over small alphabet, since a
short subsequence pattern matches with almost all long strings.
In this paper, we consider episode patterns, which were originally introducedby Mannila et al. [5]. An episode pattern v, k, where v is a string and k is aninteger, matches with a string t if v is a subsequence for some substring u of twith |u| ≤ k. Episode pattern is a generalization of subsequence pattern sincesubsequence pattern v is equivalent to episode pattern v, ∞. We give a practicalsolution to ﬁnd a best episode pattern which separates a given set of strings
from the other set of strings. We propose a practical implementation of exact
search algorithm that practically avoids exhaustive search. The key idea is tointroduce some heuristics to reduce the search space based on the combinatorialproperties of episode patterns, and to utilize an eﬃcient data structure thathelps to determine whether an episode pattern matches with a ﬁxed string, atthe cost of preprocessing time and space requirement to construct it.

2Preliminaries

Let N be the set of integers. Let Σ be a ﬁnite alphabet, and let Σ ∗ be the setof all strings over Σ. For a string w, we denote by |w| the length of w. For a set
S ⊆ Σ ∗ of strings, we denote by |S| the number of strings in S, and by ||S|| thetotal length of strings in S. We say that a string v is a preﬁx (substring, suﬃx,resp.) of w if w = vy (w = xvy, w = xv, resp.) for some strings x, y ∈ Σ ∗ . We saythat a string v is a subsequence of a string w if v can be obtained by removing
zero or more characters from w. We denote by v str w that v is a substring ofw, and by v seq w that v is a subsequence of w. An episode pattern is a pair ofa string v and an integer k, and we deﬁne the episode language Leps (v, k) byLeps (v, k) = {w ∈ Σ ∗ | ∃ ustr

w such that v

sequ and |u| ≤ k}.

We formulate the problem by following our previous paper [4]. Readers shouldrefer to [4] for basic idea behind this formulation. We say that a function f from[0, xmax] × [0, ymax] to real numbers is conic if– for any 0 ≤ y ≤ ymax , there exists an x1 such that• f(x, y) ≥ f(x , y) for any 0 ≤ x < x ≤ x1 , and• f(x, y) ≤ f(x , y) for any x1 ≤ x < x ≤ xmax .
– for any 0 ≤ x ≤ xmax , there exists a y1 such that• f(x, y) ≥ f(x, y ) for any 0 ≤ y < y ≤ y1 , and• f(x, y) ≤ f(x, y ) for any y1 ≤ y < y ≤ ymax .
We assume that f is conic and can be evaluated in constant time in the sequel.
The following is the optimization problem to be tackled.
Definition 1 (Finding the best episode pattern according to f).
Input Two sets S, T ⊆ Σ ∗ of strings.
Output An episode pattern v, k that maximizes the value f(xv,k , yv,k ),where xv,k = |S ∩ Leps (v, k)| and yv,k = |T ∩ Leps (v, k)|.
We remark that the problem is NP-hard, since it is a generalization of ﬁnding
the best subsequence pattern [4].
From the conicality of function f and the property of episode patterns, wecan prove the following lemmas.
Lemma 1 ([4]). For any 0 ≤ x < x ≤ xmax and 0 ≤ y < y ≤ ymax , we havef(x, y) ≤ max{f(x , y ), f(x , 0), f(0, y ), f(0, 0)}.
Lemma 2. For any two episode patterns v, l and w, k, if v
then Leps (v, l) ⊇ Leps (w, k).

seqw and l ≥ k

By Lemma 1 and 2, we have the next lemma, that plays a key role in ouralgorithm which will be described in Section 4.
Lemma 3. For any two episode patterns v, l and w, k, if v seq w and l ≥ kthen f(xw,k , yw,k ) ≤ max{f(xv,l , yv,l ), f(xv,l , 0), f(0, yv,l), f(0, 0)}.
2b0a1babab2a3aaba4bbb5aba6b7ba8b9aFig. 1. EDASG(t), where t = aabaababb. Solid arrows denote the forward edges, andbroken arrows denote the backward edges.

3Episode Directed Acyclic Subsequence Graphs

We ﬁrst analyze the complexity of episode pattern matching: given an episodepattern v, k and a string t, determine whether t ∈ Leps (v, k) or not. This
problem can be answered by ﬁlling up the edit distance table between v and t,
where only insertion operation with cost one is allowed. It takes Θ(mn) timeand space using a standard dynamic programming method, where m = |v| andn = |t|.
For a ﬁxed string, automata-based approach is useful. We use the EpisodeDirected Acyclic Subsequence Graph (EDASG) for string t, which was recentlyintroduced by Troı́ček in [8]. A Directed Acyclic Subsequence Graph (DASG) [2]for a string t is a ﬁnite automaton that accepts all subsequences of t. An EDASG
is a directed graph which combines two DASGs for t and the reversed string tR . Itcontains two kinds of edges, forward edges corresponding to DASG(t), and backward edges corresponding to DASG(tR ). As an example, EDASG(aabaababb) isshown in Fig. 1. When examining if an episode pattern abb, 4 matches with tor not, we start from the initial state 0 and arrive at state 6, by traversing theforward edges spelling abb. It means that the shortest preﬁx of t that contains
abb as a subsequences is t[0 : 6] = aabaab, where t[i : j] denotes the substring
ti+1 . . . tj of t. Moreover, the diﬀerence between the state numbers 6 and 0 corresponds to the length of matched substring aabaab of t, that is, 6 − 0 = |aabaab|.
Since it exceeds the threshold 4, we move backwards spelling bba and reach state
1. It means that the shortest suﬃx of t[0 : 6] that contains abb as a subsequenceis t[1 : 6] = abaab. Since 6 − 1 > 4, we have to examine other possibilities. It is
not hard to see that we have only to consider the string t[2 : ∗]. Thus we continue the same traversal started from state 2, that is the next state of state 1.
By forward traversal spelling abb, we reach state 8, and then backward traversal
spelling bba bring us to state 4. In this time, we found the matched substringt[4 : 8] = abab which contains the subsequence abb, and the length 8 − 4 = 4
satisﬁes the threshold. Therefore we report the occurrence and terminate theprocedure.
With the use of EDASG(t), episode pattern matching can be answered quickly
in practice, although the worst case behavior is still O(mn). An on-line lineartime algorithm for constructing EDASG(t) for a string t ∈ Σ ∗ was proposedin [8].
3For strings v, t ∈ Σ ∗ , we deﬁne the threshold value θ of v for t by θ = min{k ∈N | t ∈ Leps (v, k)}. If no such value, let θ = ∞. Note that t ∈ Leps (v, k) for
any k < θ, and t ∈ Leps (v, k) for any θ ≤ k. It is not diﬃcult to see that theEDASGs are useful to compute the threshold value of v for a ﬁxed t. We have
only to repeat the above forward and backward traversal up to the end, andreturn the minimum length of the matched substrings.
From now on, for a set S of strings and a string v, we consider the numericaleps
sequence {xk }∞k=0 , where xk = |S ∩ L (v, k)|. It clearly follows from Lemma 2that the sequence is non-decreasing. Moreover, notice that 0 ≤ xk ≤ |S| for any
k, and xl = xl+1 = xl+2 = · · ·, where l is the length of the longest string in S.
It implies that {xk }∞k=0 consists of at most min{|S|, l} distinct values. Hence wecan represent {xk }∞k=0 as a list of pairs (k, xk ) such that xk−1 = xk . The lengthof the list is bounded by min{|S|, l}. We call this list a compact representationof the sequence {xk }∞k=0 (CRS, for short).
We now show how to compute CRS for each v and a ﬁxed S. Observe that xk
increases only at the threshold values of v for some t ∈ S. For each string ti ∈ S,
we compute the threshold value θi of v for ti , and sort these threshold values inincreasing order. From these sorted values, we can construct the CRS in lineartime. To be summarized, if we use the counting sort, we can compute the CRSfor v ∈ Σ ∗ in O(|S|ml + |S|) = O(||S||m) time where m = |v|. We emphasizethat the time complexity of computing the CRS of {xk }∞k=0 is the same as thatof computing xk for a single k (0 ≤ k ≤ ∞), by our method. In the next section,
we use a data structure StringSet which supports the method to compute theCRS for any given string v.

4Algorithm

The basic structure of the algorithm is similar to that in [4].
Fig. 2 shows our algorithm to ﬁnd a best episode pattern from given two setsof strings, according to the function f. Optionally, we can specify the maximum
length of episode patterns by the parameter . Here, we use a data structure
PriorityQueue that supports the following methods.
– bool empty() : return true if the queue is empty.
– void push(string w, double priority) : push a string w into the queue withpriority priority.
– (string, double) pop() : pop and return a pair (string, priority), wherepriority is the highest in the queue.
At line 16 marked by (*), we can simultaneously compute k  and val byusing CRSs x̄ and ȳ in O(|x̄| + |ȳ|) time. By Lemma 3, we can use the value
upperBound to prune branches in the search tree computed at line 20 marked by(**). Note that xv,∞ and yv,∞ can be extracted from x̄ and ȳ in constant time,respectively. The next theorem guarantees the completeness of the algorithm.
Theorem 1. Let S and T be sets of strings, and  be a positive integer. Thealgorithm FindBestEpisode(S, T , ) will return an episode pattern that maxi4

1 string FindBestEpisode(StringSet S, T , int )
2string prefix , v;
3episodePattern maxSeq; /* pair of string and int */4
double upperBound = ∞, maxVal = −∞, val ;5int k ;6CompactRepr x̄, ȳ; /* CRS */7
PriorityQueue queue; /* Best First Search*/
8
queue.push(””, ∞);9while not queue.empty() do10(prefix , upperBound) = queue.pop();11
if upperBound < maxVal then break;
12foreach c ∈ Σ do13v = prefix + c; /* string concatenation */14x̄ = S.crs(v);15ȳ = T .crs(v);
16 (*)k = argmaxk {f (xv,k , yv,k )} and val = f (xv,k , yv,k  );17
if val > maxVal then18
maxVal = val ;19
maxEpisode = v, k ;
20 (**)
upperBound = max{f(xv,∞ , yv,∞ ), f (xv,∞ , 0),f (0, yv,∞ ), f (0, 0)};21
if upperBound > maxVal and |v| <  then22
queue.push(v, upperBound );23
return maxEpisode;Fig. 2. Algorithm FindBestEpisode. In our pseudocode, the break statement is tojump out of the closest enclosing loop.

mizes f(xv,k , yv,k), with xv,k = |S∩Leps (v, k)| and yv,k = |T ∩Leps(v, k)|,where v varies any string of length at most  and k varies any integer.

5Conclusion

We developed a practical algorithm to ﬁnd the best episode pattern to separate given two sets of strings. Episode pattern is a generalization of subsequence
pattern, and the search space of episode patterns is much larger than that of subsequence patterns. Nevertheless, our algorithm enabled to ﬁnd the best episodepattern eﬃciently: the running time will not be much slower than that for ﬁnding
subsequence patterns.
It is challenging to apply our approach to ﬁnd the best pattern in the senseof pattern languages introduced by Angluin [1], where the related consistency
problems are shown to be very hard [6]. Fujino et al. showed an another approach
to ﬁnd the best proximity pattern [3]. It may be interesting to combine these5approaches into one. We are now in the process of installing our algorithm into
the core of the decision tree generator in the BONSAI system [7].

References
1. D. Angluin. Finding patterns common to a set of strings. J. Comput. Syst. Sci.,
21(1):46–62, Aug. 1980.
2. R. A. Baeza-Yates. Searching subsequences. Theoretical Computer Science,78(2):363–376, Jan. 1991.
3. R. Fujino, H. Arimura, and S. Arikawa. Discovering unordered and ordered phrase
association patterns for text mining. In Proc. of the 4th Pacific-Asia Conference on
Knowledge Discovery and Data Mining, volume 1805 of Lecture Notes in ArtificialIntelligence. Springer-Verlag, Apr. 2000.
4. M. Hirao, H. Hoshino, A. Shinohara, M. Takeda, and S. Arikawa. A practical algorithm to find the best subsequence patterns. In Proc. of The Third International
Conference on Discovery Science, volume 1967 of Lecture Notes in Artificial Intelligence, pages 141–154. Springer-Verlag, Dec. 2000.
5. H. Mannila, H. Toivonen, and A. I. Verkamo. Discovering frequent episode in sequences. In U. M. Fayyad and R. Uthurusamy, editors, Proc. of the 1st International
Conference on Knowledge Discovery and Data Mining, pages 210–215. AAAI Press,Aug. 1995.
6. S. Miyano, A. Shinohara, and T. Shinohara. Polynomial-time learning of elementaryformal systems. New Generation Computing, 18:217–242, 2000.
7. S. Shimozono, A. Shinohara, T. Shinohara, S. Miyano, S. Kuhara, and S. Arikawa.
Knowledge acquisition from amino acid sequences by machine learning system BONSAI. Transactions of Information Processing Society of Japan, 35(10):2009–2018,Oct. 1994.
8. Z. Tronı́ček. Episode matching. In Proc. of 12th Annual Symposium on Combinatorial Pattern Matching, Lecture Notes in Computer Science, pages 143–146.
Springer-Verlag, July 2001.

6