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

1、最近在學(xué)習(xí)后綴樹的構(gòu)造，在網(wǎng)上找了好久發(fā)覺國內(nèi)詳解它的構(gòu)造的文章勝少，在 苦苦尋覓了許久，終于發(fā)現(xiàn)了一個網(wǎng)友翻譯的一篇文章，很好，于是我轉(zhuǎn)帖出來，希望能有 更多的人受益，也希望國內(nèi)多一些英文高手多翻譯一些國外的技術(shù)文章，好讓我們這些英文 很爛的人受益，呵呵！ 后綴樹Fast String Searching With Suffix Trees原著Mark Nelson. Fast string searching with suffix trees. 1996.構(gòu)造法E. Ukkonen. On-line construction of suffix trees. 1995.翻譯3xian /

2、 三鮮 in GDUT三鮮序原來是打算翻譯SartajSahni的Suffix tree,并專注地進(jìn)行了一周，連復(fù)習(xí)備考的時間 也不惜占去.我希望給國產(chǎn)的同好者提供更通俗易懂的資料，在翻譯的同時對原文進(jìn)行了 刪改，并加入了許多自己的心得.然而后來發(fā)現(xiàn)了 Mark Nelson的這篇文章，相比之下更有 親和力，于是老實地盡棄前功來翻譯這篇.更重要一個原因是，Mark Nelson介紹的是 Ukkonen的構(gòu)造法O(n),它比SartajSahni的構(gòu)造法O(nr), r為字母表大小在時間上更有優(yōu) 勢.但我們不能說SartajSahni的算法慢，因為r往往會很小，因此實際效率也接近線性，兩 種構(gòu)造

3、法在思想上均有可取之處.本文偏重于闡述后綴樹的構(gòu)造過程，而并沒有直接介紹后綴樹除了匹配以外還能做什 么.其實后綴樹是一種功能非常強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)，你可以去搜索引擎了解一下它還有多少 功能，當(dāng)然我最希望的是你在閱讀本文之后已經(jīng)足以體會后綴樹的妙處，日后遇到諸多問 題的時候都能隨心隨意地用上.最后嘮叨一句.我所見過的各種介紹后綴樹的論文都難免使初學(xué)者陷入混亂，本文估 計也好不到哪里去.這在一定程度上說明了后綴樹的原理是不太淺顯的，理解它需要在整 體上把握，建議希望讀者先不要糾結(jié)于細(xì)節(jié)，思路不清則反復(fù)閱讀.問題的來源字符串匹配問題是程序員經(jīng)常要面對的問題.字符串匹配算法的改進(jìn)可以使許多工程 受益良多，

4、比如數(shù)據(jù)壓縮和DNA排列.這篇文章討論的是一種相對鮮為人知的數(shù)據(jù)結(jié)構(gòu)- 后綴樹，并介紹它是如何通過自身的特性去解決一些復(fù)雜的匹配問題.你可以把自己想象成一名工作于DNA排列工程的程序員.那些基因研究者們天天忙著 分切病毒的基因材料，制造出一段一段的核苷酸序列.他們把這些序列發(fā)到你的服務(wù)器里， 指望你在基因數(shù)據(jù)庫中定位.要知道，你的數(shù)據(jù)庫里有數(shù)百種病毒的數(shù)據(jù)，而一個特定的病 毒可以有成千上萬的堿基.你的程序必須像C/S工程那樣實時向博士們反饋信息，這需要- 個很好的方案.很明顯，在這個問題上采取暴力算法是極其低效的.這種方法需要你在基因數(shù)據(jù)庫里 對比每一個核苷酸，測試一個較長的基因段基本會把你的

5、C/S系統(tǒng)變成一臺古老的批處理 機(jī).直覺上的解決方法由于基因數(shù)據(jù)庫一般是不變的，通過預(yù)處理來把搜索簡化或許是個好主意.一種預(yù)處 理的方法是建立一棵Trie.我們通過Trie引申出一種東西叫作后綴Trie.(后綴Trie離后綴 樹僅一步之遙.)首先,Trie是一種n叉樹,n為字母表大小，每個節(jié)點表示從根節(jié)點到此節(jié)點 所經(jīng)過的所有字符組成的字符串.而后綴Trie的“后綴”說明這棵Trie包含了所給字段的所 有后綴(也許正是一個病毒基因).圖1BANANAS的后綴Trie圖1展示了文本BANANAS的后綴Trie.關(guān)于這棵Trie有兩個地方需要注意.第一，從 根節(jié)點開始，BANANAS的每一個后綴都

