Finding Best Patterns Practically
Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa,
Masahiro Hirao, Hiromasa Hoshino, and Shunsuke Inenaga
Department of Informatics, Kyushu University 33, Fukuoka 812-8581, JAPAN{ayumi, takeda, arikawa, hirao, hoshino, s-ine}@i.kyushu-u.ac.jp

Abstract. Finding a pattern which separates two sets is a critical task
in discovery. Given two sets of strings, consider the problem to ﬁnd a
subsequence that is common to one set but never appears in the otherset. The problem is known to be NP-complete. Episode pattern is a
generalized concept of subsequence pattern where the length of substring
containing the subsequence is bounded. We generalize these problems
to optimization problems, and give practical algorithms to solve themexactly. Our algorithms utilize some pruning heuristics based on the
combinatorial properties of strings, and eﬃcient data structures which
recognize subsequence and episode patterns.

1

Introduction

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. String is oneof the most fundamental structure to express and reserve information. In thispaper, we review our recent work [7, 8] which ﬁnd a best pattern practically.
First we remind our motivations. Shimozono et al. [13] developed a machine
discovery system BONSAI that produces a decision tree over regular patterns
with alphabet indexing, from given positive set and negative set of strings. The
core part of the system is to generate a decision tree which classiﬁes positive
examples and negative examples as correctly as possible. For that purpose, wehave to ﬁnd a pattern that maximizes the goodness according to the entropy
information gain measure, recursively at each node of trees. In the current implementation, a pattern associated with each node is restricted to a substring
pattern, due to the limit of computation time. One of our motivations of thisstudy was to extend the BONSAI system to allow subsequence patterns as wellas substring patterns at nodes, and accelerate the computation time.
However, there is a large gap between the complexity of ﬁnding the best
substring pattern and subsequence pattern. Theoretically, the former problem
can be solved in linear time, while the latter is NP-hard. In [7], we introduced
a practical algorithm to ﬁnd a best subsequence pattern that separates positive
examples from negative examples, and showed some experimental results.

A drawback of subsequence patterns is that they are not suitable for classifying long strings over small alphabet, since a short subsequence pattern matcheswith almost all long strings. Based on this observation, in [8] we considered
episode patterns, which were originally introduced by Mannila et al. [10]. An
episode pattern v, k, where v is a string and k is an integer, matches with astring t if v is a subsequence for some substring u of t with |u| ≤ k. Episodepattern is a generalization of subsequence pattern since subsequence pattern v
is equivalent to episode pattern v, ∞. We gave a practical solution to ﬁnd abest episode pattern which separates a given set of strings from the other set of
strings.
In this paper, we summarize our practical implementations of exact searchalgorithms that practically avoids exhaustive search. Since these problems are
NP-hard, essentially we are forced to examine exponentially many candidate
patterns in the worst case. Basically, for each pattern w, we have to count the
number of strings that contain w as a subsequence in each of two sets. We callthe task of counting the numbers as answering subsequence query. The computational cost to ﬁnd the best subsequence pattern mainly comes from the total
amount of time to answer these subsequence queries, since it is relatively heavy
task if the sets are large, and many queries will be needed. In order to reduce
the time, we have to either (1) ask queries as few as possible, or (2) speed up to
answer queries. We attack the problem from both these two directions.
At ﬁrst, we reduce the search space by appropriately pruning redundant
branches that are guaranteed not to contain the best pattern. We use a heuristics inspired by Morishita and Sese [12], combined with some properties on thesubsequence languages, and episode pattern languages.
Next, we accelerate answering for subsequence queries and episode pattern
queries. Since the sets of strings are ﬁxed in ﬁnding the best pattern, it is reasonable to preprocess the sets so that answering query for any pattern will be fast.
We take an approach based on a deterministic ﬁnite automaton that accepts
all subsequences of a string. Actually, we use subsequence automata for sets ofstrings, developed in [9] for subsequence query, and episode pattern recognizer
for episode pattern query. These automata can answer quickly for subsequencequery, at the cost of preprocessing time and space requirement to construct them.

