每個分支節點的第一個字段是到以其為根的subtrie中元素(譯注:應該是指子節點)的引用.我們可以用被引用的元素的首字符的索引代替元素引用.圖3展示了替換后的樹.我們將會用這種修改后的形式作為后綴樹的表示.
Figure 3 Suffix tree for peeper
如果后綴樹的每條邊用從分支節點到其子節點的字符(串)標注,可以更容易描述后綴樹的查找和構建算法.標簽的第一個字符用來確定要移到哪一個子節點,剩余的字符表示要跳過的字符(串).圖4展示的就是圖3用這種方式畫出后得到的后綴樹.
Figure 4 A more humane drawing of a suffix tree
在后綴樹的更直觀的畫法中,從任意根節點到信息節點的路徑上所有邊的標簽拼接在一起得到的就是信息節點表示的后綴.When the digit number for the root is not 1, the humane drawing of a suffix tree includes a head node with an edge to the former root. This edge is labeled with the digits that are skipped over.
后綴樹的某個節點表示的字符串是由根節點到此節點的路徑上的標簽拼出來的.圖4中的節點A表示空串epsilon,節點C表示字符串pe,節點F表示字符串eper.
由于后綴樹的關鍵字長度不同,我們必須保證沒有一個關鍵字是另一個的真前綴(proper prefix).當字符串S的最后一個字符在S中只出現一次,就不會出現S的其中一個后綴是另一個后綴的真前綴的情況.在字符串peeper中,最后的字符是r,并且只出現了一次.因此peeper的后綴中就不會出現真前綴的情況.字符串data的最后字符是a,并且出現了兩次.因此,data有兩個以a開始的后綴,ata和a.后綴a是ata的真前綴.
當字符串S的最后字符在S中出現多于一次,就必須在S的所有后綴后面附加一個新的字符(比如說#),這樣任何一個后綴都不會是其他后綴的前綴.還有一種方法是,我們可以在S后面附加新的字符#,得到新的串$#,然后創建$#的后綴樹.這樣做之后得到的后綴樹比直接在S的每個后綴后面附加#會多一個后綴#.
讓我們查找那個子串吧
但是，首先要說明幾個術語
用n=|S|表示要創建后綴樹的字符串的長度.我們從左到右依次給S的字符編號,最左邊的編號為1.S[i]表示S的第i個字符,suffix(i)表示從字符i開始的后綴S[i]...S[n],1<=i<=n.
關于查找
當在S中查找模式P時,用到的一個基本的觀察(observation)是P在S中出現當且僅當P是S的某個后綴的前綴.
假設P = P[1]...P[k] = S[i]...S[i+k-1].則P是suffix(i)的前綴.既然suffix(i)在我們的壓縮trie樹中(也就是后綴樹),我們可以利用在壓縮trie樹中查找關鍵字前綴的策略來查找P.
讓我們在字符串S=peeper中查找模式P=per.假設我們已經為S創建好了后綴樹(圖4).查找從根結點A開始.因為P[1]=p,我們順著標簽以p開始的邊.當順著此邊繼續時,我們對邊標簽的剩余字符和P的后續字符做比較.由于標簽的剩余字符跟P的字符相符,我們到達分支C.在到達C的過程中,我們已經使用了P的前兩個字符.第三個字符是r,因此我們從節點C順著以r開始的邊繼續.由于這條邊沒有其他字符,因此不需要其他比較,到達信息節點I.這時,P中的字符已經用完了,我們就斷定P在S中.由于已經到達信息節點I,我們斷定P實際上是S的后綴.在實際的后綴樹表示中(而不是如圖4這種人性化的表示),信息節點I包含索引4,這告訴我們模式P=per由S=peeper的第4個字符開始(也就是說,P=suffix(4)).更進一步,我們可以得到P在S中只出現一次;如果一個模式在字符串中出現多次,查找會在分支節點中止,而不是信息節點.(譯注:例如查找pe,查找在節點C中止,說明它在S中出現了兩次--C有兩個葉子節點)
現在我們來查找模式P=eeee.還是從根結點開始.由于P的第一個字符是e,我們沿著以e開始的邊到達B.下一個字符還是e,因此我們從B開始沿著以e開始的邊繼續.在沿著這條邊向下的過程中,我們需要比較邊標簽的剩余字符per和P的剩余字符ee.比較第一對字符(p,e)時無法匹配,因此我們斷定P不在S中.
假設我們查找模式P=p.從根開始,沿著以p開始的邊往下.在向下的過程中,我們比較邊的剩余字符(只有字符e)和模式的剩余字符.由于已經到P的結尾,我們斷定P是以節點C為根的subtrie的所有關鍵字的前綴.可以通過遍歷以C為根的subtrie、訪問subtrie的所有信息節點找到P出現的所有位置。如果只需要P出現的一個位置，可以利用存儲在節點C的第一部分的索引。當沿著到節點X的邊查找時模式結束，我們就說已到達節點X；查找在節點X結束。
當查找模式P=rope，利用P的第一個字符r到達信息節點D。由于模式還沒有結束，我們必須根據D的字符檢查P的剩余字符。檢查顯示P不是D的關鍵字的前綴，因此P不在S=peeper中。
我們要做的最后一個查找是對模式P=pepe。從圖4的根結點開始，我們沿著以p開始的邊到達節點C。下一個未檢查的字符是p。因此，從C開始，我們希望沿著以p開始的邊繼續。由于沒有滿足這個條件的邊，我們斷定pepe不在peeper中。
Other Nifty Things You Can Do with a Suffix Tree
一旦為字符串S創建好了后綴樹，我們就可以在O(|P|)時間內判斷S是否包含P。這意味著如果為莎士比亞的戲劇“羅密歐與朱麗葉”的內容創建了后綴樹，我們就可以非常快的判斷文章中是否存在短語wherefore art thou。事實上，只需話費比較18個字符的時間（模式的長度）。查找時間跟文章的長度無關。
其他可以快速完成的有趣事情：
1.查找模式P的所有出現。這是通過對P查找后綴樹實現。如果P至少出現一次，查找會在信息節點或者分支節點中止。當中止于信息節點時，P只出現一次。如果中止于分支節點X，模式出現的所有地方可以通過訪問以X為根的subtrie的信息節點來得到。如果我們按照下面的方式，這個訪問操作可以在O(n)（n是模式出現的次數）時間內完成。
(a)
將所有的信息節點按照節點所表示的后綴的字典序鏈起來（這也是從左到右掃描信息節點時遇到這些節點的順序）。圖4的信息節點會按照E,F,G,H,I,D的順序鏈接起來。
(b)
在每個分支節點內，保存以此節點為根的subtrie的第一個和最后一個信息節點的引用。圖4中節點A,B和C分別保存序對(E,D),(E,G)和(H,I)。我們用序對(firstInformationNode, lastInformationNode)周游以firstInformationNode開始、以lastInformationNode結束的鏈。這個周游會得到模式P出現的所有位置。注意，當我們在分支節點中保存序對(firstInformationNode, lastInformationNode)時，就不需要再保存到subtrie中的信息節點的引用（也就是字段element）。
2.查找包含模式P的所有字符串。假設我們有一些字符串S1,S2,... Sk，我們想得到所有包含P的字符串。例如，基因庫中包含數以萬計的字符串，當一個研究員提交一個查詢字符串，我們就要報告所有包含此模式的字符串。為了有效的執行這類查詢，就需要創建一個包含字符串S1$S2$...$Sk#的所有后綴的壓縮trie樹（也稱為多字符串后綴樹），這里的$,#是兩個不在字符串S1, S2, ..., Sk中出現的不同字符。在后綴樹的每個（分支）結點N中，保存所有的字符串Si的鏈表，其中Si是以N為根的subtrie中所有的信息節點表示的字符串的開始點位于其中的字符串（譯注：真拗口啊，這兒的意思就是對某個信息節點L，如果L表示的字符串從Si的某個位置開始，那就將Si的引用放到L的父輩節點的鏈表中）。
3.查找S中出現次數至少為m>1次的子串。這個查詢可以按照下面的方式在O(|S|)時間內完成：
(a)周游后綴樹，對每個分支節點X，保存從根節點到X節點的字符串的長度l和以X為根的subtrie中信息節點的數目m。
(b)周游后綴樹，訪問信息節點數>=m的分支節點。l最大的分支節點表示的就是出現次數>=m的最長子串。
注意步驟(a)只需要執行一次。完成后，我們可以對需要的任意m執行步驟(b)。另外還要注意，當m=2是，不需要確定subtrie中信息節點的數目。在后綴樹中，每個分支節點之后有兩個信息節點。
4.查找字符串S和T的最長公共子串。這可以按照下面的方式在O(|S|+|T|)時間內完成：
(a)為S和T創建多字符串后綴樹（也就是S$T#的后綴樹）
(b)周游后綴樹，查找表示的字符串最長，并且以其為根的subtrie的信息節點表示的字符串中，至少有一個從S開始，另一個從T開始的字符串。
注意，有個相關的查找S和T的最長公共子序列的問題用動態規劃算法在O(|S|*|T|)時間內完成。
如何創建你自己的后綴樹
三個觀察(observation)
為了更有效的創建后綴樹，我們為每個分支節點添加字段longestProperSuffix。表示非空字符串Y的分支節點的longestProperSuffix字段指向表示Y的最長真后綴的分支節點（Y的最長真后綴通過去掉Y的首字符得到）。根結點的longestProperSuffix未使用。
圖5表示的是給圖4加上最長真后綴指針后得到（經常將最長真后綴指針簡稱為后綴指針）。后綴指針用紅色箭頭表示。節點C表示字符串pe。pe的最長后綴e由節點B表示。因此C的后綴指針指向B。e的最長后綴是空串。由于根結點A表示空串，因此B的后綴指針指向A。
Figure 5 Suffix tree of Figure 4 augmented with suffix pointers
觀察1 如果S的后綴樹有一個表示字符串Y的分支節點，那么后綴樹中也有一個表示Y的最長后綴Z的分支節點。
證明 設P為表示Y的分支節點。由于P是分支節點，至少有兩個不同的字符x和y，使得S中有兩個分別以Yx和Yy開始的后綴。因此，S有兩個分別以Zx和Zy開始的后綴。因此，S的后綴樹中必然有一個對應Z的分支節點。
觀察2 如果S的后綴樹有一個表示Y的分支節點，那么樹中對Y的每個后綴都有一個對應的分支節點。
證明 由觀察1即可得到。
注意圖5中有一個表示pe的分支節點。因此，樹中一定有表示e和epsilon的分支節點。
在描述后綴樹的創建算法時，有兩個概念很有用：last branch node和last branch index。后綴suffix(i)的last branch node是表示suffix(i)的信息節點的父節點。在圖5中，suffix(1)...suffix(6)的last branch node分別是C,B,B,C,B和A。對任意后綴suffix(i)，其last branch index lastBranchIndex(i)是在suffix(i)的last branch node中，產生分支的字符的索引。在圖5中，lastBranchIndex(1)＝3,因為：suffix(1)=peeper，suffix(1)由信息節點H表示，H的父節點是C；C的分支是在suffix(1)的第三個字符產生的；suffix(1)的第三個字符是S[3]。可以驗證一下，lastBranIndex[1:6] = [3,3,4,6,6,6]。
觀察3 在S的后綴樹中， lastBranchIndex(i) <= lastBranchIndex(i+1), 1 <= i < n。
證明作為練習。
Get Out That Hammer and Saw, and Start Building
為了創建你自己的后綴樹，你必須由你自己的字符串開始。我們使用R = ababbabbaabbabb來闡述后綴樹的構建過程。由于R的最后字符b出現了不止一次，我們在R后面附加字符#，為新的字符串S=R#創建后綴樹。
創建策略
后綴樹的創建算法從表示空串的根結點開始。根結點是一個分支節點。創建后綴樹過程的任何時候，都有一個分支節點被指定位活動節點(active node)。這是插入下一個后綴的起始節點。用activeLength表示根結點對應的字符串的長度。開始時，根節點是活動節點，activeLength=0。圖6展示了開始時的狀態，綠色的節點是活動節點。
Figure 6 Initial configuration for suffix tree construction
隨著處理的進行，我們會不斷往樹中添加分支節點和信息節點。新添加的分支節點用品紅色表示，新添加的信息節點用青色表示。后綴指針為紅色。
后綴按照suffix(1), suffix(2), ..., suffix(n)的順序依次插入到樹中。后綴以這種順序插入是通過從左到右掃描字符串S的方氏完成。用tree(i)表示插入后綴suffix(1), ..., suffix(i)之后形成的樹，lastBranchIndex(j, i)表示tree(i)中后綴suffix(j)的last branch index。minDistance表示從活動節點到即將插入的后綴的last branch index的距離的下界（譯注：感覺這個東西在實現的時候沒啥意義）。開始時，minDistance = 0并且lastBranchIndex(1,1) = 1。當插入suffix(i)時，滿足條件lastBranchIndex(i,i) >= i + activeLength + minDistance。
為了向tree(i)中插入suffix(i+1)，我們必須遵循如下步驟：
1.確定lastBranchIndex(i+1, i+1)。為了完成這點，我們從當前活動節點開始。新后綴的開始的activeLength個字符（也就是字符S[i+1], S[i+2], ..., S[i + activeLength]）已知是跟當前活動節點表示的字符串相匹配的。因此，為了確定lastBranchIndex(i+1,i+1)，需要檢測新后綴的activeLength + 1, activeLength + 2, ...字符。這些字符用于確定tree(i)中進一步處理時要經過的路徑，此路徑始于活動節點，當lastBranchIndex(i+1,i+1)確定時中止。根據已知的lastBranchIndex(i+1,i+1) >= i + 1 + activeLength + minDistance，這個過程可以簡化，從而得到效率提升。
2.如果tree(i)中沒有表示字符串S[i]...S[lastBranchIndex(i+1,i+1)-1]的節點X，則創建一個。
3.為suffix(i+1)添加一個信息節點。這個信息節點是X的孩子，從X到信息節點的邊上的標簽是S[lastBranchIndex(i+1, i+1)]...S[n]。
回到例子
我們從向圖6中的樹tree(0)插入suffix(1)開始。根結點是活動節點，activeLength = minDistance = 0。suffix(1)的第一個字符是S[1]=a。從tree(0)的活動節點開始沒有以a開始的邊（事實上，此時活動節點沒有任何邊）。因此，lastBranchIndex(1,1) = 1。我們創建一個新的信息節點和一條邊，邊的標簽是整個字符串。圖7展示了結果tree(1)。根結點依然是活動節點，activeLength和minDistance沒有變化。
Figure 7 After the insertion of the suffix ababbabbaabbabb#
在我們的畫法中，信息節點的入邊的標簽標記為i+，i表示標簽在S中的開始位置，+表示標簽一直到字符串的結尾。因此，在圖7中，1+表示字符串S[1]...S[n]。圖7也展示了字符串S。新插入的后綴用青色表示。
為了插入后綴suffix(2)，我們再次從根結點開始檢查后綴的activeLength + 1 = 1, activeLength + 2 = 2, ...,字符。因為suffix(2)的第一個字符是S[2]=b，活動節點沒有以S[2]=b開始的邊，所以lastBranchIndex(2,2) = 2。因此我們創建新的信息節點和標記為2+的邊。結果如圖8所示。根結點依然是活動節點，activeLength和minDistance依舊沒有變化。
Figure 8 After the insertion of the suffix babbabbaabbabb#
注意圖8是關于suffix(1)和suffix(2)的壓縮trie樹tree(2)。
下一個后綴suffix(3)開始于S[3]=a。由于tree(2)的活動節點有一個以a開始的邊，所以lastBranchIndex(3,3) > 3。為了確定lastBranchIndex(3,3)，必需要查看suffix(3)的更過字符。尤其是，我們需要查看盡可能多的字符，以便區分suffix(1)和suffix(3)。首先比較后綴的第二個字符S[4]=b和邊1+的第二個字符S[2]=b。由于S[4]=S[2]，必須做進一步的比較。下一步比較S[5]和S[3]。由于這兩個字符不同，我們可以確定lastBranchIndex(3,3)是5。這時，我們需要更新minDistance為2.注意，因為lastBranchIndex(3,3) = 5 = 3 + activeLength + minDistance，這是minDistance的最大可能值。
為了插入suffix(3)，我們將tree(2)的邊1+一分為二。第一條邊的標簽是1,2;第一條邊的標簽是3+。這兩個邊之間插入新的分支節點。另外，還要為新插入的后綴添加信息節點。結果如圖9所示。邊標簽1,2顯示為字符S[1]S[2] = ab。
Figure 9 After the insertion of the suffix abbabbaabbabb#
tree(3)還沒完成，因為還沒有確定新加的分支節點的后綴指針。這個分支節點的最長后綴是b，但是對應b的分支節點不存在。別驚慌，下一個要創建的分支節點就是對應b的節點。
下一個要插入的后綴是suffix(4)。這是剛插入的suffix(3)的最長后綴。新后綴的插入過程由根據當前活動節點的后綴指針確定新的活動節點開始。由于根結點沒有后綴指針，活動節點沒有變化。因此activeLength也沒有變化。但是，我們必須更新minDistance以滿足lastBranchIndex(4,4) >= 4 + activeLength + minDistance。顯然，對于所有的i<= lastBranchIndex(i+1,i+1)。因此，lastBranchIndex(i+1,i+1) >= lastBranchIndex(i,i) >= i + activeLength + minDistance。為了保證lastBranchIndex(i+1,i+1) >= i + 1 + activeLength + minDistance，我們必須將minDistance減小1.
因為minDistance = 1，我們從活動節點開始，沿著S[4]S[5]...指定的路徑記錄。我們不需要比較開始的minDistance個字符，因為在minDistance+1之前的字符都已經保證是匹配的了。由于活動節點以S[4]=b開始的邊的長度大于1,我們比較S[5]和邊的第二個字符S[3]。因為這兩個字符不同，這條邊也要一分為二。第一條邊的標簽為2,2=b；第二條棉的標簽為3+。在兩條邊之間添加新的分支節點F，還要為新插入的后綴創建信息節點G。G跟F之間通過標簽為5+的邊連接。結果如圖所示。
Figure 10 After the insertion of the suffix bbabbaabbabb#
現在我們要為插入后綴suffix(3)時創建的分支節點D設置后綴指針。這個后綴指針就是新創建的分支節點F。
節點F表示的字符串b的最長后綴是空串。因此F的后綴指針指向根結點。圖11是添加了后綴指針的結果。
Figure 11 Trie of Figure 10 with suffix pointers added
下一個要插入的是suffix(5)。由于suffix(5)是剛插入的后綴suffix(4)的最長后綴，我們從活動節點的后綴指針開始。但是當前作為活動節點的根結點沒有后綴指針。因此，活動節點不變。為了保持lastBranchIndex, activeLength, minDistance以及將插入的后綴的索引(5)之間的關系，需要將minDistance減少1.因此，minDistance變為0.
因為activeLength=0，我們需要從suffix(5)的首字符S[5]開始檢查。活動節點有一條以S[5]=b開始的邊。我們沿著這條邊比較后綴字符和標簽字符。由于所有的字符都匹配，我們到達節點F。現在F成為活動節點（在檢查后綴字符的過程中，遇到的分支節點都成為新的活動節點），activeLength=1。我們從當前活動節點的某條邊開始繼續比較。由于下一個要比較的后綴字符是S[6]=a，我們使用以a開始的邊（如果這樣的邊不存在，新后綴的lastBranchIndex是activeLength+1）。這條邊的標簽是3+。當比較到新后綴的字符S[10]=a和邊的字符S[7]=b時，比較結束。因此，lastBranchIndex(5,5) = 10. minDistance設置為允許的最大值，也就是lastBranchIndex(5,5) - (index of suffix to be inserted) - activeLength = 10 - 5 - 1 = 4.。
為了插入suffix(5)，我們將節點F和C之間的邊分裂為二。分裂出現在邊(F,C)的splitDigit=5的字符位置。
Figure 12 After the insertion of the suffix babbaabbabb#
Figure 13 After the insertion of the suffix abbaabbabb#
Figure 14 After the insertion of the suffix bbaabbabb#
Figure 15 After the insertion of the suffix baabbabb#
Figure 16 After the insertion of the suffix aabbabb#
Figure 17 After the insertion of the suffix abbabb#
Figure 18 After the insertion of the suffix bbabb#
Figure 19 After the insertion of the suffix babb#
Figure 20 After the insertion of the suffix abb#
Figure 21 After the insertion of the suffix bb#
復雜度分析用r表示字符串S的字符集的大小，n表示S的長度（也就是后綴的數目）。為了插入suffix(i)，我們(a)沿著活動節點的后綴指針（除非活動節點是根結點）。(b)在已創建的后綴樹中向下移動，直到經過了minDistance個字符。(c)然后依次比較后綴和邊的字符，直到確定了lastBranchIndex(i,i)為止。(d)最后插入新的信息節點和可能的分支節點。(a)部分消耗的總的時間是O(n)（一共有n此插入）(b)
部分中，在后綴樹中往下移動時，不需要做比較。每次移動到下級分支節點需要O(1)時間。另外，每次移動都會使minDistance減少1.由于開始時
minDistance為0,并且永遠不會小于0,(b)消耗的時間是O(n + n次插入操作中minDistance增加的總數). (c)
部分中，確定lastBranchIndex(i,i) 跟 i + activeLength +
minDistance是否相等需要的時間是O(1)。這只有在minDistance = 0或者位于suffix(i)的activeLength
+ minDistance + 1位置的字符x跟活動節點的合適的邊的minDistance +
1位置的字符不同的時候才滿足。當lastBranchIndex(i,i) != i + activeLength +
minDistance時，lastBranchIndex(i,i) > i + activeLength +
minDistance，lastBranchIndex(i,i)的值通過對后綴字符和邊的字符之間做一系列的比較來確定。每進行一次這種比
較，minDistance加1.本算法中，只有在這種情景下，minDistance才會增加。由于minDistance的每次遞增都是S的新的位置
（也就是此位置開始的字符還未比較過的位置）的字符和邊的字符相等的情形的結果，因此在n次插入中，minDistance增加的總數是O(n)。每次插入時，(d)消耗的時間是O(r)，因為我們需要初始化要創建的分支節點的O(r)個字段。因此步驟(d)消耗的總的時間是O(nr)。因此，創建后綴樹消耗的總的時間是O(nr)。如果假定字符集的大小r是常數，算法的復雜度就是O(n)。只有在字符集的大小r很小的情況下，才推薦每個分支節點有r個指向子節點的字段。當字符集很大的時候（可能會跟n一樣大，這時上述算法的復雜度是O(n^2)），使用哈希表能夠得到O(n)復雜度的算法。空間復雜度有O(nr)變為O(n)。這里有一個分治算法實現的后綴樹，時間和空間復雜度都是O(n)（即使字符集的大小是O(n)）。
References and Selected Readings
-
- Department of Energy's Web site for the human genomics project
- Biocomputing Hypertext Coursebook.
Linear
time algorithms to search for a single pattern in a given string can be
found in most algorithm's texts. See, for example, the texts:
- Computer Algorithms, by E. Horowitz, S. Sahni, and S. Rajasekeran, Computer Science Press, New York, 1998.
- Introduction to Algorithms, by T. Cormen, C. Leiserson, and R. Rivest, McGraw-Hill Book Company, New York, 1992.
For more on suffix tree construction, see the papers:
- ``A space economical suffix tree construction algorithm,'' by E. McCreight, Journal of the ACM, 23, 2, 1976, 262-272.
- ``On-line construction of suffix trees,'' by E. Ukkonen, Algorithmica, 14, 3, 1995, 249-260.
- Fast string searching with suffix trees,'' by M. Nelson, Dr. Dobb's Journal, August 1996.
- Optimal suffix tree construction with large alphabets, by M. Farach, IEEE Symposium on the Foundations of Computer Science, 1997.