後綴樹
在pongba的討論組上看到一道Amazon的麵試題:找出給定字符串裏的最長回文。例子:輸入XMADAMYX。則輸出MADAM。這道題的流行解法是用後綴樹(Suffix Tree)。這坨數據結構最酷的地方是用它能高效解決一大票複雜的字符串編程問題:
- 在文本T裏查詢T是否包含子串P(複雜度同流行的KMP相當)。
- 文本T裏找出最長重複子串。比如abcdabcefda裏abc同da都重複出現,而最長重複子串是abc。
- 找出字符串S1同S2的最長公共子串。注意不是常用作動態規劃例子的LCS哈。比如字符串acdfg同akdfc的最長公共子串為df,而他們的LCS是adf。
- Ziv-Lampel無損壓縮算法。
- 還有就是這道麵試題問的最長回文了。
另外後綴樹在生物信息學裏應該應用廣泛。堿基匹配和選取的計算本質上就是操作超長的{C, T, A, G, U}*字符串嘛。
雖說後綴樹的概念獨立於Trie的概念,但我覺得從Trie推出後綴樹自然簡潔,所以先簡單解釋一下Trie。“Trie”這個單詞來自於"retrieve",可見它的用途主要是字符串查詢。不過詞匯變遷多半比較詭異,Trie不發tree的音,而發try的音。
Trie是坨簡單但實用的數據結構,通常用於實現字典查詢。我們做即時響應用戶輸入的AJAX搜索框時,就是Trie開始。誰說學點數據結構沒用來 著?本質上,Trie是一顆存儲多個字符串的樹。相鄰節點間的邊代表一個字符,這樣樹的每條分支代表一則子串,而樹的葉節點則代表完整的字符串。和普通樹 不同的地方是,相同的字符串前綴共享同一條分支。還是例子最清楚。給出一組單詞,inn, int, at, age, adv, ant, 我們可以得到下麵的Trie:
可以看出:
- 每條邊對應一個字母。
- 每個節點對應一項前綴。葉節點對應最長前綴,即單詞本身。
- 單詞inn與單詞int有共同的前綴“in”, 因此他們共享左邊的一條分支,root->i->in。同理,ate, age, adv, 和ant共享前綴"a",所以他們共享從根節點到節點"a"的邊。
- 查詢非常簡單。比如要查找int,順著路徑i -> in -> int就找到了。
- 搭建Trie的基本算法也很簡單,無非是逐一把每則單詞的每個字母插入Trie。插入前先看前綴是否存在。如果存在,就共享,否則創建對應的節點和邊。比如要插入單詞add,就有下麵幾步:
- 考察前綴"a",發現邊a已經存在。於是順著邊a走到節點a。
- 考察剩下的字符串"dd"的前綴"d",發現從節點a出發,已經有邊d存在。於是順著邊d走到節點ad
- 考察最後一個字符"d",這下從節點ad出發沒有邊d了,於是創建節點ad的子節點add,並把邊ad->add標記為d。
繼續插播廣告。Graph作圖軟件Graphviz還不錯,用的DSL相當簡單。上麵的圖就是用它做的。三步就夠了:
- 實現Trie數據結構。這步不用花哨。10行代碼,一坨hash足矣。
- 把上麵的結構翻譯成Graphviz的DSL。簡單的深度優先足矣。
- 調用Graphviz的命令。圖就生成樂。
多花20分鍾,避免了手工作圖排版的自虐行為。而且可以自由試驗各式例子而不用擔心反複畫圖的瑣碎,何樂而不為囁?
有了Trie,後綴樹就容易理解了。先說說後綴的定義。給定一長度為n的字符串S=S1S2..Si..Sn,和整數i,1 <= i <= n,子串SiSi+1...Sn都是字符串S的後綴。以字符串S=XMADAMYX為例,它的長度為8,所以S[1..8], S[2..8], ... , S[8..8]都算S的後綴,我們一般還把空字串也算成後綴。這樣,我們一共有如下後綴。對於後綴S[i..n],我們說這項後綴起始於i。
- S[1..8], XMADAMYX, 也就是字符串本身,起始位置為1
- S[2..8], MADAMYX,起始位置為2
- S[3..8], ADAMYX,起始位置為3
- S[4..8], DAMYX,起始位置為4
- S[5..8], AMYX,起始位置為5
- S[6..8], MYX,起始位置為6
- S[7..8], YX,起始位置為7
- S[8..8], X,起始位置為8
- 空字串。記為$。
而後綴樹,就是包含一則字符串所有後綴的壓縮Trie。把上麵的後綴加入Trie後,我們得到下麵的結構:
仔細觀察上圖,我們可以看到不少值得壓縮的地方。比如藍框標注的分支都是獨苗,沒有必要用單獨的節點同邊表示。如果我們允許任意一條邊裏包含多個字 母,就可以把這種沒有分叉的路徑壓縮到一條邊。另外每條邊已經包含了足夠的後綴信息,我們就不用再給節點標注字符串信息了。我們隻需要在葉節點上標注上每 項後綴的起始位置。於是我們得到下圖:
這樣的結構丟失了某些後綴。比如後綴X在上圖中消失了,因為它正好是字符串XMADAMYX的前綴。為了避免這種情況,我們也規定每項後綴不能是其 它後綴的前綴。要解決這個問題其實挺簡單,在待處理的子串後加一坨空字串就行了。例如我們處理XMADAMYX前,先把XMADAMYX變為 XMADAMYX$,於是就得到suffix tree樂。
那後綴樹同最長回文有什麼關係呢?我們得先知道兩坨坨簡單概念:
- 最低共有祖先,LCA(Lowest Common Ancestor),也就是任意兩節點(多個也行)最長的共有前綴。比如下圖中,節點7同節點10的共同祖先是節點1與借點,但最低共同祖先是5。 查找LCA的算法是O(1)的複雜度,這年頭少見。代價是需要對後綴樹做複雜度為O(n)的預處理。
- 廣 義後綴樹(Generalized Suffix Tree)。傳統的後綴樹處理一坨單詞的所有後綴。廣義後綴樹存儲任意多個單詞的所有後綴。例如下圖是單詞XMADAMYX與XYMADAMX的廣義後綴 樹。注意我們需要區分不同單詞的後綴,所以葉節點用不同的特殊符號與後綴位置配對。
有了上麵的概念,查找最長回文相對簡單了。思維的突破點在於考察回文的半徑,而不是回文本身。所謂半徑,就是回文對折後的字串。比如回文MADAM 的半徑為MAD,半徑長度為3,半徑的中心是字母D。顯然,最長回文必有最長半徑,且兩條半徑相等。還是以MADAM為例,以D為中心往左,我們得到半徑 DAM;以D為中心向右,我們得到半徑DAM。二者肯定相等。因為MADAM已經是單詞XMADAMYX裏的最長回文,我們可以肯定從D往左數的字串 DAMX與從D往右數的子串DAMYX共享最長前綴DAM。而這,正是解決回文問題的關鍵。現在我們有後綴樹,怎麼把從D向左數的字串DAMX變成後綴 呢?到這個地步,答案應該明顯:把單詞XMADAMYX翻轉就行了。於是我們把尋找回文的問題轉換成了尋找兩坨後綴的LCA的問題。當然,我們還需要知道 到底查詢那些後綴間的LCA。這也簡單,給定字符串S,如果最長回文的中心在i,那從位置i向右數的後綴剛好是S(i),而向左數的字符串剛好是翻轉S後 得到的字符串S‘的後綴S'(n-i+1)。這裏的n是字符串S的長度。有了這套直觀解釋,算法自然唿之欲出:
- 預處理後綴樹,使得查詢LCA的複雜度為O(1)。這步的開銷是O(N),N是單詞S的長度
- 對單詞的每一位置i(也就是從0到N-1),獲取LCA(S(i), S(N-i+1)) 以及LCA(S(i+1), S(n-i+1))。查找兩次的原因是我們需要考慮奇數回文和偶數回文的情況。這步要考察每坨i,所以複雜度是O(N)
- 找到最大的LCA,我們也就得到了回文的中心i以及回文的半徑長度,自然也就得到了最長回文。總的複雜度O(n)。
用上圖做例子,i為3時,LCA(3$, 4#)為DAM,正好是最長半徑。當然,這隻是直觀的敘述。
這篇帖子隻大致描述了後綴樹的基本思路。要想寫出實用代碼,至少還得知道下麵的知識:
- 創建後綴樹的O(n)算法。至於是Peter Weiner的73年年度最佳算法,還是Edward McCreight1976的改進算法,還是1995年E. Ukkonen大幅簡化的算法,還是Juha Kärkkäinen 和 Peter Sanders2003年進一步簡化的線性算法,各位老大隨喜。
- 實現後綴樹用的數據結構。比如常用的子結點加兄弟節點列表,Directed
- 優化後綴樹空間的辦法。比如不存儲子串,而存儲讀取子串必需的位置。以及Directed Acyclic Word Graph,常縮寫為黑哥哥們掛在嘴邊的DAWG。
最後更新:2017-04-03 19:06:50