TCS -TR-A-06-20

TCS Technical Report

Eﬀcient Algorithms for Mining Maximal Flexible
Patterns in Texts and SequencesbyHiroki Arimura and Takeaki Uno

Division of Computer Science
Report Series A
July 19, 2006

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

Arimura@ist.hokudai.ac.jp

Phone:
Fax:+81-011-706-7678+81-011-706-7890

Eﬀcient Algorithms for Mining
Maximal Flexible Patterns in Texts
and Sequences
Hiroki Arimura and Takeaki Uno
Graduate School of Information Science and Technology, Hokkaido University
Kita 14 Nishi 9, Sapporo 060-0814, Japan
National Institute of Informatics
2-1-2, Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan
Abstract
In this paper, we study the maximal pattern discovery problem in a given sequence for theclass ERP of flexible patterns with applications to text mining, where a ﬂexible pattern isa sequence of constant and wildcards for possibly empty strings such as AB*B*ABC, andalso known as erasing regular patterns. We ﬁrst discuss the framework of optimal patterndiscovery for predictive mining and text classiﬁcation, and then show its connection to
maximal pattern discovery. Then, we introduce a new notion of maximality of patterns
based on the position occurrences of patterns, called position-maximality. We present aneﬃcient algorithm PosMaxFlexMotif that, given an input string of length n over analphabet Σ, enumerates all maximal patterns of ERP without duplicates in O(kmn2 ) time
per maximal pattern using O(mn) space, where m = |P | is the size of the pattern P to be
enumerated, and k = O(m) is the number of variables in P . This implies as corollary thatthe position-maximal enumeration problem for ﬂexible patterns is output-polynomial timesolvable. Then, we apply the above result to maximal pattern discovery in terms of the
maximality based on document occurrence as a sound pruning technique.
Keywords: Data mining, Enumeration algorithms, Sequence databases, Maximal pattern,
Motif Discovery

1. Introduction
By the rapid growth of the amount of human-readable electronic data on networks
and storages, there are potential demands for the eﬃcient computational methods toextract useful information and knowledge from massive amount of electronic data scattered over the network. Some prominent examples of such knowledge discovery tasks
are: Automatic classiﬁcation of natural language texts and web pages, characteristicand descriptive pattern discovery, prediction of trends from market data, detectionof malicious activities from audit data, and clustering of documents. Pattern discovery is one of the fundamental technologies to ﬁnd a class of patterns appearing in adata set satisfying given constraints, and plays an important role in many knowledge
discovery tasks.
In this paper, we consider the maximal pattern discovery problem [9, 10, 13, 14]
in a set of sequences. A pattern is maximal if there is no properly more speciﬁc
pattern w.r.t. some generalization ordering over the class of patterns that has the sameoccurrence, or equivalently, has the same frequency, in a given set of input sequences.
Since the set of all maximal patterns are typically much smaller than the set of all
patterns appearing in a data set while the formar contains the complete information of
the latter, maximal pattern discovery has merits in eﬃciency and comprehensiveness.
On the other hands, the computational complexity of maximal pattern discovery ishigher than that of frequent pattern disocovery. For example, there are few classesof patterns for which the maximal pattern discovery problem have output-polynomial
time complexity.
The class of patterns we consider is the class ERP of erasing regular patterns of
Shinohara [12], which is also called ﬂexible patterns in bioinformatics area [9]. A ﬂexible pattern over an alphabet Σ is a sequence of constant letters in Σ and wildcards∗ for possibly empty strings such as AB*B*ABC. From the view of polynomial time
enumeration, the class ERP is a super class of the class of subsequence patterns [7]for which polynomial output maximal pattern enumeration algorithm is known [14].
However, there is no output-polynomial algorithm for the maximal pattern problem
for ERP. A potential problem for the class ERP of ﬂexible patterns is, unlike classes
of itemsets and rigid patterns [3, 9, 10], there are no unique maximal pattern ineach equivalence class of patterns. To overcome this problem, we introduce a weaker
notion of maximality for ERP than the original one, called position-maximality , bygeneralizing the notion of maximality implicitly used in [14] for maximal subsequence
patterns. Then, we study the output-sensitive computational complexity of the maximal pattern enumeration problem in terms of the position-maximality.
As a main result of this paper, we present an eﬃcient enumeration algorithm
PosMaxFlexMotif that discovers all position-maximal patterns appearing in agiven string without duplicates in O(|Σ|kmn2 ) time per maximal pattern using O(mn)space, where |Σ| is the size of an alphabet, m = |P | is the size of the pattern P to
be enumerated, k = O(m) is its number of variables, and n is the total length of
an input string. As a corollary, this enumeration algorithm achieves one of the moststrict notion of output-polynomial time enumerabilities, known as polynomial-spaceand polynomial-delay enumerability. where the delay is the maximum time required
to compute each pattern. This result generalizes the output-polynomial complexityof [14] for subsequence patterns to the class ERP. The polynomial-space and delay
property indicates that it can be used as a light-weight and high-throughput algorithm
for pattern discovery.
We presented a heuristics algorithm DocMaxFlexMotif for enumerating documentmaximal patterns in a collection of strings for the class ERP with non-trivial pruning
strategies derived from the previous algorithm PosMaxFlexMotif. Finally, wediscuss the application of the maximal pattern discovery to the optimal pattern discovery problem in machine learning and knowledge discovery with application to text
mining.

