字尾樹的構造方法-Ukkonen詳解
2010-09-13 21:47:06| 分類： 算法 | 标簽：字尾樹的構造方法- ukkonen詳解 |字号大中小 訂閱
最近在學習字尾樹的構造，在網上找了好久發覺國内詳解它的構造的文章勝少，在苦苦尋覓了許久，終于發現了一個網友翻譯的一篇文章，很好，于是我轉帖出來，希望能有更多的人受益，也希望國内多一些英文高手多翻譯一些國外的技術文章，好讓我們這些英文很爛的人受益，呵呵！
字尾樹
Fast String Searching With Suffix Trees
原著
Mark Nelson. Fast string searching with suffix trees. 1996.
構造法
E. Ukkonen. On-line construction of suffix trees. 1995.
翻譯
3xian / 三鮮 in GDUT
三鮮 序
原來是打算翻譯Sartaj Sahni的Suffix tree, 并專注地進行了一周, 連複習備考的時間也不惜占去. 我希望給國産的同好者提供更通俗易懂的資料, 在翻譯的同時對原文進行了删改, 并加入了許多自己的心得. 然而後來發現了Mark Nelson的這篇文章, 相比之下更有親和力, 于是老實地盡棄前功來翻譯這篇. 更重要一個原因是, Mark Nelson介紹的是Ukkonen的構造法O(n), 它比Sartaj Sahni的構造法O(nr), r為字母表大小 在時間上更有優勢. 但我們不能說Sartaj Sahni的算法慢, 因為r往往會很小, 是以實際效率也接近線性, 兩種構造法在思想上均有可取之處.
本文偏重于闡述字尾樹的構造過程, 而并沒有直接介紹字尾樹除了比對以外還能做什麼. 其實字尾樹是一種功能非常強大的資料結構, 你可以去搜尋引擎了解一下它還有多少功能, 當然我最希望的是你在閱讀本文之後已經足以體會字尾樹的妙處, 日後遇到諸多問題的時候都能随心随意地用上.
最後唠叨一句. 我所見過的各種介紹字尾樹的論文都難免使初學者陷入混亂, 本文估計也好不到哪裡去. 這在一定程度上說明了字尾樹的原理是不太淺顯的, 了解它需要在整體上把握, 建議希望讀者先不要糾結于細節, 思路不清則反複閱讀.
問題的來源
字元串比對問題是程式員經常要面對的問題. 字元串比對算法的改進可以使許多工程受益良多, 比如資料壓縮和DNA排列. 這篇文章讨論的是一種相對鮮為人知的資料結構 --- 字尾樹, 并介紹它是如何通過自身的特性去解決一些複雜的比對問題.
你可以把自己想象成一名工作于DNA排列工程的程式員. 那些基因研究者們天天忙着分切病毒的基因材料, 制造出一段一段的核苷酸序列. 他們把這些序列發到你的伺服器裡, 指望你在基因資料庫中定位. 要知道, 你的資料庫裡有數百種病毒的資料, 而一個特定的病毒可以有成千上萬的堿基. 你的程式必須像C/S工程那樣實時向博士們回報資訊, 這需要一個很好的方案.
很明顯, 在這個問題上采取暴力算法是極其低效的. 這種方法需要你在基因資料庫裡對比每一個核苷酸, 測試一個較長的基因段基本會把你的C/S系統變成一台古老的批處理機.
直覺上的解決方法
由于基因資料庫一般是不變的, 通過預處理來把搜尋簡化或許是個好主意. 一種預處理的方法是建立一棵Trie. 我們通過Trie引申出一種東西叫作字尾Trie. (字尾Trie離字尾樹僅一步之遙.) 首先, Trie是一種n叉樹, n為字母表大小, 每個節點表示從根節點到此節點所經過的所有字元組成的字元串. 而字尾Trie的 “字尾” 說明這棵Trie包含了所給字段的所有字尾 (也許正是一個病毒基因).
圖1
BANANAS的字尾Trie
圖1展示了文本BANANAS的字尾Trie. 關于這棵Trie有兩個地方需要注意. 第一, 從根節點開始, BANANAS的每一個字尾都插入到Trie中, 包括BANANAS, ANANAS, NANAS, ANAS, NAS, AS, S. 第二, 鑒于這種結構, 你可以通過從根節點往下比對的方式搜尋到單詞的任何一個子串.
這裡所說的第二點正是我們認為字尾Trie優秀的原因. 如果你輸入一個長度為N的文本并想在其中搜尋一個長度為M的串, 傳統的暴力比對需要進行N*M次字元對比, 而一些改進過的比對技術, 比如像Boyer-Moore算法, 可以在O(N+M)的時間開銷内解決問題, 平均效率更是令人滿意. 然而, 字尾Trie亮出了O(M)的牌子, 徹底鄙視了其他算法的成績, 字尾Trie對比的次數僅僅相當于被搜尋串的長度!
這确實是可圈可點的威力, 這意味着你能通過僅僅7次對比便在莎士比亞所有作品中找出BANANAS. 但有一點我們可不能忘了, 構造字尾Trie也是需要時間的.
字尾Trie之是以沒有家喻戶曉正是因為構造它需要O(n2)的時間和空間. 平方級的開銷使它在最需要它的領域 --- 長串搜尋 中被拒之門外.
橫空出世
直到1976年, Edward McCreigh發表了一篇論文, 咱們的字尾樹問世了. 字尾Trie的困境被徹底打破.
字尾樹跟字尾Trie有着一樣的布局, 但它把隻有一個兒子的節點給剔除了. 這個過程被稱為路徑壓縮, 這意味着樹上的某些邊将表示一個序列而不是單獨的字元.
圖2
BANANAS的字尾樹
圖2是由圖1的字尾Trie轉化而來的字尾樹. 你會發現這樹基本還是那個形狀, 隻是節點變少了. 在剔除了隻有一個兒子的節點之後, 總節點數由23降為11. 經過證明, 在最壞情況下, 字尾樹的節點數也不會超過2N (N為文本的長度). 這使構造字尾樹的線性時空開銷成為可能.
然而, McCreight最初的構造法是有些缺陷的, 原則上它要按逆序構造, 也就是說字元要從末端開始插入. 如此一來, 便不能作為線上算法, 它變得更加難以應用于實際問題, 如資料壓縮.
20年後, 來自赫爾辛基理工大學的Esko Ukkonen把原算法作了一些改動, 把它變成了從左往右. 本文接下來的所有描述和代碼都是基于Esko Ukkonen的成果.
對于所給的文本T, Esko Ukkonen的算法是由一棵空樹開始, 逐漸構造T的每個字首的字尾樹. 比如我們構造BANANAS的字尾樹, 先由B開始, 接着是BA, 然後BAN, … . 不斷更新直到構造出BANANAS的字尾樹.
圖3
逐漸構造字尾樹
初窺門徑
加入一個新的字首需要通路樹中已有的字尾. 我們從最長的一個字尾開始(圖3中的BAN), 一直通路到最短的字尾(空字尾). 每個字尾會在以下三種節點的其中一種結束.
l 一個葉節點. 這個是常識了, 圖4中标号為1, 2, 4, 5的就是葉節點.
l 一個顯式節點. 圖4中标号為0, 3的是顯式節點, 它表示該節點之後至少有兩條邊.
l 一個隐式節點. 圖4中, 字首BO, BOO, 或者非字首OO, 它們都在某條表示序列的邊上結束, 這些位置就叫作隐式節點. 它表示字尾Trie中存在的由于路徑壓縮而剔除的節點. 在字尾樹的構造過程中, 有時要把一些隐式節點轉化為顯式節點.
圖4
加入BOOK之後的BOOKKEEPER
(也就是BOOK的字尾樹)
如圖4, 在加入BOOK之後, 樹中有5個字尾(包括空字尾). 那麼要構造下一個字首BOOKK的字尾樹的話, 隻需要通路樹中已存在的每一個字尾, 然後在它們的末尾加上K.
前4個字尾BOOK, OOK, OK和K都在葉節點上結束. 由于我們要路徑壓縮, 隻需要在通往葉節點的邊上直接加一個字元, 而不需要建立一個新節點.
在所有葉節點更新之後, 我們還需要在空字尾後面加上K. 這時候我們發現已經存在一條從0節點出發的邊的首字元為K, 沒必要畫蛇添足了. 換句話說, 新加入的字尾K可以在0節點和2節點之間的隐式節點中找到. 最終形态見圖5.
圖5加入BOOKK之後的BOOKKEEPER
相比圖4, 樹的結構沒有發生變化
如果你是一位敏感的讀者, 可能要發問了, 如果加入K我們什麼都不做的話, 在查找的時候如何知道它到底是一個字尾呢還是某個字尾的一截? 如果你同時又是一位熟悉字元串算法的朋友, 心裡可能馬上就有答案了 --- 我們隻需要在文本後面加個字母表以外的字元, 比如$或者#. 那我們查找到K$或K#的話就說明這是一個字尾了.
稍微麻煩一點的事情
從圖4到圖5這個更新過程是相對簡單的, 其中我們執行了兩種更新: 一種是将某條邊延長, 另一種是啥都不做. 但接下來往圖5繼續加入BOOKKE, 我們則會遇到另外兩種更新:
1. 建立一個新節點來割開某一隐式節點所處的邊, 并在其後加一條新邊.
2. 在顯式節點後加一條新邊.
圖6
先分割, 再添加
當我們往圖5的樹中加入BOOKKE的時候, 我們是從已存在的最長字尾BOOKK開始, 一直操作到最短的字尾空字尾. 更新最長的字尾必然是更新葉節點, 之前提到了, 非常簡單. 除此之外, 圖5中結束在葉節點上的字尾還有OOKK, OKK, KK. 圖6的第一棵樹展示了這一類節點的更新.
圖5中首個不是結束在葉節點上的字尾是K. 這裡我們先引入一個定義:
在每次更新字尾樹的過程中, 第一個非葉節點稱為激活節點. 它有以下性質:
1. 所有比激活節點長的字尾都在葉節點上結束.
2. 所有在激活節點之後加入的字尾都不在葉節點上結束.
字尾K在邊KKE上的隐式節點結束. 在字尾樹中我們要判斷一個節點是不是非葉節點需要看它是否有跟待加入字元相同的兒子, 即本例中的E.
一眼可以看出, KKE中的第一個K隻有一個兒子: K. 是以它是非葉節點(這裡同時也是激活節點), 我們要給他加一個兒子來表示E. 這個過程有兩個步驟:
1. 在第一個K和第二個K之間把邊分割開, 于是第一個K(隐式節點)成了一個顯式節點, 如圖6第二棵樹.
2. 在剛剛變身而來的顯式節點後加一個新節點表示E, 如圖6第三棵樹. 由此我們又多了一個葉節點.
字尾K更新之後, 别忘了還有空字尾. 空字尾在根節點(節點0)結束, 顯然此時根節點是一個顯式節點. 我們看一下它後面有沒有以E開頭的邊---沒有, 那麼加入一個新的葉節點(如果存在以E開頭的邊, 則不用任何操作). 最終如圖7.
圖7
歸納, 反思, 優化
借助字尾樹的特性, 我們可以做出一個相當有效的算法. 首先一個重要的特性是: 一朝為葉, 終生為葉. 一個葉節點自誕生以後絕不會有子孫. 更重要的是, 每當我們往樹上加入一個新的字首, 每一條通往葉節點的邊都會延長一個字元(新字首的最後一個字元). 這使得處理通往葉節點的邊變得異常簡單, 我們完全可以在建立葉節點的時候就把目前字元到文本末的所有字元一股腦塞進去. 是的, 我們不需要知道後面的字元是啥, 但我們知道它們最終都要被加進去. 是以, 一個葉節點誕生的時候, 也正是它可以被我們遺忘的時候. 你可能會擔心通往葉節點的邊被分割了怎麼辦, 那也不要緊, 分割之後隻是起點變了, 尾部該怎麼着還是怎麼着.
如此一來, 我們隻需要關心顯式節點和隐式節點上的更新.
還要提到一個節約時間的方法. 當我們周遊所有字尾時, 如果某個字尾的某個兒子跟待加字元(新字首最後一個字元)相同, 那麼我們目前字首的所有更新就可以停止了. 如果你了解了字尾樹的本質, 你會知道一旦待加字元跟某個字尾的某個兒子相同, 那麼更短的字尾必然也有這個兒子. 我們不妨把首個這樣的節點定義為結束節點. 比結束節點長的字尾必然是葉節點, 這一點很好解釋, 要麼本來就是葉節點, 要麼就是新建立的節點(新建立的必然是葉節點). 這意味着, 每一個字首更新完之後, 目前的結束節點将成為下一輪更新的激活節點.
好了, 現在我們可以把字尾樹的更新限制在激活節點和結束節點之間, 效率有了很大的改善. 整理成僞代碼如下:
PLAIN TEXT
C:
1. Update( 新字首 )
2. {
3. 目前字尾 = 激活節點
4. 待加字元 = 新字首最後一個字元
5. done = false;
6. while ( !done ) {
7. if ( 目前字尾在顯式節點結束 ) {
8. if ( 目前節點後沒有以待加字元開始的邊 )
9. 在目前節點後建立一個新的葉節點
10. else
11. done = true;
12. } else {
13. if ( 目前隐式節點的下一個字元不是待加字元 ) {
14. 從隐式節點後分割此邊
15. 在分割處建立一個新的葉節點
16. } else
17. done = true;
18. if ( 目前字尾是空字尾 )
19. done = true;
20. else
21. 目前字尾 = 下一個更短的字尾
22. }
23. 激活節點 = 目前字尾
24. }
字尾指針
上面的僞代碼看上去很完美, 但它掩蓋了一個問題. 注意到第21行, “下一個更短的字尾”, 如果呆闆地沿着樹枝去搜尋我們想要的字尾, 那這種算法就不是線性的了. 要解決此問題, 我們得附加一種指針: 字尾指針. 字尾指針存在于每個結束在非葉節點的字尾上, 它指向“下一個更短的字尾”. 即, 如果一個字尾表示文本的第0到第N個字元, 那麼它的字尾指針指向的節點表示文本的第1到第N個字元.
圖8是文本ABABABC的字尾樹. 第一個字尾指針在表示ABAB的節點上. ABAB的字尾指針指向表示BAB的節點. 同樣地, BAB也有它的字尾指針, 指向AB. 如此這般.
圖8
加上字尾指針(虛線)的ABABABC的字尾樹
介紹一下如何建立字尾指針. 字尾指針的建立是跟字尾樹的更新同步的. 随着我們從激活節點移動到結束節點, 我把每個新的葉節點的父親的路徑儲存下來. 每當建立一條新邊, 我同時也在上一個葉節點的父親那兒建立一個字尾指針來指向目前新邊開始的節點. (顯然, 我們不能在第一條新邊上做這樣的操作, 但除此之外都可以這麼做.)
有了字尾指針, 就可以友善地一個字尾跳到另一個字尾. 這個關鍵性的附加品使得算法的時間上限成功降為O(N).