2

Preliminaries

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 say that a string v
is a subsequence of a string w if v can be obtained by removing zero or morecharacters from w, and say that w is a supersequence of v. We denote by v str w
that v is a substring of w, and by v seq w that v is a subsequence of w. For2

a string v, we deﬁne the substring language Lstr (v) and subsequence language
Lseq (v) as follows:
Lstr (v) = {w ∈ Σ ∗ | v
Lseq (v) = {w ∈ Σ ∗ | vw}, andseq w}, respectively.
str

An episode pattern is a pair of a string v and an integer k, and we deﬁne theepisode language Leps (v, k) by
Leps (v, k) = {w ∈ Σ ∗ | ∃ ustr

w such that v

sequ and |u| ≤ k}.

The following lemma is obvious from the deﬁnitions.
Lemma 1 ([7]). For any strings v, w ∈ Σ ∗ ,(1) if v is a preﬁx of w, then v str w,(2) if v is a suﬃx of w, then v str w,(3) if v str w then v seq w,(4) v str w if and only if Lstr (v) ⊇ Lstr (w),(5) v seq w if and only if Lseq (v) ⊇ Lseq (w).
We formulate the problem by following our previous paper [7]. Readers shouldrefer to [7] 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 are the optimization problems to be tackled.
Definition 1 (Finding the best substring pattern according to f ).
Input Two sets S, T ⊆ Σ ∗ of strings.
Output A string v that maximizes the value f (xv , yv ), where xv = |S ∩ Lstr (s)|and ys = |T ∩ Lstr (s)|.
Definition 2 (Finding the best subsequence pattern according to f ).
Input Two sets S, T ⊆ Σ ∗ of strings.
Output A string v that maximizes the value f (xv , yv ), where xv = |S ∩ Lseq (v)|and yv = |T ∩ Lseq (v)|.
Definition 3 (Finding the best episode pattern according to f ). .
Input Two sets S, T ⊆ Σ ∗ of strings.
Output A episode pattern v, k that maximizes the value f (xv,k , yv,k ), wherexv,k = |S ∩ Leps (v, k)| and yv,k = |T ∩ Leps (v, k)|.
3

1 pattern FindMaxPattern(StringSet S, T )2
maxVal = −∞;3
for all possible pattern π do
4
x = |S ∩ L(π)|;
5y = |T ∩ L(π)|;
6val = f (x, y);7
if val > maxVal then8maxVal = val;
9maxPat = π;10return maxPat;
Fig. 1. Exhaustive search algorithm.

We remind that the ﬁrst problem can be solved in linear time [7], while thelatter two problems are NP-hard.
We review the basic idea of our algorithms. Fig. 1 shows a naive algorithm
which exhaustively examines and evaluate all possible patterns one by one, andreturns the best pattern that gives the maximum value. The most time consuming part is obviously the lines 4 and 5, and in order to reduce the searchtime, we should (1) reduce the possible patterns in line 3 dynamically by using
some appropriate pruning method, and (2) speed up to compute |S ∩ L(π)| and|T ∩ L(π)| for each π. In Section 3, we deal with (1), and in Section 4, we treat(2).

3

Pruning Heuristics

In this section, we introduce some pruning heuristics, inspired by Morishita andSese [12].
For a function f (x, y), we denote F (x, y) = max{f (x, y), f (x, 0), f (0, y), f (0, 0)}.
From the deﬁnition of conic function, we can prove the following lemma.
Lemma 2. For any patterns v and w with L(v) ⊇ L(w), we havef (xw , yw ) ≤ F (xv , yv ).
3.1

Subsequence patterns

We consider ﬁnding subsequence pattern in this subsection. By Lemma 1 (5)and Lemma 2, we have the following lemma.
Lemma 3 ([7]). For any strings v, w ∈ Σ ∗ with v

seqw, we havef (xw , yw ) ≤ F (xv , yv ).
In Fig. 2, we show our algorithm to ﬁnd the best subsequence pattern fromgiven two sets of strings, according to the function f . Optionally, we can specify
the maximum length of subsequences. We use the following data structures in
the algorithm.
4

