文档介绍：断头指标25
Affix Tree(1)
Prefixes of t are suffixes of 反(t)
Prefix Tree(t) = Suffix Tree(反(t))
Example:
T = b a a b b e(3)
Unidirectional Affix Tree Construction
CAT(T)=CST(T)+CPT(T)
= CST(T)+CST(反(T))
CST(Ta)+CST(反(Ta))
=CST(Ta)+CST(a反(T))
=CST(Ta)+CPT(Ta)
=CAT(Ta)
19
Constructing Affix Tree(4)
Bidirectional Affix Tree Construction
Extra 生長點
20
Constructing Affix Tree(5)
Algorithm for constructing CST in reversed order
Algorithm for combining the construction of CST & CPT Uni-directional
Algorithm for coordinating 生長點 Bidirectional
21
Online construction of Suffix Tree in reversed order
22
Online construction of Suffix Tree in reversed order
Goal: Building CST(at) from CST(t).
Weiner’s algorithm.
Idea: Since CST(t) already represents all suffixes of CST(at) except at. Only the suffix at needs to be inserted.
23
Online construction of Suffix Tree in reversed order
α(t) longest nested prefix(t)
Additional Information: We assume that we have |α(at)| in each iteration of the following algorithm. With this, we don’t need the ”indicator vector“ used by Weiner.
|α(at)| = the length of α(at)
24
From CST(t) to CST(at)
Idea: If we insert the suffix at into the CST(t), the leaf for at will branch at the location representing α(at) in CST(t).
Why?
25
Definition
Reference Pair
(base, (offset, length))
(b,(o,l)) is a reference pair for s if path(b)t[o,…,o+l] = s.
(b, (o, l))
b
b1
b2
b3
b4
l1
l2
l3
(b1, (o, l))
(b2, (o+ l1, l-l1))
(b3, (o+l1+l2, l-l1-l2))
…………….A B C A B C A B C A B C
o
l
O+l1
l-l1
l-l1-l2
O+l1+l2
26
From CST(t) to CST(at)
Goal: Find 生長點(at) from 生長點(t).
生長點(at) = the canonical location of α(at)
生長點(t) = the canonical location of α(t)
27
From CST(t) to CST(at)
Algorithm
Step1: find 生長點(at) from 生長點(t).
Step2: insert the leaf for at at 生長點(at).
28
Step1: find 生長點(at) from 生長點(t).
l