6、插入到Trie中，包括BANANAS, ANANAS, NANAS, ANAS, NAS, AS, S.第二，鑒于這種結(jié)構(gòu)，你可以通過從根節(jié)點往下匹配的方式 搜索到單詞的任何一個子串.這里所說的第二點正是我們認(rèn)為后綴Trie優(yōu)秀的原因.如果你輸入一個長度為N的文 本并想在其中搜索一個長度為M的串，傳統(tǒng)的暴力匹配需要進(jìn)行N*M次字符對比，而一些 改進(jìn)過的匹配技術(shù)，比如像Boyer-Moore算法，可以在O(N+M)的時間開銷內(nèi)解決問題，平 均效率更是令人滿意.然而，后綴Trie亮出了 O(M)的牌子，徹底鄙視了其他算法的成績，后 綴Trie對比的次數(shù)僅僅相當(dāng)于被搜索串的長度！這確實是可圈可點的威

7、力，這意味著你能通過僅僅7次對比便在莎士比亞所有作品中 找出BANANAS.但有一點我們可不能忘了，構(gòu)造后綴Trie也是需要時間的.后綴Trie之所以沒有家喻戶曉正是因為構(gòu)造它需要O(n2)的時間和空間.平方級的開 銷使它在最需要它的領(lǐng)域-長串搜索中被拒之門外.橫空出世直到1976年，Edward McCreigh發(fā)表了一篇論文，咱們的后綴樹問世了.后綴Trie的 困境被徹底打破.后綴樹跟后綴Trie有著一樣的布局，但它把只有一個兒子的節(jié)點給剔除了.這個過程 被稱為路徑壓縮，這意味著樹上的某些邊將表示一個序列而不是單獨的字符.圖2BANANAS的后綴樹圖2是由圖1的后綴Trie轉(zhuǎn)化而來的后綴樹

8、.你會發(fā)現(xiàn)這樹基本還是那個形狀，只是 節(jié)點變少了.在剔除了只有一個兒子的節(jié)點之后，總節(jié)點數(shù)由23降為11.經(jīng)過證明，在最 壞情況下，后綴樹的節(jié)點數(shù)也不會超過2N (N為文本的長度).這使構(gòu)造后綴樹的線性時空 開銷成為可能.然而,McCreight最初的構(gòu)造法是有些缺陷的，原則上它要按逆序構(gòu)造，也就是說字符 要從末端開始插入.如此一來，便不能作為在線算法，它變得更加難以應(yīng)用于實際問題，如 數(shù)據(jù)壓縮.20年后，來自赫爾辛基理工大學(xué)的EskoUkkonen把原算法作了一些改動，把它變成了 從左往右.本文接下來的所有描述和代碼都是基于EskoUkkonen的成果.對于所給的文本T, EskoUkkon

9、en的算法是由一棵空樹開始，逐步構(gòu)造T的每個前綴的 后綴樹.比如我們構(gòu)造BANANAS的后綴樹，先由B開始，接著是BA,然后BAN,.不 斷更新直到構(gòu)造出BANANAS的后綴樹.圖3逐步構(gòu)造后綴樹初窺門徑加入一個新的前綴需要訪問樹中已有的后綴.我們從最長的一個后綴開始（圖3中的 BAN）, 一直訪問到最短的后綴（空后綴）.每個后綴會在以下三種節(jié)點的其中一種結(jié)束.l 一個葉節(jié)點.這個是常識了，圖4中標(biāo)號為1,2, 4, 5的就是葉節(jié)點.l 一個顯式節(jié)點.圖4中標(biāo)號為0, 3的是顯式節(jié)點，它表示該節(jié)點之后至少有兩條 邊.l一個隱式節(jié)點.圖4中，前綴BO, BOO,或者非前綴OO,它們都在某條表示序