1 string FindMaxSubsequence(StringSet S, T , int maxLength = ∞)2string prefix , seq, maxSeq;
3
double upperBound = ∞, maxVal = −∞, val;
4
int x, y;5PriorityQueue queue; /* Best First Search*/
6
queue.push(””, ∞);7
while not queue.empty() do
8(prefix , upperBound ) = queue.pop();9
if upperBound < maxVal then break;10
foreach c ∈ Σ do11
seq= prefix + c; /* string concatenation */12
x = S.numOfSubseq(seq);13
y = T .numOfSubseq(seq);
14
val = f (x, y);15
if val > maxVal then16
maxVal = val;
17
maxSeq = seq;
18*
upperBound = F (x, y);19
if |seq| < maxLength then20
queue.push(seq, upperBound );21
return maxSeq;

Fig. 2. Algorithm FindMaxSubsequence.

StringSet Maintain a set S of strings.
– int numOfSubseq(string seq) : return the cardinality of the set {w ∈ S |seq seq w}.
PriorityQueue Maintain strings with their priorities.
– 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.
The next theorem guarantees the completeness of the algorithm.
Theorem 1 ([7]). Let S and T be sets of strings, and  be a positive integer. The
algorithm FindMaxSubsequence(S, T , ) will return a string w that maximizes
the value f (xv , yv ) among the strings of length at most , where xv = |S ∩ Lstr (s)|and ys = |T ∩ Lstr (s)|.
Proof. We ﬁrst consider the case that the lines 18 is removed. Since the valueof upperBound is unchanged, PriorityQueue is actually equivalent to a simple
queue. Then, the algorithm performs the exhaustive search in a breadth ﬁrst
5manner. Thus the algorithm will compute the value f (xv , yv ) for all strings oflength at most maxLength, in increasing order of the length, and it can ﬁnd thebest pattern trivially.
We now focus on the line 9, by assuming the condition upperBound < maxValholds. Since the queue is a priority queue, we have F (xv , yv ) ≤ upperBound forany string v in the queue. By Lemma 3, f (xv , yv ) ≤ F (xv , yv ), which implies
f (xv , yv ) < maxVal. Thus no string in the queue can be the best subsequence
and we jump out of the loop immediately.
Next, we consider the lines 18. Let v be the string currently represented
by the variable seq. At lines 12 and 13, xv and yv are computed. At line 18,
upperBound = F (xv , yv ) is evaluated, and if upperBound is less than the current
maximum value maxVal, v is not pushed into queue. It means that any string
w of which v is a preﬁx will not be evaluated. We can show that such a string
w can never be the best subsequence as follows. Since v is a preﬁx of w, weknow v is a subsequence of w, by Lemma 1 (1) and (3). By Lemma 3, we know
f (xw , yw ) ≤ F (xv , yv ), and since F (xv , yv ) < maxVal, the string w can never be
the maximum.

3.2

Episode pattern

We now show a practical algorithm to ﬁnd the best episode patterns. We should
remark that the search space of episode patterns is Σ ∗ × N , while the search
space of subsequence patterns was Σ ∗ . A straight-forward approach based on
the last subsection might be as follows. First we observe that the algorithm
FindMaxSubsequence in Fig. 2 can be easily modiﬁed to ﬁnd the best episodepattern v, k for any ﬁxed threshold k: we have only to replace the lines 12
and 13 so that they compute the numbers of strings in S and T that match withthe episode pattern seq, k, respectively. Thus, for each possible threshold valuek, repeat his algorithm, and get the maximum. A short consideration reveals
that we have only to consider the threshold values up to l, that is the length ofthe longest string in given S and T .
However, here we give a more eﬃcient solution. Let us consider the following
problem, that is a subproblem of ﬁnding the best episode pattern in Deﬁnition 3.
Definition 4 (Finding the best threshold value).
Input Two sets S, T ⊆ Σ ∗ of strings, and a string v ∈ Σ ∗ .
Output Integer 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)|.
The next lemma give a basic containment of episode pattern languages.
Lemma 4 ([8]). For any two episode patterns v, l and w, k, if v
l ≥ k then Leps (v, l) ⊇ Leps (w, k).

