Page 7 - 《软件学报》2021年第11期
P. 7

武优西  等:无重叠条件严格模式匹配的高效求解算法                                                       3333


                 同位置使用了 s 7 的“g”和 s 8 的“a”,因此,这两个出现不满足无重叠条件.尽管出现〈1,3,5〉和〈5,7,8〉均使用了字符
                 s 5 =“a”,但这两条出现中的 s 5 分别与 p 3 和 p 1 进行匹配,因此,〈1,3,5〉和〈5,7,8〉构成了两个无重叠出现.
                                                  12 34 5 6 7 8
                                              s =  ag g c aa g a
                                                                  st
                                                  a ·   g ·   a · · ·   1  occurrence
                                                                  nd
                                                  · ·  · ·   a ·   g a  2 occurrence
                                                                  rd
                                                  · ·  · ·  ·   ag a  3 occurrence
                                Fig.1    All occurrences of pattern P=a[0,1]g[0,1]a in sequence S=aggcaaga
                                    图 1   模式 P=a[0,1]g[0,1]a 在序列 S=aggcaaga 中的所有出现
                    尽管 Wu 等人   [25,26] 提出了基于网树结构的模式匹配算法 NETLAP-Best 和 NETGap,这两种算法均采用在网
                 树结构上剪枝无效结点的策略,虽然得到了问题的完备解,但时间复杂度均为 O(m×m×n×W).这里 m,n 和 W 分别
                 为模式长度、序列长度及最大间隙.研究具有更低时间复杂度的完备性无重叠模式匹配算法具有重要的意义.这
                 是因为其是无重叠序列模式挖掘研究的重要基石.序列模式挖掘研究主要包含候选模式生成和支持度计算(即
                 模式匹配问题)两个部分.因此,影响模式挖掘速度的主要因素有两个:候选模式剪枝策略和模式支持度计算效
                 率.虽然候选模式剪枝策略对挖掘效率具有重要影响,但是在候选模式剪枝策略不变的情况下,模式支持度计算
                 效率在一定程度上也会影响挖掘效率;此外,支持度计算的准确性能够保证挖掘算法的完备性.
                    本文对具有长度约束的无重叠条件严格模式匹配问题进行研究,提出了一种高效求解算法 Nonoverlapping
                 NetTreeBacktracking(NetBack),该算法结合回溯策略,无需检测网树中无效结点,采用在网树上查找最左孩子路
                 径(leftmost child  path)的方式获得一个无重叠出现,并迭代此过程,即可实现无重叠条件模式匹配问题的求解.
                 NetBack 算法可将无重叠严格模式匹配算法的时间复杂度从 O(m×m×n×W)降为 O(m×n×W).在此基础上,本文指
                 出:除了最左孩子路径以外,还可以采用其他 3 种方式进行求解,分别为最左双亲路径(leftmost parent path)、最
                 右双亲路径(rightmost parent path)和最右孩子路径(rightmost child path),其中,最左双亲路径和最左孩子路径所
                 获得的无重叠出现完全一致;最右双亲路径和最右孩子路径所获得的无重叠出现完全一致.这 4 种方法均为完
                 备性求解算法,能够找到的无重叠出现数目是一致的.本文在真实生物数据上进行了大量的实验,与多种算法进
                 行了对比,并将 NetBack 算法应用于序列模式挖掘中进行实验,实验结果验证了本文算法的正确性与高效性.
                    本文第 1 节总结相关工作进展.第 2 节给出问题定义及相关理论证明.第 3 节介绍网树,并提出本文求解算
                 法 NetBack,分析 NetBack 算法的空间复杂度及时间复杂度.第 4 节实验验证算法的正确性及高效性.第 5 节给
                 出结论.

                 1    相关工作

                    目前,具有间隙约束的模式匹配问题可从以下几个方面进行划分:严格模式匹配还是宽松模式匹配,其中,
                 严格模式匹配可以细分为一次性条件、无重叠条件和无特殊条件;是否具有长度约束;是否为精确模式匹配.
                    文献[27]首次将具有间隙约束的模式匹配问题划分为严格模式匹配和宽松模式匹配:严格模式匹配                                 [28,29] 是
                 指使用模式串中的对应字符,在满足间隙约束的情况下,在序列串中对应的位置索引来表示出现;而宽松模式匹
                 配 [13,30] 只使用模式串中最后一个字符在序列串中的位置表示一个出现.严格模式匹配又存在 3 种不同条件的研
                 究,分别是:无特殊条件      [31−33] 、一次性条件 [5,28] 和无重叠条件 [24,25,34] .例 2 用来说明宽松模式匹配及 3 种条件下的
                 严格模式匹配之间的关系.
                    例 2:给定与例 1 相同的序列串 S 及模式串 P.表 1 给出了不同条件下的出现.
                    如表 1 所示,若按照宽松模式匹配,例 2 中有两个出现,分别为〈5〉和〈8〉.显然,宽松模式匹配忽略了匹配过程,
                 而严格模式匹配更注重匹配的细节.一次性条件指序列中任意位置的字符只能使用一次,所以满足该条件的严
                 格模式匹配出现为〈1,3,5〉和〈6,7,8〉.根据无重叠的定义可知:满足无重叠条件的严格模式匹配的出现有两个,可
                 以是{〈1,3,5〉,〈5,7,8〉}或{〈1,3,5〉,〈6,7,8〉}.无特殊条件指序列中任何位置的字符都可以多次使用,所以无特殊条件
   2   3   4   5   6   7   8   9   10   11   12