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

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

Table 8 Comparison of mining time on sequences DNA1~DNA5
表 8 在序列 DNA1~DNA5 上挖掘时间对比
运行时间(ms)
算法
DNA1 DNA2 DNA3 DNA4 DNA5
NOSEP 920 3 962 13 525 39 140 78 749
NOSEP-back 889 3 759 12 932 38 221 77 329
通过图 11 可以看出,NOSEP-back 算法与 NOSEP 算法得到的频繁模式数量是一致的,这验证了 NetBack 算
法支持度计算的正确性.通过表 8 可以看出,NOSEP-back 算法的运行速度在整体上要略快于 NOSEP 算法.造成
这种现象的原因如下:一方面,我们优化了支持度计算方法,使 NetBack 算法较之 NETGap 算法具有更低的时间
复杂度,但是由于网树中可剪枝结点的占比较小,所以虽然 NetBack 算法的实际运行速度快于 NETGap 算法,但
差异不大;另一方面,候选空间剪枝对挖掘效率有着重要影响,本文只对支持度计算方法进行了优化,未对候选
空间剪枝进行优化.因此,NOSEP-back 算法运行速度只是略快于 NOSEP 算法,但没有显著差异.

5 结 论

本文研究了具有多个可变间隙约束的无重叠严格模式匹配问题,它是一种允许序列中的任意位置的字符
重复使用,但不允许同一字符在相同位置多次使用、模式串中包含多个可变间隙约束且具有长度约束的严格精
确模式匹配.本文针对该问题当前求解算法存在的不足,提出了基于网树结构及回溯策略的求解算法 NetBack
算法,有效地降低了时间复杂度,提高了算法的效率,为提高无重叠序列模式挖掘的效率提供了基础.本文理论
证明了 NetBack 算法的完备性与正确性,并理论证明了该算法的空间复杂度和时间复杂度都为 O(m×n×W),其
中, m,n 和 W 分别为模式长度、序列长度及最大间隙.通过真实生物数据实验,验证了 NetBack 算法的正确性与
高效性.此外,本文指出:除 NetBack 算法所采用的最左孩子路径外,还存在其他 3 种求解策略,分别为最左双亲路
径、最右双亲路径和最右孩子路径,并通过理论证明和实验验证了这 3 种求解策略的可行性与正确性.
本文基于网树结构提出了 NetBack 算法,该算法较之以往算法具有较低的时间复杂度,具有较高的求解效
率.虽然采用网树结构可以直观易懂地表示所有出现,并解决无重叠条件严格模式匹配问题,但网树结构的创建
过程较为复杂,这会增加算法的时间开销.特别是从定理 4 的证明可以看出,若不建立网树,则可以将算法的时间
复杂度降低为 O(m×n).因此,如何在不建立网树结构的情况下,有效地减少无重叠模式匹配及挖掘问题的求解
时间,值得进一步探索.同时,无重叠模式匹配在其他领域的应用也值得进一步研究.

References:
[1] Wu X, Zhu X, Wu G, et al. Data mining with big data. IEEE Trans. on Knowledge and Data Engineering, 2014,26(1):97−107.
[2] Li C, Yang Q, Wang J, et al. Efficient mining of gap-constrained subsequences and its various applications. ACM Trans. on
Knowledge Discovery from Data, 2012,6(1):Article No.2.
[3] Song W, Rong K. Mining high utility sequential patterns using maximal remaining utility. In: Proc. of the Int’l Conf. on Data
Mining and Big Data. Cham: Springer-Verlag, 2018. 466−477.
[4] Tan CD, Min F, Wang M, et al. Discovering patterns with weak-wildcard gaps. IEEE Access, 2016,4(1):4922−4932.
[5] Wu X, Zhu X, He Y, et al. PMBC: Pattern mining from biological sequences with wildcard constraints. Computers in Biology and
Medicine, 2013,43(5):481−492.
[6] Peng H, Li J, Li B, et al. Fast multi-pattern matching algorithm on compressed network traffic. China Communications, 2016,13(5):
141−150.
[7] Jiang X, Xu T, Dong X. Campus data analysis based on positive and negative sequential patterns. Int’l Journal of Pattern
Recognition and Artificial Intelligence, 2019,33(5):Article No.1959016.
[8] Dong X, Qiu P, Lü J, et al. Mining top-k useful negative sequential patterns via learning. IEEE Trans. on Neural Networks and
Learning Systems, 2019,30(9):2764−2778.
[9] Li F, Yao B, Tang M, et al. Spatial approximate string search. IEEE Trans. on Knowledge & Data Engineering, 2013,25(6):
1394−1409.