seq

w and

seq

w and

By Lemma 2 and 4, we have the next lemma.
Lemma 5 ([8]). For any two episode patterns v, l and w, k, if v
l ≥ k then f (xw,k , yw,k ) ≤ F (xv,l , yv,l ).
6For strings v, s ∈ Σ ∗ , we deﬁne the threshold value θ of v for s by θ = min{k ∈N | s ∈ Leps (v, k)}. If no such value, let θ = ∞. Note that s ∈ Leps (v, k) for
any k < θ, and s ∈ Leps (v, k) for any k ≥ θ. For a set S of strings and a stringv, let us denote by ΘS,v the set of threshold values of v for some s ∈ S.
A key observation is that a best threshold value for given S, T ⊆ Σ ∗ and astring v ∈ Σ ∗ can be found in ΘS,v ∪ ΘT,v without loss of generality. Thus we
can restrict the search space of the best threshold values to ΘS,v ∪ ΘT,v .
From now on, we consider the numerical sequence {xv,k }∞k=0 . (We will treat{yv,k }∞k=0 in the same way.) It clearly follows from Lemma 4 that the sequence
is non-decreasing. Remark that 0 ≤ xv,k ≤ |S| for any k. Moreover, xv,l =xv,l+1 = xv,l+2 = · · ·, where l is the length of the longest string in S. Hence,
we can represent {xv,k }∞k=0 with a list having at most min{|S|, l} elements.
We call this list a compact representation of the sequence {xv,k }∞k=0 (CRS, forshort).
We show how to compute CRS for each v and a ﬁxed S. Observe that xv,k
increases only at the threshold values in ΘS,v . By computing a sorted list of all
threshold values in ΘS,v , we can construct the CRS of {xv,k }∞k=0 . If using thecounting sort, we can compute the CRS for any v ∈ Σ ∗ in O(|S|ml + |S|) =O(||S||m) time, where m = |v|.
We emphasize that the time complexity of computing the CRS of {xv,k }∞k=0
is the same as that of computing xv,k for a single k (0 ≤ k ≤ ∞), by our method.
∞
After constructing CRSs x̄ of {xv,k }∞k=0 and ȳ of {yv,k }k=0 , we can compute the best threshold value in O(|x̄| + |ȳ|) time. Thus we have the following,
which gives an eﬃcient solution to the ﬁnding the best threshold value problem.
Lemma 6. Given S, T ⊆ Σ ∗ and v ∈ Σ ∗ , we can ﬁnd the best threshold valuein O( (||S|| + ||T ||)·|v| ) time.
By substituting this procedure into the algorithm FindMaxSubsequence, we
get an algorithm to ﬁnd a best episode pattern from given two sets of strings,
according to the function f , shown in Fig. 3. We add a method crs(v) to thedata structure StringSet that returns CRS of {xv,k }∞k=0 , as mentioned above.
By Lemma 5, we can use the value upperBound = F (xv,∞ , yv,∞ ) to prune
branches in the search tree computed at line 20 marked by (*). We emphasize that the value F (xv,k , yv,k ) is insuﬃcient as upperBound. Note also thatx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 2 ([8]). Let S and T be sets of strings, and  be a positive integer.
The algorithm FindBestEpisode(S, T , ) will return an episode pattern thatmaximizes 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.

4

Using Eﬃcient Data Structures

We introduces some eﬃcient data structures to speed up answering the queries.
7

