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

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