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

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

左双亲结点.在所有孩子结点中,最大标签的孩子称为最右孩子结点,最小标签的孩子称为最左孩子结点.
定义 12. 在网树中,一个结点可以到达不止一个根结点,结点可到达的最小根结点称为 minroot,最大根结点
称为 maxroot.根结点的 minroot 和 maxroot 都是它本身.同理,网树中的结点可以到达不止一个绝对叶子结点,
结点可到达的最小绝对叶子结点称为 minleaf,最大绝对叶子结点称为 maxleaf.绝对叶子结点层的 minleaf 和
maxleaf 都是它本身.
定义 13. 选择最小树根结点,并迭代最左孩子形成的完全路径称为最左孩子路径.类似地,我们有如下 3 种
定义:选择最小绝对叶子结点,并迭代最左双亲形成的完全路径称为最左双亲路径;选择最大绝对叶子结点,并
迭代最右双亲形成的完全路径称为最右双亲路径;选择最大树根结点,并迭代最右孩子形成的完全路径称为最
右孩子路径.
引理 4. 如果存在两条完全路径 A 和 B,若这两条路径没有经过相同的网树结点,则称 A 和 B 对应的出现为
无重叠出现.
b
证明:完全路径 A 和 B 分别表示为 n〈 1 a ,n 2 a ,...,n 〉 a m 和 nn〈 1 b , 2 b ,...,n 〉 ,对应的两个出现为 L A =〈a 1 ,a 2 ,…,a m 〉和
m
1 2 m 1 2 m
L B =〈b 1 ,b 2 ,…,b m 〉.因为 A 和 B 不包含相同结点,所以对于任意的 i(1≤i≤m),满足 a i ≠b i .因此,L A 和 L B 为两个无重
叠出现.证毕. □
根据无重叠出现的定义,序列中的字符并非是只可使用一次的,如何判断某一字符是否可以重复使用是一
个难题.与其他无重叠模式匹配算法相比,使用网树结构可以高效地处理无重叠条件,只需保证每层每个结点最
多使用一次即可.例 6 用于说明这一特点.
例 6:根据给定序列串 S=atatgtagatgattga 和模式串 P=a[0,2]t[0,2]g[0,1]a,可得到如图 3 所示的网树.

1 3 7 9 12 16

2 4 6 10 13 14
5 8 11 15

7 9 12 16
Fig.3 NetTree of pattern P=a[0,2]t[0,2]g[0,1]a in sequence S=atatgtagatgattga
图 3 模式 P=a[0,2]t[0,2]g[0,1]a 在序列 S=atatgtagatgattga 上的网树
在图 3 中,可以找到所有满足间隙约束的出现,分别是〈1,2,5,7〉,〈1,4,5,7〉,〈3,4,5,7〉,〈3,6,8,9〉,〈7,10,11,12〉,〈9,10,
11,12〉,〈12,13,15,16〉,〈12,14,15,16〉.易知,〈1,2,5,7〉与〈3,4,5,7〉是重叠的出现,因为这两个出现都使用了第 3 层的结
7
7
5
点 n 和第 4 层的结点 n ;而出现〈1,2,5,7〉与出现〈7,10,11,12〉就是两个无重叠出现,因为在网树中,结点 n 与结点
3 4 1
7
n 为不同结点.
4
3.2 NetBack算法
3.2.1 创建网树
我们通过例 7 来展示创建网树的原理,并说明网树所具有的优势.
例 7:给定与例 6 相同的模式串与序列串,若长度约束为 LEN=[5,7],则利用网树结点的 minroot 和 maxroot
及 minleaf 和 maxleaf,可以有效地处理长度约束.具有最小、最大根及最小、最大叶子标记的网树如图 4 所示.
在图 4 中,结点右上的标记为此结点可到达的 minroot 和 maxroot,右下的标记为此结点可到达的 minleaf
4
和 maxleaf.这里以 s 4 =t 为例,说明如何创建结点 n 并计算其 minroot 和 maxroot 值.由于 s 4 =t=p 2 且 4−1−1=2 满
2
1
4
1
足[0,2]间隙约束,此时创建结点 n ,并与结点 n 建立父子关系,使其 minroot 和 maxroot 值与结点 n 的 minroot
1
1
2
4
4
3
3
和 maxroot 值一致,均为 1;又由于结点 n 与结点 n 也满足间隙约束,故结点 n 与结点 n 也建立父子关系,同时,
1
2
2
1
4
4
4
3
结点 n 的 minroot 从当前 1 和结点 n 的 minroot=3 中选择最小值,故结点 n 的 minroot=1;结点 n 的 maxroot 从
2
2
1
2