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

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

下的严格模式匹配出现有 3 个,即〈1,3,5〉,〈5,7,8〉和〈6,7,8〉.相对于一次性条件及无重叠条件,无特殊条件可以得到
问题的全部解,但这也会造成问题解空间呈指数级增长,并且可能得到过多的无用解.一次性条件虽然有效地限
制了解空间,但其要求过于苛刻,也会遗漏许多有价值的信息.而无重叠条件处于两者之间,即限制了解的个数,
又可得到更多的重要信息.
Table 1 Comparison of occurrences under different conditions
表 1 不同条件下出现的对比
条件 出现数 出现
宽松模式匹配 2 〈5〉,〈8〉
无特殊条件下严格模式匹配 3 〈1,3,5〉,〈5,7,8〉,〈6,7,8〉
一次性条件下严格模式匹配 2 〈1,3,5〉,〈6,7,8〉
无重叠条件下严格模式匹配 2 〈1,3,5〉,〈5,7,8〉或〈1,3,5〉,〈6,7,8〉

对出现的总长度进行约束,即出现中最大位置与最小位置的差需满足一定范围.目前,许多模式匹配研究都
使用了长度约束 [29,35] ,并且在序列模式挖掘 [36,37] 中也引入了长度约束.假设例 1 中的最小长度约束和最大长度
约束分别为 4 和 5,那么满足长度约束的出现只有〈1,3,5〉和〈5,7,8〉,因为这两个出现的长度分别为 5−1+1=5,
8−5+1=4,在长度约束范围内.但出现〈6,7,8〉不合法,因为它的长度为 8−6+1=3,不在范围内.
模式匹配问题作为序列模式挖掘的核心,与序列模式挖掘的关系密不可分.因此,表 2 中对比了几种具有间
隙约束的模式匹配工作及序列模式挖掘工作.
Table 2 Comparison of related work
表 2 相关工作的对比
相关工作 匹配/挖掘 间隙个数 严格/宽松 匹配类型 约束条件 长度约束
Manber 等人 [11] 模式匹配 一个可变间隙 严格 精确 无 无
①
②
Bille 等人 [38] 模式匹配 多个可变间隙 宽松 /严格 精确 − /无 −
Fredriksson 等人 [30] 模式匹配 多个可变间隙 宽松 近似 − −
Zhang 等人 [18] 序列模式挖掘 多个可变间隙 严格 精确 无 无
Chen 等人 [29] 模式匹配 多个可变间隙 严格 精确 一次性 有
Liu 等人 [39] 模式匹配 多个可变间隙 严格 精确 一次性 有
Ding 等人 [24] 序列模式挖掘 多个可变间隙 严格 精确 无重叠 有
Wu 等人 [26] 序列模式挖掘 多个可变间隙 严格 精确 无重叠 有
Wu 等人 [34] 模式匹配 多个可变间隙 严格 近似 无重叠 有
Wu 等人 [25] 模式匹配 多个可变间隙 严格 精确 无重叠 有
本文 模式匹配 多个可变间隙 严格 精确 无重叠 有
注:① 该文献设计了两种算法,分别对严格模式匹配和宽松模式匹配进行研究;
② 宽松模式匹配通常不考虑一次性条件和长度约束问题.本文以“−”表示不予考虑
通过表 2 可以看出,本文的研究与文献[25]是一致的,都是无重叠条件下具有多个可变间隙约束的严格精确
模式匹配.而本文的研究与文献[25]的差异在于如下几点.
(1) 降低了求解算法的时间复杂度.
尽管 Wu 等人 [25,26] 利用网树结构得到了无重叠严格模式匹配问题的完备解,但每次获得一个无重叠出现
后,需要在网树上查找并剪枝无效结点,以实现完备性求解.这造成上述文献的求解算法时间复杂度较高.本文
拟研究一个更高效的完备性求解算法,无需查找并剪枝无效结点就可实现问题求解,并将完备性算法的时间复
杂度从 O(m×m×n×W)降低为 O(m×n×W).例 3 用来说明文献[25]提出的 NETLAP-Best 算法工作原理.
例 3:假设序列串 S=actataagg,模式串 P=a[0,1]t[0,1]a[1,3]g.根据序列串及模式串,可得到如图 2 所示的网树.
由图 2 可以看出,模式 P 在序列 S 中存在两条无重叠出现,分别为〈1,3,4,8〉和〈4,5,7,9〉.若采用文献[25]的
NETLAP-Best 算法进行求解,从最大叶子结点,即第 4 层的结点 9 开始向上迭代寻找最右双亲结点,找到第 1 条
出现〈4,5,7,9〉后,必须对网树进行无效结点的查找及剪枝,即必须剪枝第 3 层结点 6,这是因为 NETLAP-Best 算法
不采用回溯策略,若不剪枝第 3 层结点 6,在找到子出现〈6,8〉后,会发现第 2 层结点 5 不可重用,从而放弃这条路