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

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

(1) INSGrow [24] 算法.该算法是最早提出的无重叠严格模式匹配算法,其不采用回溯策略,而是基于最左
原则寻找出现,其时间复杂度为 O(m×n),但会造成丢失可行解的现象.与 INSGrow 算法相比,本文算法
能够得到问题的完备解集.
(2) NETLAP-Nonpruning [25] 算法.该算法的时间复杂度与本文算法一致,但因其不采用回溯策略,也会造
成可行解的丢失.与 NETLAP-Nonpruning [25] 算法的解数量进行对比,验证本文算法中回溯策略的必
要性.
(3) NETLAP-Best [25] 算法和 NETGap [26] 算法.这两种算法均采用网树结构进行求解,其求解原理基本相似,
都是在找到一个无重叠出现后必须对网树进行剪枝操作,以便实现完备性求解.因此,这两种算法的
时间复杂均为 O(m×m×n×W).这两种算法的差异在于:NETLAP-Best 算法采用最右双亲路径方式,而
NETGap 算法采用最左孩子路径方式.为了验证本文算法解的完备性,与 NETLAP-Best 算法和
NETGap 算法的解数量进行对比;同时,为了验证本文算法的高效性,与 NETLAP-Best 算法和 NETGap
算法的运行时间进行对比.
除本文 NetBack 算法外,还存在另外 3 种不同寻径方式的算法:NetBack-rrtl 算法、NetBack-rltr 算法和
NetBack-lltr 算法.这 3 种算法均采用网树结构与回溯策略相结合的方式,但分别采用最右孩子路径(从最大根结
点开始向下迭代搜索最右孩子结点)方式、最右双亲路径(从最大绝对叶子结点开始向上迭代搜索最右双亲结
点)方式和最左双亲路径(从最小绝对叶子结点开始向上迭代搜索最左孩子结点)方式实现求解.
4.3 实验结果与分析
5 种算法在 9 个模式 8 种序列 S1~S8 上关于无重叠严格模式匹配问题的解如图 9 所示,5 种算法在 9 个模
式 8 种序列上的运行时间见表 5.我们从如下几方面进行分析.
(1) NetBack 算法和 NETLAP-Best 算法、NETGap 算法都是完备算法,而 INSGrow 算法和 NETLAP-
Nonpruning 算法会丢失可行解.在图 9 中的 72 个实例上,NetBack 算法和 NETLAP-Best 算法、NETGap
算法的结果个数是相同的,且总是大于或者等于 INSGrow 算法和 NETLAP-Nonpruning 算法的结果,
这同时也验证了 NetBack 的正确性.例如,模式 P3 在序列 S1 上,NetBack 算法和 NETLAP-Best 算法、
NETGap 算法的出现数均为 203,而 INSGrow 算法和 NETLAP-Nonpruning 算法得到的出现数分别为
80 和 151.因此,真实生物数据的实验结果验证了 NetBack 算法的完备性,同时也验证了回溯策略的必
要性.
(2) NetBack 算法的求解速度快于 NETLAP-Best,NETLAP-Nonpruning 及 NETGap 算法.INSGrow 算法运
行时间最短,这是因为 INSGrow 算法是最简单的,而其他算法均比 INSGrow 算法复杂;但是 INSGrow
算法会丢失大量可行解,解的质量明显差于其他算法.通过表 5 可以看出,在 72 个实例上,除 INSGrow
算法外,NetBack 算法在大多数情况下求解速度是最快的,个别情况下,NETLAP-Nonpruning 算法求解
速度最快,均比 NETLAP-Best 算法和 NETGap 算法要快.例如在表 5 中,9 个模式在序列 S7 上,NetBack
算法的运行时间有 7 个是最快的,NETLAP-Nonpruning 算法的运行时间有 2 个是最快的,在其他实例
中也有类似现象.在全部 72 个实例中,NetBack 算法有 50 个是求解速度最快的,这说明 NetBack 算法
具有较优的求解效率.
(3) 尽管 NetBack 算法运行效率整体最优,但与 NETLAP-Best 算法和 NETGap 算法的差异不大,原因如下:
从图 5 中可以看出,NETLAP-Best 算法和 NETGap 算法需要剪枝的结点数量在整个网树中的占比很
小,其剪枝消耗的时间在整个算法运行时间中占比也很小.因此,尽管本文算法采用回溯策略降低了
算法的求解复杂度,但是运行时间差异不大.
(4) NetBack 算法与 NETLAP-Nonpruning 算法运行时间相差较小.通过表 5 可以看出,NetBack 算法与
NETLAP-Nonpruning 算法运行时间相近,这是因为这两种算法的时间复杂度均为 O(m×n×W).
NetBack 算法与 NETLAP-Nonpruning 算法都不对网树进行无效结点的查找及剪枝,网树中的结点最
多被访问一次,而 NETLAP-Best 算法和 NETGap 算法需要多次访问网树结点,时间复杂度较高.虽然