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

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

坏情况下的空间复杂度为 O(m×n×W).证毕. □
定理 4. NetBack 算法的时间复杂度为 O(m×n×W).
证明:NetBack 算法时间开销由两部分组成——创建网树和计算出现.
i
• 在创建网树方面,由于算法 1 的第 7 行结点 n 最多存在 W 个双亲结点,易知网树创建及更新最小、最
j
大根的时间复杂度为 O(m×n×W);同理,更新最小、最大叶子的时间复杂度也为 O(m×n×W).
• 在计算出现方面,根据定理 1 可知,每个结点最多被访问一次.根据定理 3 可知,网树上最多有个 m×n 结
点,因此计算出现的时间复杂度为 O(m×n).因此,NetBack 算法的时间复杂度为
O(m×n×W+m×n×W+m×n)=O(m×n×W). □
例如,在例 8 中采用最左孩子路径方式,从最小树根结点开始结合回溯策略得到无重叠最小出现集,在这个
过程中,每个结点最多被访问一次.找到第 2 个无重叠出现〈3,6,8,9〉后,它左边的结点均不会被后面的出现使用.
14
4
4
7
也就是说,结点 n 不可能与结点 n 及它之后的根结点存在父子关系,于是无需再次访问结点 n ,而结点 n 从
2
1
2
2
未被访问.在图 5 中,白色结点均未被访问过,其他颜色结点均被访问过一次.
3.4 其他3种寻径算法及分析
除最左孩子路径(leftmost child path)外,还存在 3 种类似的寻径方式,分别是最左双亲路径(leftmost parent
path)、最右双亲路径(rightmost parent path)、最右孩子路径(rightmost child path).这 4 种不同的寻径方式分别对
网树进行不同方向的遍历,均可与回溯策略相结合,求得无重叠严格模式匹配问题的完备解集.
定理 5. 最左双亲路径得到的出现与最左孩子路径得到的出现相同,也是最小出现.
证明:采用反证法证明.假设当前网树上最小出现 L A =〈a 1 ,a 2 ,…,a m 〉与最左双亲路径策略所获的第 1 个出现
L B =〈b 1 ,b 2 ,…,b m 〉是不同的.由最左双亲定义可知,b m 为第 m 层可到达树根结点层的最小绝对叶子结点.这样存在
如下两种情况.
(1) a j 与 b j 完全不同,即所有的 a j ≠b j (1≤j≤m).由于 L A 是最小出现,因此有 a j <b j (1≤j≤m),这样 a m <b m .这就
是说,能够从绝对叶子层到达树根层的最小结点是 a m ,这与假定 b m 是可到达树根结点层的最小绝对
叶子结点矛盾.
(2) a j 与 b j 局部有不同.由于 L A 是最小出现,所以有 a j <b j (1≤j≤m).我们从如下两方面进行分析:
① 假定 j=m,即 a m <b m .这与情形(1)相同,这种情况与假定 b m 为第 m 层可到达树根结点层的最小绝对
叶子结点矛盾.
② 假定 1≤j<m 且 a j+1 =b j+1 .由于 a j <b j ,且 b j+1 也是 a j 的孩子结点,即 a j 也是 b j+1 的双亲结点,因此对
于 b j+1 结点来说,最左双亲结点是 a j ,这与在出现 L B 中 b j+1 选择 b j 作为最左双亲结点矛盾.
综上,所有假设均存在矛盾,因此,L B 是与 L A 完全一致的出现,即最左双亲路径得到的出现与最左孩子路径
得到的出现都是最小出现.证毕. □
例 9:给定与例 7 相同的模式串与序列串和长度约束,采用最小策略与回溯策略结合寻找无重叠出现.
根据例 8 已知:采用最左孩子路径找到的第 1 个出现为〈1,2,5,7〉,而〈1,2,5,7〉是全集 R 中的最小出现.从 R 中
删除〈1,2,5,7〉及与它重叠的出现后,出现〈3,6,8,9〉为当前最小出现,最左孩子路径找到的第 2 个出现就是〈3,6,8,
9〉.以此类推,最左孩子路径可得到无重叠最小出现集{〈1,2,5,7〉,〈3,6,8,9〉,〈7,10,11,12〉,〈12,13,15,16〉}.若采用最左
7
5
双亲路径,如图 6 所示,首先访问最小绝对叶子结点 n ,向上选择最左双亲结点 n .迭代此过程,找到第 1 个出现
3
4
〈1,2,5,7〉.以此类推,得到无重叠出现集{〈1,2,5,7〉,〈3,6,8,9〉,〈7,10,11,12〉,〈12,13,15,16〉}.这与最左孩子路径得到的
结果是一致的.
综上,只要采用最小策略,无论是最左孩子路径方式还是最左双亲路径方式,均能得到无重叠最小出现集.
例 10:给定与例 7 相同的模式串与序列串和长度约束,最右双亲路径方式寻径过程如图 7 所示.
16
15
若采用最右双亲路径,如图 7 所示,首先选择最大绝对叶子结点 n ,向上选择最右双亲结点 n .迭代此过
4
3
10
12
程,可得到第 1 个出现〈12,14,15,16〉.向前访问绝对叶子结点 n ,迭代选择其最右双亲结点,当选择结点 n 的最
2
4