10、列的邊上結(jié)束，這些位置就叫作隱式節(jié)點.它表示后綴Trie中存在的由于路徑壓縮而剔除的 節(jié)點.在后綴樹的構(gòu)造過程中，有時要把一些隱式節(jié)點轉(zhuǎn)化為顯式節(jié)點.圖4加入BOOK之后的BOOKKEEPER（也就是BOOK的后綴樹）如圖4,在加入BOOK之后，樹中有5個后綴（包括空后綴）.那么要構(gòu)造下一個前綴 BOOKK的后綴樹的話，只需要訪問樹中已存在的每一個后綴，然后在它們的末尾加上K.前4個后綴BOOK, OOK, OK和K都在葉節(jié)點上結(jié)束.由于我們要路徑壓縮，只需要 在通往葉節(jié)點的邊上直接加一個字符，而不需要創(chuàng)建一個新節(jié)點.在所有葉節(jié)點更新之后，我們還需要在空后綴后面加上K.這時候我們發(fā)現(xiàn)已經(jīng)存在

11、一條從0節(jié)點出發(fā)的邊的首字符為K,沒必要畫蛇添足了.換句話說，新加入的后綴K可以 在0節(jié)點和2節(jié)點之間的隱式節(jié)點中找到.最終形態(tài)見圖5.圖5加入BOOKK之后的BOOKKEEPER相比圖4,樹的結(jié)構(gòu)沒有發(fā)生變化如果你是一位敏感的讀者，可能要發(fā)問了，如果加入K我們什么都不做的話，在查找的 時候如何知道它到底是一個后綴呢還是某個后綴的一截？如果你同時又是一位熟悉字符串 算法的朋友，心里可能馬上就有答案了 -我們只需要在文本后面加個字母表以外的字符， 比如$或者#.那我們查找到或K#的話就說明這是一個后綴了.稍微麻煩一點的事情從圖4到圖5這個更新過程是相對簡單的，其中我們執(zhí)行了兩種更新：一種是將某條

12、邊 延長，另一種是啥都不做.但接下來往圖5繼續(xù)加入BOOKKE,我們則會遇到另外兩種更 新：創(chuàng)建一個新節(jié)點來割開某一隱式節(jié)點所處的邊，并在其后加一條新邊.在顯式節(jié)點后加一條新邊.圖6先分割，再添加當(dāng)我們往圖5的樹中加入BOOKKE的時候，我們是從已存在的最長后綴BOOKK開始, 一直操作到最短的后綴空后綴.更新最長的后綴必然是更新葉節(jié)點，之前提到了，非常簡單. 除此之外，圖5中結(jié)束在葉節(jié)點上的后綴還有OOKK, OKK, KK.圖6的第一棵樹展示了這 一類節(jié)點的更新.圖5中首個不是結(jié)束在葉節(jié)點上的后綴是K.這里我們先引入一個定義：在每次更新后綴樹的過程中，第一個非葉節(jié)點稱為激活節(jié)點.它有以下性

13、質(zhì)：所有比激活節(jié)點長的后綴都在葉節(jié)點上結(jié)束.所有在激活節(jié)點之后加入的后綴都不在葉節(jié)點上結(jié)束.后綴K在邊KKE上的隱式節(jié)點結(jié)束.在后綴樹中我們要判斷一個節(jié)點是不是非葉節(jié)點 需要看它是否有跟待加入字符相同的兒子，即本例中的E.一眼可以看出，KKE中的第一個K只有一個兒子：K.所以它是非葉節(jié)點（這里同時也是 激活節(jié)點），我們要給他加一個兒子來表示E.這個過程有兩個步驟：在第一個K和第二個K之間把邊分割開，于是第一個K（隱式節(jié)點）成了一個顯式 節(jié)點，如圖6第二棵樹.在剛剛變身而來的顯式節(jié)點后加一個新節(jié)點表示E,如圖6第三棵樹.由此我們 又多了一個葉節(jié)點.后綴K更新之后，別忘了還有空后綴.空后綴在根節(jié)點

14、（節(jié)點0）結(jié)束，顯然此時根節(jié)點 是一個顯式節(jié)點.我們看一下它后面有沒有以E開頭的邊-沒有，那么加入一個新的葉節(jié)點 （如果存在以E開頭的邊,則不用任何操作）.最終如圖7.KE E KKE OKKE圖7歸納，反思，優(yōu)化借助后綴樹的特性，我們可以做出一個相當(dāng)有效的算法.首先一個重要的特性是：一 朝為葉，終生為葉.一個葉節(jié)點自誕生以后絕不會有子孫.更重要的是，每當(dāng)我們往樹上加 入一個新的前綴，每一條通往葉節(jié)點的邊都會延長一個字符（新前綴的最后一個字符）.這使 得處理通往葉節(jié)點的邊變得異常簡單，我們完全可以在創(chuàng)建葉節(jié)點的時候就把當(dāng)前字符到 文本末的所有字符一股腦塞進(jìn)去.是的，我們不需要知道后面的字符是啥

