文档介绍：Bidirectional Online Construction of Affix Tree
B89209016 張嘉真
B89902103 林虹佑
B89902106 高偉鈞
1
精选课件
Source
Moritz for t = ababc
b
a
c
b
a
b
a
The reverse tree of the CST for t
c
b
a
b
c
a
b
c
c
a
b
c
a
b
a
b
a
b
c
a
b
a
b
a
b
a
c
b
a
b
a
The CPT for t = ababc
(The CST for t’=cbaba)
12
精选课件
Affix Tree(4)
Definition of Affix Tree
字串(T) = {u | u is a suffix of t} and
字串(反(T))={u | u is a suffix of 反(t)}
Example
c
b
a
b
c
a
b
c
c
a
b
c
CAT for t focused on the suffix structure
t = a b a b c
The CAT focused on the prefix structure
Dual suffix tree
a
b
a
b
a
b
a
c
b
a
b
a
13
精选课件
Nested Suffix / Prefix
Nested suffix
t = { __w______w }
Nested prefix
t = { w______w__ }
w
w
14
精选课件
Nested Suffix / Prefix(2)
Longest nested suffix
t = { __aw______bw }
生長點 in Ukkonen’s algorithm
1 2 3 4 5
S = a b a a b
6
c …
[1,-]
[2,-]
1
[1,1]
[2,-]
[4,-]
1
15
精选课件
Nested Suffix / Prefix(3)
短(t) shortest non-nested suffix
Shortest Leaf
16
精选课件
Constructing Affix Tree(1)
Prefixes of t are suffixes of 反(t)
Prefix Tree(t) = Suffix Tree(反(t))
17
精选课件
Constructing Affix Tree(2)
Ukkonen’s algorithm CST(T) CST(Ta)
Construct CST(T) CST(aT)
CAT(T)=CST(T)+CPT(T)
18
精选课件
Constructing Affix Tree(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)