后綴樹構(gòu)造方法講義

后綴樹講義1.基本定義后綴：一個長度為m的序列S=sss.....s，記S=ss.....s為S的第i個后綴，顯123miii+1m然S1=S。后綴樹：一個長度為m的序列S的后綴樹是一個有根定向樹，別且滿足下面條件它剛好有m個葉節(jié)點。除了根節(jié)點之外的每一個內(nèi)節(jié)點至少有兩個子節(jié)點，并且每條邊都對應S的一個非空子序列。任何從一個內(nèi)節(jié)點出發(fā)的兩條邊對應的子序列的第一個字符都不同。每一條從根節(jié)點出發(fā)到葉子節(jié)點的路徑對應序列S的一個后綴。第四個條件是后綴樹的主要特征。6圖1：序列xabxa$對應的后綴樹路徑的標簽：我們稱一個路徑對應的序列叫路徑的標簽。一個節(jié)點的標簽：從根節(jié)點到這個節(jié)點的路徑對應的序列。注：并不是所有的序列都對應有后綴樹，比如序列xabxa就沒有后綴樹因為后綴xa剛好是后綴xabxa的前綴，因此標簽為序列xa的路徑并不是葉節(jié)點，此時xabxa沒有后綴樹，為了解決這一問題，通常我們在序列末尾加上一個$字符（不同于序列中出現(xiàn)的任何字符）以解決這個問題，因為此時任何一個后綴都不可能是另外一個后綴的前綴。隱含后綴樹：序列S的隱含后綴樹指的是，序列S$的后綴樹去掉那些有$的邊上的$符號，然后將空白的邊去掉得到的樹。圖2：xabxa的隱含后綴樹。2.后綴樹的構(gòu)造后綴樹的構(gòu)造方法有很多種，其中Ukkonen’s算法是最容易理解的而且其時間和空間復雜度都是線性的，這里我們只講這種算法。該算法根據(jù)S的前綴sss.....s構(gòu)建一個隱含后綴樹「，當I=m的時候r就是S的123iim后綴樹，因此Ukkonen’s算法可以被分成m個階段，在第I+1個階段，根據(jù)「.構(gòu)建樹「工，而每一個階段又被分成I+1個擴展，其中的第j個擴張確認S[j,j+1...I+1],1<j<i+1,即S[1—i]序列的第j個后綴在樹中。算法過程如下：Ukkonen‘s后綴樹構(gòu)造算法構(gòu)建后綴樹r1I從1到m第I+1階段開始j從1至到I+1開始｛第j個擴展｝在現(xiàn)在的已經(jīng)構(gòu)建好的樹中找到從根節(jié)點出發(fā)的標簽為Sj..i],如果需要的話將S[I+1]加到這條路徑后面確認SU...I+1]在樹中。第j個擴展結(jié)束。第I+1個階段結(jié)束。后綴擴展規(guī)則令Sj..I]=p,p是S[1..i]的一個后綴，第j步擴展的主要任務是確保序列P,S[I+1]在樹中規(guī)則1路徑p是以一個葉子節(jié)點結(jié)束的，此時直接將S[I+1]加到葉子節(jié)點上面即可。規(guī)則2p后面沒有路徑以S[I+1]開始但是至少有一個路徑是p的延續(xù)。此時如果p在一個內(nèi)節(jié)點終止，則我們需要重新建一個葉子節(jié)點作為這個內(nèi)節(jié)點的子節(jié)點并且它對應的路徑標簽是S[I+1]。當p是在一條邊的中間的時候，此時除了建一個葉子節(jié)點之外還要建一個從根出發(fā)的標簽為p的內(nèi)節(jié)點。規(guī)則3有某個從p末端出發(fā)的路徑是以S[I+1]開始的，此時我們什么也不用做。圖3：axabxb的后綴樹。上面算法的時間復雜度分析:一般情況下下，我們要花。(|時)的時間才能找到路徑P，因此第I+1階段的第j個擴展消耗時間是O(I+1-j)因此「,H可以經(jīng)過O(i2)的時間從氣擴展得到，因此構(gòu)建[的時間復雜度是0(m3)。Ukknonen的算法是在這個簡單算法的基礎上，經(jīng)過改進實現(xiàn)線性時間的。后綴鏈接：第一個加速技巧后綴鏈接：令^a為任意一個字符串，其中x為任意一個字符，a為任意一個字符串(可以為空)，對一個路徑標簽為xa的內(nèi)節(jié)點v，如果有另外一個內(nèi)節(jié)點s(v)的路徑標簽是a，那么一個從v指向s(v)的指針被稱為后綴鏈接。命題1：如果一個新的路徑標簽xa為內(nèi)節(jié)點v在第I+1個階段的j個擴展中被加進樹中，那么要么路徑標簽為a的內(nèi)節(jié)點已經(jīng)在樹中存在，要么在第j+1個擴展中會出現(xiàn)。證明：內(nèi)節(jié)點的出現(xiàn)只可能在擴展j實現(xiàn)的是規(guī)則二的時候，也就是說，此時路徑xa后面有某個字符c而不是S[I+1]，因此在擴展j+1中肯定有一個路徑的標簽為a，但后面跟的是字符c。此時有兩種情況，一種是a后面只有c字符，另外一種情況是a后面跟著其它字符。第二種情況s(v)節(jié)點肯定已經(jīng)存在，第一種情況下，根據(jù)規(guī)則二，一個新的內(nèi)節(jié)點s(v)將會被創(chuàng)建。故定理得證。推論：在Ukknonen算法中任何一個剛被創(chuàng)建得節(jié)點v到下一個擴展為止都將有一個后綴鏈接從它出發(fā)。為將S[j..i]擴展到Sj..I+1],重復下面得做法，從后綴樹中路徑S[j-1..i]的末端出發(fā)，我們最多移動一個節(jié)點到樹的根節(jié)點或者是有后綴鏈接的內(nèi)節(jié)點。令T是那條邊的標簽，如果v不是根節(jié)點，沿著后綴鏈接到S(v):然后沿著邊的標簽Y到路徑S[j..i]的末尾，然后按照擴展規(guī)則完成由S[j..i]到S[j.I+1]的擴展。單步擴展算法(singleextensionalgorithm):SEA查找與S[j-1..i]對應的節(jié)點，或者是在該子串末端之上的那個節(jié)點v，要么節(jié)點有一個后綴鏈接，要么就是根節(jié)點，這就最多需要指針挪動一個位置。令y為v和S[j..i]的末端之間對應的路徑。如果v不是根節(jié)點，指針轉(zhuǎn)移到v的后綴鏈接S(v)上，然后沿著y對應的路徑。如果v是根節(jié)點，直接查找S[j..i]對應的路徑。根據(jù)擴展規(guī)則，確保S[j..i]S[I+1]在樹中。如果在擴展j-1中出現(xiàn)一個新的內(nèi)節(jié)點w，則根據(jù)定理必然有一個后綴鏈接從w指向S(W)o后綴鏈接的使用并沒有降低運算復雜度。要降低復雜度，需要下面的技巧。技巧1:跳邊技巧在第j+1個擴張中，沿著節(jié)點S(v)下一條標簽為Y的路徑，時間復雜度為Oy|.但是根據(jù)后綴樹的定義，一個節(jié)點出發(fā)的幾條路徑開始的字符不可能相同，因此y的第一個字符必須是那條與y對應的邊的第一個字符。令g'為這條邊上的字符個數(shù)，g=y|，如果g'<g，我們可以跳過這條邊，令g=g-g'，h=g'+1然后重復上面的過程，直到將y路徑完全遍歷為止。因此我們查找y的時間復雜度跟y的長度沒有關系，而只和從這條路徑上面的節(jié)點個數(shù)有關。深度：一個節(jié)點u的深度是從樹根出發(fā)到這個節(jié)點的路徑上面的所有節(jié)點的個數(shù)。命題2：如果(v,s(v))為一個后綴鏈接，則v的深度最多比S(v)的深度大1o證明：(略)，(根據(jù)后綴鏈接的定義)。定理：使用跳邊技巧，算法的每一個階段的時間復雜度都是O(m).證明：根據(jù)上面的算法實現(xiàn)過程，在單個擴展算法中，我們主要的操作就是從一個節(jié)點跳到另外一個節(jié)點，因此只要我們分析一下深度變化就可以了。單步擴展算法中向上最多跳一個節(jié)點，深度最多減少1，當沿著后綴鏈接跳的時候深度也是作多減一。因此在整個階段當前節(jié)點的深度變化最多為2m次，而沒有一個節(jié)點的深度可以超過m，故整個階段的時間復雜度為O(m)o推論：利用后綴鏈接，Ukkonen算法的時間復雜度為O(m2)。后綴樹的兩個重要特征：如果一個節(jié)點是一個葉子節(jié)點，那么它將一直是一個葉子節(jié)點。(沒有任何操作將一個葉子節(jié)點改為內(nèi)節(jié)點的)規(guī)則3是一個停止規(guī)則。(一旦規(guī)則三實施，沒有必要再查找下去)兩個技巧：我們可以在常數(shù)時間內(nèi)完成對葉子節(jié)點的擴張，用一個全局變量指向所有葉子節(jié)點的末尾。一旦規(guī)則三被使用，則這個階段就結(jié)束了。單階段算法(singlephasealg