2. Preliminaries
Let A be an alphabet of symbols. We denote by A∗ the set of all ﬁnite strings over
A and deﬁne Σ+ = Σ∗ − {ε}. Let s = a1 · · · an ∈ A∗ be a string over A of lengthn. We denote |s| = n the length of s and by ε the empty string. For any indices1 ≤ i ≤ j ≤ n, we denote by s[i] = ai the i-th letter of s, and by s[i..j] the substrings[i..j] = ai · · · aj that starts with i and ends with j. For a set S ⊆ A∗ , we denote by|S| the cardinality of S and by ||S|| = s∈S |s| be the total size of the strings in S.
For strings u, v, w ∈ A∗ , we say that u, v, and w, respectively, are a preﬁx , a
substring, and a suﬃx of a string s = uvw. Then, the substring v occurs in s at
position p = |u| + 1. Equivalently, if s = s[1] · · · s[n], then v occurs in s at position i
iﬀ v = s[i] · · · s[i + |v| − 1]. The left position and the right position of v corresponding
to this occurrence of in t are i and i + |v| − 1, respectively. The reversal of a stringx = a1 · · · am is deﬁned by xR = an · · · a1 .

2.1. Text and Patterns
In this subsection, we introduce the class ERP of erasing regular patterns of Shinohara [12], also known as ﬂexible patterns [9]. Let Σ = {a, b, c, . . .} be a ﬁnite
alphabet of constant symbols. We assume a special symbol ∗ ∈ Σ called a variable (orvariable-length don’t cares, VLDC ), which represents arbitrary long possibly-empty
ﬁnite string in Σ∗ . Then, an erasing regular pattern (or pattern, for short) over Σ is astring P ∈ (Σ∪{∗})∗ consisting of constant symbols and variables. An erasing regularpattern P is said to be in canonical form if it is written as P = w0 ∗ w1 ∗ · · · ∗ wm forsome integer m ≥ 0 and some non-empty strings w0 , w1 , . . . , wm ∈ Σ+ . Each constantstring wi is called a segment of P . An erasing regular pattern in canonical form isalso called as a ﬂexible pattern or a VLDC pattern [9]. We denote by ERP the class oferasing regular patterns over Σ in canonical form (or equivalently ﬂexible patterns).
We note that Σ∗ ⊆ ERP.
Example 1 Let Σ = {A, B, C}. Then, P0 = AB ∗ A ∗ ABC is an erasing regularpattern in canonical form, i.e., a ﬂexible pattern. On the other hand, P1 = ∗AC ∗BB ∗ CB and P2 = A ∗ ∗B are erasing regular patterns but not in canonical form
since P2 starts with a wildcard and P3 has consecutive occurrences of wildcards ∗∗.
Let Σ be a ﬁxed alphabet of constants. An input string is a constant string T =a1 · · · an (n ≥ 0) over Σ. Let P = w0 ∗ w1 ∗ · · · ∗ wm ∈ (Σ ∪ {∗})∗ be a patternwith m ≥ 0 variables in canonical form. A substitution for P is any m-tuple θ =(u1 , . . . , um) ∈ ((Σ ∪ {∗})∗ )m of strings. Then, we deﬁne the application of θ to P ,denoted by P θ, as the string P θ = w0 u1w1 u2 · · · um wm ∈ (Σ ∪ {∗})∗ , where the i-th

012345678

Pattern P

Text T

AB*CBA*BBBCBCABDCBCBABACBBABAB

m=9n = 21012345678901234567890
00
10
20

p = 4 An occurrence position p of P in T

Figure 1: A pattern and its left and right positions in a text.

occurrence of variable ∗ is replaced with the i-th string ui for every i = 1, . . . , m. The
string P θ is said to be an instance of P by substition θ.
For strings P, Q ∈ (Σ ∪ {∗})∗ , P occurs in Q at position 1 ≤ i ≤ n if there exists
some instance I of P that is a substring of Q starting at p, that is, Q[i .. i+ |P θ| −1] =P θ for some substitution θ for P . Particularly, the positions i and i + |P θ| − 1,
respectively, correspond to the left and the right ends of the occurrence of instanceP θ, and are called the left and the right positions of P in T (See Fig. 1). We denoteby LO(P, T ) and RO(P, T ) the set of all left-positions and the set of all right-positionsof pattern P in text T , respectively. We refer to LO(P, T ) and RO(P, T ) as the leftlocation list and the right-location list of P in T , respectively. Recall that T R denotes
the reversal of T .
Lemma 1 Let P be a pattern and T be a text. For any position 1 ≤ p ≤ n, p ∈RO(P, T ) if and only if n − p + 1 ∈ LO(P R , T R ).
By the symmetry between the left and the right location lists in Lemma 1, it
is suﬃcient to consider only LO(P, T ) than RO(P, T ). Thus, we only consider thelocation list O(P, T ) = LO(P, T ) in what follows.
Lemma 2 The location list LO(P, T ) is computable in O(mn) time, where m = |P |and n = |T |.
We deﬁne a binary relation  over P, called the speciﬁty relation, as follows [2, 9,12]. For patterns P, Q ∈ ERP , P is more speciﬁc than Q, denoted by P  Q, iﬀ P
occurs in T at some position 1 ≤ p ≤ n − 1. If P  Q and Q < P hold, then we saythat P is properly more speciﬁc than Q and denote P < Q. We note that if P  Q
and Q < P hold then P = Q holds.
Lemma 3 Let T be any text. Then, (ERP, ) is a partial ordering with the smallest
element ε.

