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

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

5: return BackTracking(level+1,NetTree,m,LEN,G);
6: else
7: return BackTracking(level−1,NetTree,m,LEN,G);
8: end if
3.2.3 求解算法 NetBack
定理 1. 无重叠出现 L 1 为最小出现,则无重叠出现 L 2 不会也不可能用到 L 1 左边的结点.
证明:采用反证法证明.假设无重叠出现 L 1 =〈a 1 ,a 2 ,…a j ,a j+1 ,…,a m 〉为当前最小出现,且无重叠出现 L 2 可用 L 1
左边的结点,即同时存在出现 L 2 =〈b 1 ,b 2 ,…b j ,b j+1 ,…,b m 〉,其中,1≤k≤j 时 a k <b k ,且 j+1≤k≤m 时 a k >b k .根据引理 1
可知:若同时存在出现 L 1 和 L 2 ,那么一定存在出 L′ =〈a 1 ,a 2 ,…a j ,b j+1 ,…,b m 〉和出现 L′ =〈b 1 ,b 2 ,…b j ,a j+1 ,…,a m 〉可替换
1
2
出现 L 1 和 L 2 .又因为 j+1≤k≤m 时 a k >b k ,那么 L 1 与 L′ 相比, L′ 为当前最小出现,这与假设 L 1 为最小出现矛盾.
1
1
因此,若无重叠出现 L 1 为最小出现,那么无重叠出现 L 2 一定不会用到 L 1 左边的结点.证毕. □
同理,若无重叠出现 L 3 为当前最大出现,则无重叠出现 L 4 不会也不可能用到 L 3 右边的结点.
算法 3 给出本文 NetBack 算法.该算法首先调用算法 1 创建网树,然后对最小网树树根结点调用算法 2 回
溯获得最左孩子路径 G:如果结果为 1,则无重叠出现集 C 获得路径 G 所对应的最小出现,并依据定理 1 删除路
径 G 及其以左结点.迭代这一过程,直至网树中所有树根结点处理完毕.
算法 3. NetBack.
输入:序列 S,模式 P 以及长度约束 LEN.
输出:无重叠出现集 C.
1: 使用算法 1 创建网树;
2: for l=1 to 根结点个数 step 1 do
3: G[1]=第 l 个根结点;
4: ret=BackTracking(1,NetTree,|P|,G);
5: if ret=1 then
6: C=C∪G.nodelabel;
7: 依据定理 1,删除路径 G 及其以左结点;
8: end if
9: end for
10: return C;
3.3 算法分析
定理 2. NetBack 算法是完备算法.
证明:首先证明 NetBack 算法采用算法 2 获得最左孩子路径的方式是一种最小策略.显然,算法 2 中 g 1 是最
小树根结点,因此 g 1 是所有出现中的最小值.现在假设 g k 是所有出现在第 k 层的最小值且 g k+1 是 g k 的最左孩子
结点(1≤k<m).我们将证明 g k+1 是所有出现在 k+1 层的最小值.采用反证法证明.假设 l k+1 是所有出现在第 k+1 层
的最小值,即 g k+1 >l k+1 .设 l k+1 的最左双亲是 l k ,则 l k 与 g k 存在以下 3 种情况.
(1) l k <g k .这与假设 g k 是所有出现在第 k 层的最小值矛盾.

(2) l k >g k .因此,〈g k ,g k+1 〉和〈l k ,l k+1 〉均为子出现.因为 g k+1 >l k+1 ,根据引理 1,〈g k ,l k+1 〉也是一个子出现.又由于 g k
是所有出现在第 k 层的最小值,因此 g k <l k .这与假设 l k 是 l k+1 的最左双亲矛盾.
(3) l k =g k .这样,〈g k ,g k+1 〉与〈g k ,l k+1 〉也是两个子出现.但是 g k+1 >l k+1 ,这与假设 g k+1 为 g k 的最左孩子矛盾.
综上,所有情况均不成立,所以 g k+1 是所有出现在 k+1 层的最小值.故算法 2 采用最左孩子路径得到的出现
为模式在序列中的最小出现.通过引理 2 可知,最小策略可得到完备解集,因此 NetBack 算法是完备算法. □
定理 3. NetBack 算法的空间复杂度为 O(m×n×W),其中,m,n 和 W 分别为模式长度、序列长度及最大间隙.
证明:由于网树最多有 m 层,每层结点最多有 n 个,每个结点最多有 W 个双亲结点,因此,NetBack 算法在最