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

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

5〉,〈5,6,7〉},|C|=2,即模式 P 在序列 S 中的无重叠出现数为 2.
2.2 问题分析
引理 1. 给定子模式 p j [min j ,max j ]p j+1 的两个子出现为〈a j ,a j+1 〉和〈b j ,b j+1 〉,如果 a j <b j 且 a j+1 >b j+1 ,则〈a j ,b j+1 〉和〈b j ,
a j+1 〉也是两个子出现;反之,若 a j <b j 且 a j+1 <b j+1 ,〈a j ,b j+1 〉和〈b j ,a j+1 〉不一定为子出现.
证明:我们之前的工作 [25] 根据最小数最大数原理已经证明:如果存在两个子出现〈a j ,a j+1 〉和〈b j ,b j+1 〉并满足
a j <b j 且 a j+1 >b j+1 ,那么〈a j ,b j+1 〉和〈b j ,a j+1 〉也一定是两个子出现;相反,若 a j <b j 且 a j+1 <b j+1 ,〈a j ,b j+1 〉和〈b j ,a j+1 〉不一定为
子出现.证毕. □
引理 2. 无重叠条件下的严格模式匹配问题是一个 P 问题.
证明:令集合 R 为出现全集,即 R 是由在不考虑无重叠条件时,模式 P 在序列 S 中所有满足间隙约束与长度
约束的出现构成的集合.现有无重叠出现集 C,包含 k 个无重叠出现,即 C={〈c 1,1 ,c 1,2 ,…,c 1,m 〉,〈c 2,1 ,c 2,2 ,…,c 2,m 〉,…,
〈c k,1 ,c k,2 ,…,c k,m 〉},其中,c i,1 <c i+1,1 (1≤i<k).根据引理 1 和我们之前的工作 [25] ,可得到一个同样包含 k 个无重叠出现
的集合 D,且 D 中的出现是有序的,即 D={〈d 1,1 ,d 1,2 ,…,d 1,m 〉,〈d 2,1 ,d 2,2 ,…,d 2,m 〉,…,〈d k,1 ,d k,2 ,…,d k,m 〉},其中,d h,j <d h+1,j
(1≤h<k,1≤j≤m).根据我们之前的工作 [25,26] ,对于集合 D,存在以下两种情况.
(1) 令〈f k,1 ,f k,2 ,…,f k,m 〉为 R 中最大出现,那么无论出现〈d k,1 ,d k,2 ,…,d k,m 〉是否是最大出现,都可被最大出现〈f k,1 ,
f k,2 ,…,f k,m 〉替换.从 R 中删除〈f k,1 ,f k,2 ,…,f k,m 〉以及与它有重叠的出现,此时〈f k−1,1 ,f k−1,2 ,…,f k−1,m 〉为最大出现.
同理,〈d k−1,1 ,d k−1,2 ,…,d k−1,m 〉可被〈f k−1,1 ,f k−1,2 ,…,f k−1,m 〉替换.重复上述过程,直到 R 为空.可得到包含 k 个无
重叠出现的无重叠最大出现集 F,F={〈f 1,1 ,f 1,2 ,…,f 1,m 〉,〈f 2,1 ,f 2,2 ,…,f 2,m 〉,…,〈f k,1 ,f k,2 ,…,f k,m 〉}.
(2) 令〈g 1,1 ,g 1,2 ,…,g 1,m 〉为 R 中最小出现,那么无论出现〈d 1,1 ,d 1,2 ,…,d 1,m 〉是否是最小出现,都可被最小出现
〈g 1,1 ,g 1,2 ,…,g 1,m 〉替换.从 R 中删除〈g 1,1 ,g 1,2 ,…,g 1,m 〉以及与它有重叠的出现,此时〈g 2,1 ,g 2,2 ,…,g 2,m 〉为最小
出现.同理,〈d 2,1 ,d 2,2 ,…,d 2,m 〉可被〈g 2,1 ,g 2,2 ,…,g 2,m 〉替换.重复上述过程,直到 R 为空.可得到包含 k 个无重
叠出现的无重叠最小出现集 G,G={〈g 1,1 ,g 1,2 ,…,g 1,m 〉,〈g 2,1 ,g 2,2 ,…,g 2,m 〉,…,〈g k,1 ,g k,2 ,…,g k,m 〉}.
所以,求解无重叠严格模式匹配问题可采取两种方式:一是选择最大出现得到无重叠最大出现集 F,我们称
此方法为最大策略;二是选择最小出现得到无重叠最小出现集 G,我们称此方法为最小策略.综上,最大策略和最
小策略都可得到无重叠严格模式匹配问题的完备解集,可证明此问题的计算复杂性为 P.证毕. □
3 网树与 NetBack 算法

3.1 网 树
我们首先介绍网树的基本定义.
定义 7. 网树结构 [25,26] 类似于树结构,具有以下的特点.
(1) 一棵网树可以有 n 个根结点,其中,n≥1;
(2) 除根结点外的任意结点可以有不止一个双亲,并且一个结点的所有双亲结点必须在网树的同一层;
i
(3) 网树允许同一结点出现在不同层,为了准确表示某一结点,使用 n 表示网树第 j 层的结点 i;
j
(4) 从一个结点到其祖先结点(或子结点)的路径存在很多条.
定义 8. 若网树有 m 层,则称第 m 层的叶子为绝对叶子结点.
定义 9. 从树根结点到绝对叶子结点的一条路径称为完全路径.
定义 10. 在网树中,用 nn〈 1 1 i , 2 2 i ,...,n 〉 m m i 表示一条完全路径,相应的出现表示为〈i 1 ,i 2 ,…,i m 〉.一棵 m 层网树的完
全路径长度是 m,因为绝对叶子结点在第 m 层.
引理 3. 网树上的一条完全路径对应模式 P 在序列 S 上的一个出现.
证明:在文献[40]中我们已经证明:模式 P 在序列 S 中的匹配问题可以转化为一棵网树进行求解,且每条完
全路径对应一个出现.也就是说,只要在网树中找到一条完全路径,就代表找到了一个出现. □
i
定义 11. 对于结点 n 来说,在所有双亲结点中,最大标签的双亲称为最右双亲结点,最小标签的双亲称为最
j