In machine learning area, the learning problem for the class formal languages
deﬁned by ERP has been extensively studied [12]. For a erasing regular pattern
P ∈ ERP, the language deﬁned by P is the set LangΣ (P ) = { s ∈ Σ∗ : P  s } ⊆ Σ∗ .
It is easy to see that for any regular pattern P ∈ (Σ ∪ {∗})∗ , there exists someQ ∈ ERP in canonical form such that LangΣ (P ) = LangΣ (Q).
Example 2 For patterns P3 = A ∗ BA ∗ B and P4 = BAB ∗ BA ∗ AB ∗ B, we can seethat P3  P4 as follows. P3 has an instance P4 θ = AB ∗ BA ∗ AB that is a substringof P4 by the substitution θ = (B∗, ∗A). From this, P3  P4 holds.

2.2. Maximal patterns
Let T be a ﬁxed text of length n ≥ 0. The frequency of a pattern P in T is |OT (P )|.
A minimum support threshold is a nonnegative integer 0 ≤ σ ≤ n. A pattern P is
σ-frequent in T if it has the frequency no less than σ in T , i.e., |OT (P )| ≥ σ.
Deﬁnition 1 A pattern P is maximal in T if there is no proper specialization Q of
P that has the same location list, i.e., P < Q and OT (P ) = OT (Q).
We see that a pattern P ∈ ERP is maximal iﬀ P is a maximal element w.r.t.  inthe equivalence class [P ]≡T = { Q ∈ ERP : P ≡T Q } under the equivalence relation≡T deﬁned by P ≡T Q ⇔ OT (P ) = OT (Q).
Lemma 4 The maximal patterns in each equivalence class [P ]≡T is not unique ingeneral.
We denote by Fσ , M, and Mθ = Fσ ∩ M the classes of the σ-frequent patterns,
the maximal patterns, and the maximal σ-frequent patterns in T . It is easy see thatthe number of frequent ﬂexible patterns in an input text S is exponential in the total
length n of T in the worst case.
Lemma 5 There is an inﬁnite sequence (Ti )i≥0 of texts such that the number of maximal ﬂexible patterns in Ti is exponential in n = |Ti |, i.e., |Mσ | = 2Ω(n) .
Now, we state our data mining problem considered in this paper as follows.
Maximal Flexible Pattern Enumeration Problem:
Input: An alphabet Σ, a text T of length n, and a minimum support threshold σ.
Task: To generate all maximal frequent ﬂexible patterns in Mσ ⊆ ERP in T without
duplicates.
It is easy to see that Mθ = Fσ ∩ M. Therefore, we will ﬁrst present an eﬃcient
enumeration algorithm for M = M1 , and then extend it for Mσ for every σ ≥ 1.

3. Motivated Applications of Maximal Pattern Discovery
In this section, we discuss potential applications of maximal pattern discovery
considered in this paper to predictive mining and classiﬁcation.

3.1. Predictive Mining and Text Classiﬁcation
First, we introduce a practical model of machine learning in a noizy environment,
known as robust training or agnostic learning according to, e.g.,[5, 6]. Suppose weare given a ﬁnite collection S = { xi : i = 1, . . . , m } ⊆ Σ∗ of strings, called a sample,
and a binary labeling function F : S → {0, 1}, called an objective function. Eachstring s ∈ S is called a document and the value of the funcion F (s) ∈ {0, 1} indicates
whether the document is, e.g., interesting or not. Let P be a class of classiﬁcation rules
or patterns, where each pattern P ∈ P represents a binary function P : S → {0, 1}.
In our case, for any document s ∈ S, we deﬁne P (s) = 1 if P matches s and P (s) = 0
otherwise. For a predicate π(x) on a string x, [π(x)] ∈ {0, 1} is the indicator functionthat returns 1 or 0 depending on the truth value of π(x). Now, we state our patterndiscovery problem.
Empirical Error Minimization Problem: ([5, 6])
Input: A sample S and an objective function F : S → {0, 1}.
Task: To ﬁnd an optimal pattern P ∈ P that minimizes the empirical error
ErrS,F (P ) =[P (x) = F (x)].

x∈Samong all patterns in P.
In learning theory, it is known that any algorithm that eﬃciently solves the above
empirical error minimization problem can approximate a target concept within a given
concept class under arbitrary unknown probability distributions, and thus can workwith noisy environments [11].

