《断头指标》PPT课件.ppt

Bidirectional Online Construction of Affix Tree
B89209016 張嘉真
B89902103 林虹佑
B89902106 高偉鈞
1
精选课件ppt
Source
Moritz G. Maaß. Linear Bidirectional On-Line Construction of Affix Trees. Algorithmica.
Online publication May 28, 2003
2
精选课件ppt
Outline
Introduction to Affix Tree
Online construction of Suffix Tree in reversed order
Online construction of Affix Tree
Online bidirectional construction of Affix Tree
3
精选课件ppt
Sigma+ Tree
字母樹
a rooted, directed tree with edge labels from sigma+.
every node in T has at most one outgoing edge whose label starts with a.
Example:
S = b a a b
a
b
4
精选课件ppt
Path(n)
路徑(n)  w = path(n)
w is the string that is constructed by concatenating all edge labels on the path from the root to the node n.
Example:
n
path(n) = b b a b a c
b
b
a
b
a
c
5
精选课件ppt
CST & CPT (1)
Compact Suffix Tree (CST):
字串(T)={u|u is a suffix of t}
Example:
S = b a a b b
Compact Suffix Tree (CST)
a
b
a
a
b
a
b
b
b
b
b
b
6
精选课件ppt
CST & CPT (2)
Compact Prefix Tree (CPT):
字串(T)={u|u is a prefix of t}
Example:
S = b a a b b
Compact Prefix Tree (CPT)
b
b
a
a
a
a
a
a
b
b
b
b
7
精选课件ppt
Affix Tree(1)
Prefixes of t are suffixes of 反(t)
Prefix Tree(t) = Suffix Tree(反(t))
Example:
T = b a a b b 反(T) = b b a a b
b
b
a
a
a
a
a
a
b
b
b
b
Compact Prefix Tree (CPT) of T
8
精选课件ppt
Affix Tree(2)
斷頭指標 Suffix Links
Example:
T = a b a b c
c
b
a
b
c
a
b
c
c
a
b
c
The CST for t = ababc
9
精选课件ppt
Affix Tree(2)
斷頭指標上的label
The substring that is discarded
Example:
t = a b a b c
c
b
a
b
c
a
b
c
c
a
b
c
The CST for t = ababc
a
b
a
b
a
b
c
10
精选课件ppt