Page 6 - 《软件学报》2021年第11期

3332 Journal of Software 软件学报 Vol.32, No.11, November 2021

5 (Key Laboratory of Knowledge Engineering with Big Data (Hefei University of Technology), Ministry of Education, Hefei 230009,
China)
6 (Mininglamp Academy of Sciences, Mininglamp Technology, Beijing 100084, China)
Abstract: Nonoverlapping conditional sequence pattern mining is a method of gap constrained sequence pattern mining. Compared with
similar mining methods, this method is easier to find valuable frequent patterns. The core of the problem is to calculate the support (or the
number of occurrences) of a pattern in the sequence, and then determine whether the pattern is frequent. The essence of calculating the
support is the pattern matching under nonoverlapping condition. The current studies employ the iterative search to find a nonoverlapping
occurrence, and then prune the useless nodes to calculate the support of the pattern. The computational time complexity of these
algorithms is O(m×m×n×W), where m, n, and W are the pattern length, sequence length, and maximum gap, respectively. In order to
improve the calculation speed of pattern matching under nonoverlapping condition, and effectively reduce sequence pattern mining time,
this study proposes an efficient and effective algorithm, which converts the pattern matching problem into a NetTree, then starts from the
minroot node of the NetTree, and adopts the backtracking strategy to iteratively search the leftmost child to calculate the nonoverlapping
minimum occurrence. After pruning the occurrence on the NetTree, the problem can be solved without further searching and pruning
invalid nodes. This study proves the completeness of the algorithm and reduces the time complexity to O(m×n×W). On this basis, the
study continues to indicate that there are other three similar solving strategies for this problem, iteratively finds the leftmost parent path
from the leftmost leaf, the rightmost child path from the rightmost root, and the rightmost parent path from the rightmost leaf. Extensively
experimental results verify the efficiency of the proposed algorithm in this study, especially, the mining algorithm adopting this method
can reduce the mining time.
Key words: pattern matching; sequence pattern mining; nonoverlapping condition; NetTree; backtracking strategy

[1]
模式匹配作为计算机科学的基本问题之一,包括大数据挖掘 在内的诸多研究都建立在模式匹配的基础
[6]
[5]
[4]
上,如序列模式挖掘 [2,3] 、时间序列分析与预测 、生物序列数据分析 、网络入侵检测 、正负序列分析 [7,8]
以及大空间数据库中的字符串搜索 [9,10] .近年来,具有间隙约束的模式匹配逐渐引起研究者们的广泛关注,如
Manber 等人 [11] 最先研究了具有间隙约束的模式匹配问题,但其模式中只有一个可变间隙,具有一定的局限性.
随着研究的深入,更多学者将注意力转向具有多个可变间隙约束模式匹配问题(或称间隙约束模式匹配问
题) [12] .具有多个可变间隙的模式匹配在诸多领域具有广泛的应用,例如,在计算生物学中,Navarro 和 Raffinot [13]
采用此种模式匹配提出了更为优化的搜索方法用来寻找特殊蛋白质位点,Drory 等人 [14] 实现了 RNA 序列的
motif 结构检测;在文本匹配方面,Cole 等人 [15] 在可变间隙近似模式匹配下有效地判断模式串是否在指定的文本
或字典中.特别需要指出的是,具有间隙约束模式匹配在序列模式挖掘领域具有重要应用 [16,17] .传统序列模式挖
掘研究只关注模式在序列中是否存在,而不关注模式在序列中出现的次数.这导致序列串“AC”与序列串
“ACACACAC”的作用相同,因此,传统序列模式挖掘方式会在诸如 DNA 序列等长序列挖掘中丢失诸多重要信
息.为了弥补传统序列模式挖掘的不足,可重复序列模式挖掘孕育而生 [18] ,这种挖掘方法更加关注模式在序列中
出现的次数 [19,20] .为了避免匹配的序列间隔过大,间隙约束序列模式挖掘孕育而生,其核心工作之一是计算模式
在序列中的出现次数,即支持度,实质上就是间隙约束模式匹配问题 [21] .在间隙约束序列模式挖掘和模式匹配问
题中,模式串可以写作 P=p 1 [min 1 ,max 1 ]p 2 …[min j−1 ,max j−1 ]p j …[min m−1 ,max m−1 ]p m 的形式 [22] ,其中,min j−1 和 max j−1
分别指 p j−1 和 p j 之间通配符的最小和最大个数 [23] .间隙约束作为一种新型的通配符,比传统通配符“?”和“*”更具
灵活性与适用性,这是因为其允许在 p j−1 和 p j 之间通配的字符数量是一个范围值,而非一个确定值.
无重叠条件的模式匹配作为间隙约束模式匹配的一种方法,最早是在文献[24]中提出,其是指允许序列中
的任意位置的字符重复使用,但不允许同一字符在相同位置多次使用.Wu 等人 [25] 严格形式化地给出了无重叠
条件模式匹配的定义,并理论证明了该问题的复杂度为 P.之后,文献[26]研究了无重叠条件序列模式挖掘,并有
效地解决了间隙约束序列模式挖掘难以兼顾 Apriori 性质和挖掘完备性的问题 [5,20] .下面举例说明无重叠条件
模式匹配问题.
例 1:给定序列串 S=s 1 s 2 s 3 s 4 s 5 s 6 s 7 s 8 =aggcaaga,模式串 P=p 1 [min 1 ,max 1 ]p 2 [min 2 ,max 2 ]p 3 =a[0,1]g[0,1]a.
子模式 a[0,1]g 指在 a 与 g 之间可以没有间隙或者有一个通配符“?”,也就是说,a 与 g 之间可以通配 0~1 个
字符.由图 1 可知:例 1 中满足间隙约束的出现共有 3 个,分别是〈1,3,5〉,〈5,7,8〉,〈6,7,8〉.出现〈5,7,8〉和〈6,7,8〉均在相