15、，但我們知道它們 最終都要被加進(jìn)去.因此，一個葉節(jié)點誕生的時候，也正是它可以被我們遺忘的時候.你可 能會擔(dān)心通往葉節(jié)點的邊被分割了怎么辦，那也不要緊，分割之后只是起點變了，尾部該怎 么著還是怎么著.如此一來，我們只需要關(guān)心顯式節(jié)點和隱式節(jié)點上的更新.還要提到一個節(jié)約時間的方法.當(dāng)我們遍歷所有后綴時，如果某個后綴的某個兒子跟 待加字符（新前綴最后一個字符）相同，那么我們當(dāng)前前綴的所有更新就可以停止了.如果你 理解了后綴樹的本質(zhì)，你會知道一旦待加字符跟某個后綴的某個兒子相同，那么更短的后 綴必然也有這個兒子.我們不妨把首個這樣的節(jié)點定義為結(jié)束節(jié)點.比結(jié)束節(jié)點長的后綴 必然是葉節(jié)點，這一點很好解釋，

16、要么本來就是葉節(jié)點，要么就是新創(chuàng)建的節(jié)點（新創(chuàng)建的 必然是葉節(jié)點）.這意味著，每一個前綴更新完之后，當(dāng)前的結(jié)束節(jié)點將成為下一輪更新的 激活節(jié)點.好了，現(xiàn)在我們可以把后綴樹的更新限制在激活節(jié)點和結(jié)束節(jié)點之間，效率有了很大 的改善.整理成偽代碼如下：PLAIN TEXTC:Update（新前綴）當(dāng)前后綴=激活節(jié)點待加字符=新前綴最后一個字符done = false;while （ !done ） if （當(dāng)前后綴在顯式節(jié)點結(jié)束）if （當(dāng)前節(jié)點后沒有以待加字符開始的邊）在當(dāng)前節(jié)點后創(chuàng)建一個新的葉節(jié)點elsedone = true; else if （當(dāng)前隱式節(jié)點的下一個字符不是待加字符）從隱式節(jié)點

17、后分割此邊在分割處創(chuàng)建一個新的葉節(jié)點 elsedone = true;if （當(dāng)前后綴是空后綴）done = true;else當(dāng)前后綴=下一個更短的后綴激活節(jié)點=當(dāng)前后綴24. 后綴指針上面的偽代碼看上去很完美，但它掩蓋了一個問題.注意到第21行，“下一個更短的后 綴”，如果呆板地沿著樹枝去搜索我們想要的后綴，那這種算法就不是線性的了.要解決此 問題，我們得附加一種指針：后綴指針.后綴指針存在于每個結(jié)束在非葉節(jié)點的后綴上，它 指向“下一個更短的后綴”.即，如果一個后綴表示文本的第0到第N個字符，那么它的后綴 指針指向的節(jié)點表示文本的第1到第N個字符.圖8是文本ABABABC的后綴樹.第一個后

18、綴指針在表示ABAB的節(jié)點上.ABAB的后 綴指針指向表示BAB的節(jié)點.同樣地，BAB也有它的后綴指針，指向AB.如此這般.ABC. C圖8加上后綴指針（虛線）的ABABABC的后綴樹介紹一下如何創(chuàng)建后綴指針.后綴指針的創(chuàng)建是跟后綴樹的更新同步的.隨著我們從 激活節(jié)點移動到結(jié)束節(jié)點，我把每個新的葉節(jié)點的父親的路徑保存下來.每當(dāng)創(chuàng)建一條新 邊，我同時也在上一個葉節(jié)點的父親那兒創(chuàng)建一個后綴指針來指向當(dāng)前新邊開始的節(jié)點. （顯然，我們不能在第一條新邊上做這樣的操作，但除此之外都可以這么做.）有了后綴指針，就可以方便地一個后綴跳到另一個后綴.這個關(guān)鍵性的附加品使得算 法的時間上限成功降為O（N）.參考文獻(xiàn)E.M. McCreight. A s