1 string FindBestEpisode(StringSet S, T , int )2string prefix , v;
3
episodePattern maxSeq; /* pair of string and int */4
double upperBound = ∞, maxVal = −∞, val;5
int k ;6
CompactRepr x̄, ȳ; /* CRS */7
PriorityQueue queue; /* Best First Search*/
8
queue.push(””, ∞);9while not queue.empty() do
10(prefix , upperBound ) = queue.pop();11
if upperBound < maxVal then break;12
foreach c ∈ Σ do
13v = prefix + c; /* string concatenation */14x̄ = S.crs(v);15ȳ = T .crs(v);16k = 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 = F (xv,∞ , yv,∞ );21
if upperBound > maxVal and |v| <  then22
queue.push(v, upperBound);23
return maxEpisode;Fig. 3. Algorithm FindBestEpisode.

4.1

Subsequence Automata

First we pay our attention to the following problem.
Definition 5 (Counting the matched strings).
Input A ﬁnite set S ⊆ Σ ∗ of strings.
Query A string seq ∈ Σ ∗ .
Answer The cardinality of the set S ∩ Lseq (seq).
Of course, the answer to the query should be very fast, since many queries
will arise. Thus, we should preprocess the input in order to answer the query
quickly. On the other hand, the preprocessing time is also a critical factor insome applications. In this paper, we utilize automata that accept subsequencesof strings.
In [9], we considered a subsequence automaton as a deterministic complete
ﬁnite automaton that recognizes all possible subsequences of a set of strings,
that is essentially the same as the directed acyclic subsequence graph (DASG)
introduced by Baeza-Yates [2]. We showed an online construction of subsequence
automaton for a set of strings. Our algorithm runs in O(|Σ|(m + k) + N ) timeusing O(|Σ|m) space, where |Σ| is the size of alphabet, N is the total length of
8

a
3

a

2

b

b

2
a

a

1

b

aa

b

a

1
b

2

3

0
b
a

b
3

a
b

b

Fig. 4. Subsequence automaton for S = {abab, abb, bb}, where Σ = {a, b}. Each number
on a state denotes the number of matched strings. For example, by traverse the statesaccording to a string ab, we reach the state whose number is 2. It corresponds to thecardinality |Lseq (ab) ∩ S| = 2, since ab seq abab, ab seq abb and ab seq bb.

strings, and m is the number of states of the resulting subsequence automaton.
We can extend the automaton so that it answers the above Counting the matchedstrings problem in a natural way (see Fig. 4).
Although the construction time is linear to the size m of automaton to bebuilt, unfortunately m = O(nk ) in general, where we assume that the set S
consists of k strings of length n. (The lower bound of m is only known for thecase k = 2, as m = Ω(n2 ) [4].) Thus, when the construction time is also a criticalfactor, as in our application, it may not be a good idea to construct subsequence
automaton for the set S itself. Here, for a speciﬁed parameter mode > 0, we
partition the set S into d = k/mode subsets S1 , S2 , . . . , Sd of at most mode
strings, and construct d subsequence automata for each Si . When asking a query
seq, we have only to traverse all automata simultaneously, and return the sumof the answers. In this way, we can balance the preprocessing time with the total
time to answer (possibly many) queries. In [7], we experimentally evaluated the
optimal value of the parameter mode.
4.2

Episode Directed Acyclic Subsequence Graphs

We now 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 recently
introduced by Troı́ček in [14]. Hereafter, let EDASG(t) denote the EDASG for t.
With the use of EDASG(t), episode pattern matching can be answered quickly
in practice, although the worst case behavior is still O(mn). EDASG(t) is also
useful to compute the threshold value θ of given v for t quickly in practice. As an
example, EDASG(aabaababb) is shown in Fig. 5. When examining if an episode
9

b
0

a

1

b

a

b
a

b

2
a

3

a

a

b
4

a

b
b

b

5
a

b
a

6
b

7

b
a

8

b

9

a

Fig. 5. EDASG(t), where t = aabaababb. Solid arrows denote the forward edges, andbroken arrows denote the backward edges. The number in each circle denotes the state
number.