3.2. Optimal Pattern Discovery
The above framework can be extended for more general classes of score functions [4]. An impurity function is any real-valued function ψ : [0, 1] → Real suchthat (i) it takes the maximum value ψ(1/2), (ii) the minimum value ψ(0) = ψ(1) = 0,
and (iii) ψ(x) is convex, i.e., ψ( 12 (x + y)) ≥ 12 (ψ(x) + ψ(y)) for every x, y ∈ [0, 1].
• The information entropy: ψ1 (x) = −x log x − (1 − x) log(1 − x).
• The Gini index: ψ2 (x) = 2x(1 − x).
Let N be the number of all examples and M be the number of positive examples
in S with respect to a given an objective function F . Given objective function F ,and pattern P , let S1 and S0 be the set of the matched examples and the unmatchedexamples, where Sα = { s ∈ S : P (s) = α } for every α ∈ {0, 1}. The contingency tablefor P is a 4-tuple (M1 , M0 , N1 , N0 ), where Mα and Nα are the number of all positive
examples and the number of all examples in Sα for every α ∈ {0, 1}. Then, our1) andgoal is to ﬁnd such rules that decreases the impurities or the ambiguities, ψ( M
N1
M0
ψ( N0 ), for S1 and S0 . Now, we describe our data mining problem, the optimal patterndiscovery problem, which is parameterized by an impurity function ψ, as follows (See,e.g., Devroy et al. [4]).
ψ-Optimal Pattern Discovery Problem:
Input: A sample S and an objective function F : S → {0, 1}.
Task: To ﬁnd an optimal pattern P ∈ P that minimizes the cost
GψS,F (P ) = N1 · ψ(

M1
M0
) + N0 · ψ(
),
N1
N0

among all patterns in P, where (M1 , M0 , N1 , N0 ) is the contingency table deﬁned by
S, F , and the pattern P .

3.3. A Heuristic Algorithm for Optimal Pattern Discovery
In spite of the practical importance of optimal pattern problem, unfortunately, theabove optimization problems are known to be computationally hard even for mostclasses of simple patterns, e.g., half-spaces in Rd or Boolean conjunctions in Bd [5].
In particular for the class ERP of ﬂexible patterns, Miyano, Shinohara, and Shinohara [8] showed that the consistency problem for ERP is NP-complete. Furthermore,
Shimozono, Arimura, and Arikawa [11] showed that the empirical error minimization problem for ERP is even hard to approximation within arbitrary small ratio.1
Therefore, a class of straightfoward generate-and-test algorithms, which enumerates
frequent patterns with an adequate threshold, are used to solve the optimized patterndiscovery problem in practice. However, a potential problem with this approach isthat there are a huge number of frequent patterns.
In Fig. 2, we show a heuristic algorithm FindOptimal for discovering top-K
optimal patterns in terms of the score function GψS,F (P ) based on a generate-and-test
strategy using maximal patterns in M instead of frequent patterns in F . If we set
K = 1 then the algorithm solves the above ψ-optimal pattern problem. Then, thefollowing theorem gives a justiﬁcation of such an approach.
Theorem 6 Let S ⊆ Σ∗ and F : S → {0, 1}. Let P = ERP and M ⊆ P be
the class of maximal patterns in S. Even if we restrict the class of patterns to
M in S, then this does not lose the optimility of the answers for the empiricalerror minimization problem and the ψ-optimal pattern discovery problem. That is,min{ ErrS,F (P ) : P ∈ M } = min{ ErrS,F (P ) : P ∈ P } and min{ GψS,F (P ) : P ∈M } = min{ GψS,F (P ) : P ∈ P } hold.
1

Although the original approximation hardness result in [11] has been shown for the class withproximity constraints, we can obtain the same result for ERP without proximity constraints fromits proof.

Proof: For any pattern P , the cost GS,F (P ) is uniquely determined by the contingency table (M1 , M0 , N1 , N0 ) corresponding to a sample S, an objective function F ,and pattern P . For any patterns P, Q, if LO(P, S) = LO(Q, S) then P and Q realizes
the same classiﬁcation function P : S → {0, 1}, and thus gives the same contingency
table. Hence, the result follows.
2
Algorithm FindOptMax(S, F )input: A sample S, an objective function F : S → {0, 1}, and an integer K ≥ 1.
output: The top-K optimal patterns P1 , . . . , PK minimizing the cost GS,F (P ).
1 Let Q := ∅ be an empty priority queue with the cost as the key.
2 foreach maximal pattern P ∈ M in S do begin:3
Let LO(P, S) be the location list of P ;4
Compute the contingency table τ = (M1 , M0 , N1 , N0 ) from LO(P, S);
5
Q := Q ∪ {(P, GψS,F (P ))};
6 end
7 output the top K patterns P in Q in terms of GS,F (P );Figure 2: An algorithm for the optimal pattern discovery via maximal pattern enumeration.
From Theorem 6, we know that the algorithm FindOptMax correctly ﬁnds top-K
optimal patterns in S minimizing the cost GψS,F (P ). The eﬃciency of this heuristics
algorithm heavily depends on that of enumeration of maximal patterns in M at
Line 2. Therefore, our goal in the remainder of this paper is to develop a memory andtime eﬃcient enumeration algorithm for maximal patterns in M for the class ERP.
Since the number |M| of maximal patterns is exponential in the total input size, it
is natural to consider output-sensitive algorithm for M. In what follows, we refer tothe maximum computation time of A between consecutive outputs as the delay of an
enumeration algorithm A.

4. Tree-shaped Search Route for Position-Maximal Flexible
Patterns
In this section, we will present our algorithm for ﬁnding position-maximal patterns
in a given input string for the class ERP of ﬂexible patterns. First, we introduce atree-shaped search route T for the space of all maximal patterns in M. Then, inthe next section, we give a memory eﬃcient algorithm for enumerating all maximal
patterns based on the depth-ﬁrst search over T . Out strategy is explained as follows:First we deﬁne a binary relation between maximal patterns, called the parent function,
which indicates a reverse edge from a child to its parent. Next, we reverse the directionof the edges to obtain a spanning tree for M.
We start with technical lemmas. Let P, Q ∈ ERP be patterns over Σ. Recall that Q
is a specialization of P , denoted by P  Q, iﬀ Q = α(P θ)β for some α, β ∈ (Σ ∪ {∗})∗
and for some substitution θ for P . We distinguish two cases whether α = ε.

Deﬁnition 2 A pattern Q is said to be a preﬁx specialization of another pattern P if
P occurs in the initial part of Q, i.e., Q = (P θ)β for some string β ∈ (Σ ∪ {∗})∗ andfor some substitution θ for P . If there is no such β and θ, Q is said to be a non-preﬁx
specialization of P .
The following two lemmas are essential for ﬂexible patterns.
Lemma 7 Let T ∈ Σ∗ be an input string and P, Q ∈ ERP be ﬂexible patterns.
Suppose that P  Q. Then, if Q is a preﬁx specialization of P then O(P, T ) ⊇O(Q, T ).
Proof: Let T be an input string of length n. Let p ∈ O(P, T ) = LO(P, T ) be anyleft-position of P in T . Then, it follows from the deﬁnition that If p ∈ LO(P, T )then some substring H of T starting at position p is an instance of Q. On the other
hand, since Q is a preﬁx specialization of P , some preﬁx H  of Q is an instance of P .
Therefore, some preﬁx H  of H, and thus a substring of T , is an instance of P . Since
H  is a substring starting at p in T , the lemma is proved.
2
Lemma 8 Let T ∈ Σ∗ be an input string and P, Q ∈ ERP be ﬂexible patterns.
Suppose that P  Q. Then, if Q is a non-preﬁx specialization of P then O(P, T ) ⊆O(Q, T ).
Proof: Let pmax = max LO(P, T ) be the largest left-position of P in T . Since
LO(P, T ) = ∅ and T has ﬁnite length, there always exists such a largest left-position
pmax in T . Now we assume to contradict that O(P, T ) ⊆ O(Q, T ). Then, pmax is also
a postition of Q in T . Since Q is a non-preﬁx specialization of P , P occurs in Q atsome position δ > 1. Thus, we know that q = pmax + δ − 1 is a position of P in T . If
δ > 1 then q is strictly larger than pmax . This contradicts the assumption that pmax isthe largest position of P in T , and thus we conclude that O(P, T ) ⊆ O(Q, T ). Hence,
the result is proved.
2
Corollary 9 Let T ∈ Σ∗ be an input string and P, Q ∈ ERP be ﬂexible patterns.
Suppose that P  Q. Then, if Q is a non-preﬁx specialization of P then O(P, T ) =O(Q, T ).
We deﬁne the parent-child relationship between two ﬂexible patterns in ERP as
follows.
Deﬁnition 3 Let Q = w0 ∗ w1 ∗ · · · ∗ wm be a ﬂexible pattern over Σ, where m ≥ 0
and w1 , . . . , wm ∈ Σ+ . Then, we deﬁne the parent of Q, denoted by P(Q), is thepattern satisfying the the followings (i) or (ii):(i) If |w0 | ≥ 2, that is, w0 = au0 for some letter a ∈ Σ and a non-empty stringu0 ∈ Σ+ , then then P(Q) = u0 ∗ w1 ∗ · · · ∗ wm .

(ii) If |w0| = 1, that is, w0 = a for some letter a ∈ Σ then P(Q) = w1 ∗ · · · ∗ wm .
In summary, the parent P(Q) is the ﬂexible pattern obtained from Q by removing
the ﬁrst letter, and then remove the ﬁrst variable ∗ at the starting position if it exists.
The removal of the initial ∗ ensures the canonicity of the resulting pattern.
Lemma 10 For any non-empty ﬂexible pattern Q ∈ ERP in cannonical form, its
parent P(Q) is always deﬁned, unique, and a ﬂexible pattern in canonical form, i.e.,a member of ERP.
Let n ≥ 0 be a positive integer. For a nonnegative integer 0 ≤ k ≤ n and a set
X ⊆ {1, . . . , n}, we deﬁne X + k = { x + k : x ∈ X }. For sets X, Y ⊆ {1, . . . , n}, wedeﬁne X 1≤ Y = { p ∈ X : p ≤ q for some q ∈ Y }. By deﬁnition, both of X + k and
X 1≤ Y are subsets of X. Using these operators, we can describe the location lists
of a composite pattern of the form wP or w ∗ P , where w ∈ Σ+ and P ∈ ERP as
follows.
Lemma 11 Let T ∈ Σ∗ be any input string, w ∈ Σ+ be any non-empty constantstring, and P ∈ ERP be any ﬂexible pattern. Then, the following (a) and (b) hold:(a) LO(wP ) = LO(w, T ) ∩ (LO(P, T ) − |w|).
(b) LO(w ∗ P ) = LO(w, T ) 1≤ (LO(P, T ) − |w|).
Let T ∈ Σ∗ be any input string of length n ≥ 0. A maximal pattern P is a root
pattern in T if O(P, T ) = {1, . . . , |T |}. Now, we show the main result of this section.
Theorem 12 (reverse search property of M) Let Q ∈ M be a maximal pattern
in T that is not a root pattern. Then, P(Q) is also a maximal pattern in T . That is,
if Q ∈ M then P(Q) ∈ M holds. Furthermore, |P(Q)| < |Q| holds.
Proof: Let Q be a maximal pattern that is not a root pattern, and let P = P(Q) be
the parent of Q. In what follows, for any pattern R, we write LO(R) for LO(R, T ) by
omitting T for simplicity. Suppose to contradict that P is not maximal in T . Then,
there exists some proper specialization P  of P , i.e., P < P , such that LO(P ) =LO(P  ).
If P < P  then P occurs in P  at some position, say, 1 ≤ p ≤ |P  |. There are twocases below.
(i) The case where p = 1: Then, P  is a non-preﬁx specialization of P . It immediately follows from Lemma 9 that LO(P ) = LO(P ). This is a contradiction.
(ii) The case where p = 1: Then, P  is a preﬁx specialization of P . By the deﬁnitionof the parent, there are the following cases for P and Q.
(ii.a) The case where Q = aP for some letter a ∈ Σ: Let Q = aP  ∈ ERP. Since
P  is a proper preﬁx specialization of P , Q is also a proper specialization of Q, i.e.,Q < Q . In this case, we have LO(Q ) = LO(aP ) = LO(a) ∩ (LO(P ) − |a|) by
Property (a) of Lemma 11. Since LO(P ) = LO(P ) by the assumption, it is obviousthat LO(a) ∩ (LO(P  ) − |a|) = LO(a) ∩ (LO(P ) − |a|). Again by applying Property(a) of Lemma 11 to the right hand side, we have LO(a) ∩ (LO(P ) − |a|) = LO(aP ).
Thus, we have Q < Q and LO(Q ) = LO(Q), which says that Q is not maximal in
T . However, this contradicts the assumption.
(ii.b) The case where Q = a ∗ P for some letter a ∈ Σ: Let Q = a ∗ P  ∈ ERP.
Since P  is a proper specialization of P (in this case, P  is not necessarily preﬁxspecialization), we have Q < Q . Furthermore, since LO(P ) = LO(P ) by assumption,
we can also show that LO(Q ) = LO(Q) by applying Property (b) of Lemma 11 as in
the proof for case (ii.a). Therefore, we see that Q is not maximal in T , and thus, thecontradiction is derived.
By combining cases (i), (ii.a), and (ii.b) above, we conclude by contradiction that
P is maximal in T . Furthermore, it is clear from the construction that P is strictly
shorter than Q in length. Hence, the result is proved.
2
Deﬁnition 4 A search graph for M w.r.t. P is a directed graph T = (M, P, I) withroots, where M is the set of nodes, i.e., the set of all maximal ﬂexible patterns in T ,P is the set of reverse edge such that (P, Q) ∈ P iﬀ P = P(Q) holds, and I ⊆ M isthe set of root patterns in T .
Since each non-root node has the unique parent in T from Theorem 12, the searchgraph T is acturally a directed tree with reverse edges. Therefore, we have the following corollary.
Corollary 13 Let T be any input string. Then, T = (M, E, I) is a spanning forest
for M with the root set I.

5. An Algorithm for Position-Maximal Flexible Pattern
Enumeration
In Fig. 3, we show a polynomial-space and polynomial-delay enumeration algorithm
PosMaxFlexMotif for maximal ﬂexible patterns. Given an input string T of lengthn, this algorithm enumerates all position-maximal patterns in T without duplicatesin polynomial time per maximal pattern using polynomial space in the input size nusing depth-ﬁrst search over the search tree T over M based on Corollary 13,
Recall that the search tree T for M has reverse edges only, that is, each edge of
T is directed from a child to its parent. Therefore, the ﬁrst step is to compute all
children, given a parent pattern P ∈ M. This can be done as follows.
Lemma 14 For any maximal ﬂexible patterns P, Q ∈ M, P = P(Q) if and only ifthere exists some constant letter a ∈ Σ such that either (i) Q = aP or (ii) Q = a∗Pholds.

Algorithm PosMaxFlexMotif(Σ, S, σ)
input: An alphabet Σ, an input string S,
minimum frequency threshold 0 ≤ σ ≤ |S|;
output: All maximal patterns in M;
1 Let ⊥ be the maximal pattern in T which equivalent to ε (the root pattern).
2 EnumMaximal(ε, σ);Procedure EnumMaximal(P, LO(P ), σ)input: A maximal pattern P and its left-location list LO(P ).
output: All maximal patterns that are descendants of P .
1 Compute LO(P );2 if |LO(P )| = 0 then return;3 if P is not maximal in S then return;
4 Output P ;5 foreach a ∈ Σ do begin:
6
EnumMaximal(aP, LO(aP ), σ);
7
EnumMaximal(a ∗ P, LO(a ∗ P ), σ);
7 endFigure 3: An algorithm PosMaxFlexMotif for enumerating all maximal ﬂexible
patterns in an input sequence.
Furthermore, since P(Q) is deﬁned also for non-maximal ﬂexible patterns Q, weknow that any ﬂexible pattern can be obtained from ﬁnite applications of the operations in above Lemma 14 to the empty pattern ε. Then, Theorem 12 gives a soundpruning strategy that once an enumerated pattern P gets non-maximal then we canimmediately prune all the descendants of P .
Secondly, we discuss how to eﬃciently test the maximality of a given pattern P .
The reﬁnement operator for ERP was introduced by Shinohara [12]. The following
version is due to [2].
Deﬁnition 5 A basic reﬁnement of a pattern P is any pattern Q obtained from P
by applying one of the following operations (r1) and (r2):(r1) Q is obtained by replacing some segment w ∈ Σ+ in P with either aw, wa, a∗ w,
w ∗ a for some a ∈ Σ.
(r2) Q is obtained by replacing a pair of consecutive segments v ∗ w ∈ Σ+ {∗}Σ+ in
P with vw.
For a pattern P , we deﬁne ρ(P ) ⊆ ERP to be the set of all basic reﬁnements ofP.
Lemma 15 A ﬂexible pattern P is maximal in T if and only if there is no basic
reﬁnement Q ∈ ρ(P ) such that LO(P, T ) = LO(Q, T ).

Corollary 16 The maximality of a ﬂexible pattern P in an input string T is decidablein O(|Σ|m2 n) time, where m = |P | and n = |T |.
On the shape of T , we have the following lemma.
Lemma 17 Let P ∈ M be any maximal pattern in T and m = |P |. Then,(i) The depth of P in T (the length of the unique path from the root to P ) is at
most m.
(ii) The branching of P in T (the number of the children for P ) is at most O(|Σ|m).
By combining the above lemmas, we have the main result of this paper. This saysthat our algorithm PosMaxFlexMotif is a memory and time eﬃcient algorithm
for discovering maximal ﬂexible patterns.
Theorem 18 Let Σ be an alphabet and T ∈ Σ∗ be an input string of length n ≥ 0.
Then, the algorithm PosMaxFlexMotif in Fig. 3 enumerates all position-maximal
patterns P in T without duplicates in O(|Σ|kmn2 ) delay per maximal pattern using
O(mn) space, where m = |P | and k = O(m) are the size and the number of variablesof the pattern P to be enumerated.
Corollary 19 The maximal pattern enumeration problem for the class ERP of ﬂexible patterns (or erasing regular patterns) w.r.t. position-maximality is solvable inpolynomial-space and polynomial-delay in the total input size.

6. A Practical Algorithm for Discovering documentmaximal ﬂexible patterns in a set of input strings
In this section, we consider the maximality based on the document occurrences andpresent a heuristic algorithm for solving the document-maximal pattern enumeration
problem for ERP using the algorithm in the previous section as a pruning technique.
Let Σ be a ﬁxed alphabet of constants. An input string set is a collection of
constant strings over Σ
S = {s1 , . . . , sd } ⊆ Σ∗ ,where each member si ∈ Σ∗ is called a document of S (i = 1, . . . , d). For a ﬂexible
pattern P ∈ ERP, the document-location list of P is deﬁned by the set DO(P, S) ={ 1 ≤ i ≤ d : P  si } of the indices of the documents in which P occurs. The
document frequency of P in S is deﬁned by |DO(P, S)|.
For 0 ≤ σ ≤ |S|, a pattern P is document σ-frequent if |DO(P, S)| ≥ σ. A pattern
P is document-maximal in S if there is no proper specialization Q of P that has thesame document-location list in S, i.e., P < Q and DO(P, S) = DO(Q, S). The following lemma justiﬁes the pruning strategy at Line 2 of Algorithm DocMaxFlexMotifin Fig. 4.

Algorithm DocMaxFlexMotif(Σ, S, σ)
input: An alphabet Σ, an input set S = {s1 , . . . , sk } ⊆ Σ∗ , 0 ≤ σ ≤ |S|;
output: All document-maximal patterns in DM;
1 Let ⊥ be the maximal pattern in T which equivalent to ε (the root pattern).
2 Let S = s1 # · · · #sk be an input string (# ∈ Σ).
3 DocEnumMaximal(⊥, LO(⊥, S), σ);Procedure DocEnumMaximal(P, LO(P ), σ)input: A maximal pattern P and its left-location list LO(P, S).
output: All maximal patterns that are descendants of P .
1 Compute DO(P, S) from LO(P, S);
2 if |DO(P, S)| < σ then return;3 if P is not position-maximal in S w.r.t. LO(P, S) then return;4 if P is document-maximal in S then output P ;5 foreach a ∈ Σ do begin:6
DocEnumMaximal(aP, LO(aP, S), σ);7DocEnumMaximal(a∗P, LO(a∗P, S), σ);
7 endFigure 4: An algorithm PosMaxFlexMotif for enumerating all maximal ﬂexible
patterns in an input sequence.

Lemma 20 (pruning by monotonicity) If P  Q then DO(P, S) ⊇ DO(Q, S).
Let S = {s1 , . . . , sk } ⊆ Σ∗ be an input document set and let # ∈ Σ) be a newdelimitor symbol. Then, we deﬁne an input string S = s1 # · · · #sk obtained from S
by concatenating all documents by the delimitor #. The following lemma ensure thesoundness of the pruning strategy at Line 3 of Algorithm DocMaxFlexMotif inFig. 4.
Lemma 21 (pruning by position-maximality) Let P be any ﬂexible pattern overΣ. If P is document-maximal in S then P is also a position-maximal in S.
Based on the above lemmas, we show the algorithm DocMaxFlexMotif forenumerating all document-maximal frequent ﬂexible patterns in a set of strings in
Fig. 4. Unfortunately, this algorithm is not shown to be of output-polynomial time.
Theorem 22 Let Σ be an alphabet and T ∈ Σ∗ be an input string of length n ≥0. Then, the algorithm DocMaxFlexMotif in Fig. 4 enumerates all documentmaximal patterns P in T without duplicates using O(mn) space, where m = |P | is thesize of the pattern P to be enumerated and k = O(m) is the number of variables of P .

7. Conclusion
In this paper, we consider the maximal pattern discovery problem for the class
ERP of ﬂexible patterns [9], which is also known as erasing regular patterns in machine learning. The motivation of this study is applications to the optimal patterndiscovery problem in machine learning and knowledge discovery. As a main result
we present a polynomial-space and polynomial-delay algorithm for enumerating all
maximal patterns appearing in a given string without duplicates in terms of postionmaximality deﬁned through the equivalence relation between the location lists. As
another application, we presented a heuristics algorithm for enumerating documentmaximal patterns in a collection of strings for the class ERP with non-trivial pruning
strategies.

References[1] D. Avis and K. Fukuda, Reverse Search for Enumeration, Discrete Applied
Mathematics, Vol. 65, 21–46, 1996.
[2] H. Arimura, R. Fujino, T. Shinohara, Protein motif discovery from positive examples by minimal multiple generalization over regular patterns, Proc. GIW’94,
39-48, Dec. 1994.
[3] H. Arimura, T. Uno, A polynomial space and polynomial delay algorithm forenumeration of maximal motifs in a sequence, Proc. ISAAC’05, LNCS 3827,
Springer, Dec. 2005.
[4] L. Devroy, L. Gyrﬁ and G. Lugosi, A Probabilistic Theory of pattern Recognition,
Springer Verlag, 1996.
[5] M. J. Kearns, R. E. Shapire, L. M. Sellie, Toward eﬃcient agnostic learning,
Machine Learning, 17(2–3), 115–141, 1994.
[6] W. Maass, Eﬃcient agnostic PAC-learning with simple hypothesis, In Proc.
COLT94, 67–75, 1994.
[7] H. Mannila, H. Toivonen, A. I. Verkamo, Discovery of frequent episodes in event
sequences, Data Min. Knowl. Discov., 1(3), 259–289, 1997.
[8] S. Miyano, A. Shinohara, T. Shinohara, Polynomial-time learning of elementary
formal systems, New Generation Comput. 18(3): 217–242, 2000.
[9] L. Parida, I. Rigoutsos, et al., Pattern discovery on character sets and realvalued data: linear-bound on irredandant motifs and eﬃcient polynomial timealgorithms, In Proc. SODA’00, 2000.
[10] N. Pisanti, M. Crochemore, R. Gross, M.-F. Sagot, A basis of tiling motifs for generating repeated patterns and its complexity of higher quorum, In
Proc. MFCS’03, 2003.
[11] S. Shimozono, H. Arimura, S. Arikawa, Eﬃcient discovery of optimal wordassociation patterns in large text databases, New Generation Comput. 18(1),49–60, 2000.
[12] T. Shinohara, Polynomial time inference of extended regular pattern Languages.
Proc. RIMS Symp. on Software Sci. & Eng., 115–127, 1982.
[13] X. Yan and J. Han, R. Afshar, CloSpan: mining closed sequential patterns inlarge databases, In Proc. SDM 2003, SIAM, 2003.
[14] J. Wang and J. Han, BIDE: eﬃcient mining of frequent closed sequences, In
Proc. IEEE ICDE’04, 2004.