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

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

4
4
3
当前 1 和结点 n 的 maxroot=3 中选择最大值,故结点 n 的 maxroot=3.因此,结点 n 右上方标记为(1,3).当网树创
2
2
1
3
建完毕后,从叶子层至树根层逐层更新每个结点的 minleaf 和 maxleaf.这里以结点 n 为例,易知其可抵达的最小
1
3
叶子为 7,最大叶子为 9,于是,结点 n 右下方的标记为(7,9).运用最小、最大根和最小、最大叶子,可以方便地确
1
定该结点是否满足长度约束:若该结点的长度区间[minleaf−maxroot+1,maxleaf−minroot+1]与长度约束 LEN 存
9
在交集,那么此结点就满足长度约束;否则,就不满足长度约束.如结点 n ,其 minleaf 和 maxleaf 为(12,12),minroot
1
9
和 maxroot 为(9,9),那么此结点的长度区间为[4,4],与长度约束 LEN=[5,7]不存在交集,所以,结点 n 不满足长度
1
约束,即出现〈9,10,11,12〉不满足长度约束.因此,本例中满足间隙约束及长度约束的出现全集 R 为
{〈1,2,5,7〉,〈1,4,5,7〉,〈3,4,5,7〉,〈3,6,8,9〉,〈7,10,11,12〉,〈12,13,15,16〉,〈12,14,15,16〉}.
(1,1) (3,3) (7,7) (9,9) (12,12) (16,16)
1 3 7 9 12 16
(7,7) (7,9) (12,12) (12,12) (16,16) (16,16)
(3,3)
(1,1) (1,3) (7,9) (12,12) (12,12)
2 4 6 10 13 14
(7,7) (7,7) (9,9) (12,12) (16,16) (16,16)
(1,3) (3,3) (7,9) (12,12)
5 8 11 15
(7,7) (9,9) (12,12) (16,16)
(1,3) (3,3) (7,9) (12,12)
7 9 12 16
(7,7) (9,9) (12,12) (16,16)
Fig.4 NetTree with minroot, maxroot, minleaf, and maxleaf
图 4 具有最小、最大根及最小、最大叶子的网树

i
本文创建网树的基本原理如下 [25,26] :逐一读取序列中每个字符 s i ,若其与 p 1 相同,则直接创建网树树根 n ,
1
i
并设置最小、最大根均为 i;若其与 p j (j>1)相同,且第 j−1 层存在与 s i 满足间隙约束条件的结点,则创建结点 n ,
j
i
并在第 j−1 层寻找所有与结点 n 满足间隙约束的双亲结点,建立父子关系,并更新结点 n 的最小、最大根.当全
i
j j
部字符读取完毕后,网树创建完毕.此时从网树的叶子层向树根层,逐层逐一更新各个结点的最小、最大叶子.具
体创建算法如算法 1 所示.
算法 1. CreNetTree.
输入:序列 S 及模式 P.
输出:NetTree.
1: for i=1 to n step 1 do
2: for j=1 to m step 1 do
3: if p 1 =s i then
i
4: NetTree[1].add( n )并设置最小、最大根均为 i;
1
5: else if p j =s i 且第 j−1 层存在与 i 满足间隙约束的结点 then
i
6: NetTree[j].add( n );
j
i
7: 与第 j−1 层满足间隙约束的所有结点建立父子关系,并更新 n 的最小、最大根;
j
8: end if
9: end for
10: end for
11: for j=m to 1 step −1 do