《断头指标》PPT课件

《《断头指标》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、BidirectionalOnlineConstructionofAffixTreeB89209016張嘉真B89902103林虹佑B89902106高偉鈞1SourceMoritzG.Maaß.LinearBidirectionalOn-LineConstructionofAffixTrees.Algorithmica.OnlinepublicationMay28,20032OutlineIntroductiontoAffixTreeOnlineconstructionofSuffixTreeinreversedord

2、erOnlineconstructionofAffixTreeOnlinebidirectionalconstructionofAffixTree3Sigma+Tree字母樹arooted,directedtreewithedgelabelsfromsigma+.everynodeinThasatmostoneoutgoingedgewhoselabelstartswitha.Example:S=baabab4Path(n)路徑(n)w=path(n)wisthestringthatisconstructedbycon

3、catenatingalledgelabelsonthepathfromtheroottothenoden.Example:npath(n)=bbabacbbabac5CST&CPT(1)CompactSuffixTree(CST):字串(T)={u

4、uisasuffixoft}Example:S=baabbCompactSuffixTree(CST)abaababbbbbb6CST&CPT(2)CompactPrefixTree(CPT):字串(T)={u

5、uisaprefixoft}Example:S=baabbCo

6、mpactPrefixTree(CPT)bbaaaaaabbbb7AffixTree(1)Prefixesoftaresuffixesof反(t)PrefixTree(t)=SuffixTree(反(t))Example:T=baabb反(T)=bbaabbbaaaaaabbbbCompactPrefixTree(CPT)ofT8AffixTree(2)斷頭指標SuffixLinksExample:T=ababccbabcabccabcTheCSTfort=ababc9AffixTree(2)斷頭指標上的labelThe

7、substringthatisdiscardedExample:t=ababccbabcabccabcTheCSTfort=ababcabababc10AffixTree(3)鏡像樹ThetreethatisformedbythesuffixlinksofTinreversedorderExample:T=ababcTheCSTfort=ababcbacbabaThereversetreeoftheCSTfort=ababccbabcabccabcababcab11Thisisnottheprefixtree….t=ab

8、abcTheCSTfort=ababcbacbabaThereversetreeoftheCSTfortcbabcabccabcabababcabababacbabaTheCPTfort=ababc(TheCSTfort’=cbaba)12AffixTree(4)DefinitionofAffixTree字串(T)={u

9、uisasuffixoft}and字串(反(T))={u

10、uisasuffixof反(t)}ExamplecbabcabccabcCATfortfocusedonthesuffixstructuret=

11、ababcTheCATfocusedontheprefixstructureDualsuffixtreeabababacbaba13NestedSuffix/PrefixNestedsuffixt={__w______w}Nestedprefixt={w______w__}ww14NestedSuffix/Prefix(2)Longestnestedsuffixt={__aw______bw}生長點inUkkonen’salgorithm12345S=abaab6c…[1,-][2,-]1[1,1][2,-][4,-]1

12、15NestedSuffix/Prefix(3)短(t)shortestnon-nestedsuffixShortestLeaf16ConstructingAffixTree(1)Prefixesoftaresuffixesof反(t)PrefixTree(t)=SuffixTree(反(t))17Construc