pattern abb, 4 matches with t or not, we start from the initial state 0 andarrive at state 6, by traversing the forward edges spelling abb. It means that the
shortest preﬁx of t that contains abb as a subsequences is t[0 : 6] = aabaab, wheret[i : j] denotes the substring ti+1 . . . tj of t. Moreover, the diﬀerence between thestate numbers 6 and 0 corresponds to the length of matched substring aabaab oft, 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 subsequence is 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 substring t[4 : 8] = abab which contains the subsequenceabb, and the length 8 − 4 = 4 satisﬁes the threshold. Therefore we report theoccurrence and terminate the procedure.
It is not diﬃcult to see that the EDASGs are useful to compute the thresholdvalue of v for a ﬁxed t. We have only to repeat the above forward and backward traversal up to the end, and return the minimum length of the matchedsubstrings. Although the time complexity is still Θ(mn), practical behavior isusually better than using standard dynamic programming method.

5

Conclusion

In this paper, we focused on ﬁnding the best subsequence pattern and episodepatterns. However, we can easily extend our algorithm to enumerate all strings
whose values of the objective function exceed the given threshold, since essentially we examine all strings, with eﬀective pruning heuristics. Enumeration may
be more preferable in the context of text data mining [3, 5, 15].
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 [11]. Hamuro et al. [6] implemented ouralgorithm for ﬁnding best subsequences, and reported a quite successful experiments on business data. We are now in the process of installing our algorithms
into the core of the decision tree generator in the BONSAI system [13].
10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. A. Califano. SPLASH: Structural pattern localization analysis by sequential histograms. Bioinformatics, Feb. 1999.
4. M. Crochemore and Z. Tronı́ček. Directed acyclic subsequence graph for multiple
texts. Technical Report IGM-99-13, Institut Gaspard-Monge, June 1999.
5. R. Feldman, Y. Aumann, A. Amir, A. Zilberstein, and W. Klosgen. Maximal
association rules: A new tool for mining for keyword co-occurrences in document
collections. In Proc. of the 3rd International Conference on Knowledge Discovery
and Data Mining, pages 167–170. AAAI Press, Aug. 1997.
6. Y. Hamuro, H. Kawata, N. Katoh, and K. Yada. A machine learning algorithm
for analyzing string patterns helps to discover simple and interpretable businessrules from purchase history. In Progress in Discovery Science, LNCS, 2002. (Inthis volume).
7. M. Hirao, H. Hoshino, A. Shinohara, M. Takeda, and S. Arikawa. A practicalalgorithm to ﬁnd 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.
8. M. Hirao, S. Inenaga, A. Shinohara, M. Takeda, and S. Arikawa. A practicalalgorithm to ﬁnd the best episode patterns. In Proc. of The Fourth International
Conference on Discovery Science, Lecture Notes in Artiﬁcial Intelligence. SpringerVerlag, Nov. 2001.
9. H. Hoshino, A. Shinohara, M. Takeda, and S. Arikawa. Online construction ofsubsequence automata for multiple texts. In Proc. of 7th International Symposiumon String Processing and Information Retrieval. IEEE Computer Society, Sept.
2000. (to appear).
10. H. Mannila, H. Toivonen, and A. I. Verkamo. Discovering frequent episode insequences. 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.
11. S. Miyano, A. Shinohara, and T. Shinohara. Polynomial-time learning of elementary formal systems. New Generation Computing, 18:217–242, 2000.
12. S. Morishita and J. Sese. Traversing itemset lattices with statistical metric pruning.
In Proc. of the 19th ACM SIGACT-SIGMOD-SIGART Symposium on Principles
of Database Systems, pages 226–236. ACM Press, May 2000.
13. 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.
14. Z. Tronı́ček. Episode matching. In Proc. of 12th Annual Symposium on Combinatorial Pattern Matching, Lecture Notes in Computer Science. Springer-Verlag,
July 2001. (to appear).
15. J. T. L. Wang, G.-W. Chirn, T. G. Marr, B. A. Shapiro, D. Shasha, and K. Zhang.
Combinatorial pattern discovery for scientiﬁc data: Some preliminary results. In
Proc. of the 1994 ACM SIGMOD International Conference on Management of
Data, pages 115–125. ACM Press, May 1994.

11