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

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

9
7
右双亲时,发现结点 n 不满足长度约束,根据回溯策略,此时选择结点 n ,得到第 2 个出现〈7,10,11,12〉.同理,依次
1
1
4
向前遍历绝对叶子结点,可得到出现〈3,6,8,9〉和〈1,4,5,7〉.特别地,在寻找出现〈1,4,5,7〉时,向上选择结点 n 的最右
2
3
1
双亲结点时,发现其最右双亲结点 n 已被使用,所以根据回溯策略,此时应选择结点 n 作为双亲结点.
1
1
(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)
(1,1) (1,3) (3,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.6 Leftmost parent path
图 6 最左双亲路径
(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)

(1,1) (3,3) (7,9) (12,12) (12,12)
2 4 (1,3) 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.7 Rightmost parent path
图 7 最右双亲路径

定理 6. 最右双亲路径得到的出现是模式在序列中的最大出现.
证明:同定理 2 的证明,可以证明最右双亲路径得到的出现是模式在序列中的最大出现. □
定理 7. 最右孩子路径得到的出现与最右双亲路径得到的出现相同,也是最大出现.
证明:同定理 5 的证明,可以证明最右孩子路径得到的出现与最右双亲路径得到的出现是一致的,是模式在
序列中的最大出现. □
例 11:给定与例 7 相同的模式串与序列串和长度约束,采用最大策略与回溯策略结合寻找无重叠出现.
根据例 10 可知:采用最右双亲路径找到的第 1 个出现为〈12,14,15,16〉,在全集 R 中最大出现为〈12,14,15,16〉.
从 R 中删除〈12,14,15,16〉及与它重叠的出现后,出现〈7,10,11,12〉为当前最大出现.最右孩子路径找到的第 2 个出
现就是〈7,10,11,12〉.以此类推,最右双亲路径可得到无重叠最大出现集:{〈1,4,5,7〉,〈3,6,8,9〉,〈7,10,11,12〉,〈12,14,15,
16
12
16〉}.若采用最右孩子路径,如图 8 所示,首先选择最大根结点 n ,但该结点不满足约束条件,向前访问结点 n ,
1 1
14
选择其最右孩子结点 n .迭代此过程,找到第 1 个出现〈12,14,15,16〉.以此类推,得到无重叠出现集{〈1,4,5,7〉,〈3,
2
6,8,9〉,〈7,10,11,12〉,〈12,14,15,16〉},这与最右双亲路径得到的结果是一致的.