聲明
歡迎提出反例來(lái)證明代碼有bug, 雖然我自己測(cè)試了一段時(shí)間成艘，但畢竟測(cè)試不能證明一段代碼沒(méi)有bug??
前言
最近項(xiàng)目中的一個(gè)關(guān)鍵算法使用了后綴樹(shù)(Suffix Tree)來(lái)優(yōu)化匹配速度拷获，所以花時(shí)間去研究了一下辱志。
后綴樹(shù)是一種數(shù)據(jù)結(jié)構(gòu)懈糯，能夠幫助我們快速解決很多關(guān)于字符串的問(wèn)題壕曼。后綴樹(shù)的概念最早由Weiner在1973年提出再芋，后來(lái) McCreight 和Ukkonen又對(duì)其做了改進(jìn)和完善戈盈，本文的主角就是Ukkonen在論文On–line construction of suffix trees中提出的后綴樹(shù)構(gòu)造算法仇穗。
什么是后綴樹(shù)
先給你們看一幅恐怖的后綴樹(shù)表示圖：
是不是頓時(shí)感覺(jué)很頭疼??流部？
其實(shí)還沒(méi)到頭疼的地方。
筆者理解后綴樹(shù)的過(guò)程是: 字典樹(shù)(Trie) ->后綴字典樹(shù)(Suffix Trie) -> 壓縮之后的后綴字典樹(shù)纹坐，即后綴樹(shù)枝冀。
什么是字典樹(shù)(Trie)
Trie常用于詞頻統(tǒng)計(jì)及大量字符串的排序，核心思想是空間換時(shí)間。
Trie長(zhǎng)這樣：
插入ABABA, ABABC
再插入ABBAC
Trie的基本性質(zhì)可以歸納為：
- 根節(jié)點(diǎn)不包含字符果漾，除根節(jié)點(diǎn)意外每個(gè)節(jié)點(diǎn)只包含一個(gè)字符球切。
- 從根節(jié)點(diǎn)到某一個(gè)節(jié)點(diǎn)，路徑上經(jīng)過(guò)的字符連接起來(lái)绒障，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串吨凑。
- 每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符串不相同。
Trie的結(jié)構(gòu)就是這么簡(jiǎn)單直接端盆。如果我們?cè)诠?jié)點(diǎn)的實(shí)現(xiàn)類上加一個(gè)計(jì)數(shù)屬性怀骤，然后
在每次新字符串插入完成時(shí)將所在節(jié)點(diǎn)的計(jì)數(shù)加一，我們就可以實(shí)現(xiàn)詞頻統(tǒng)計(jì)了焕妙。
什么是后綴字典樹(shù)(Suffix Trie)
把一個(gè)字符串的所有后綴都插入到Trie中蒋伦，就得到了Suffix Trie。
壓縮我們的Suffix Trie
通過(guò)觀察上圖焚鹊，我們可以發(fā)現(xiàn)一個(gè)問(wèn)題痕届。
（樹(shù)太長(zhǎng)了一屏都放不下？逃末患。研叫。。璧针。嚷炉。
樹(shù)確實(shí)太長(zhǎng)了，對(duì)于那些沒(méi)有分叉的一連串節(jié)點(diǎn)探橱，完全可以壓縮成一個(gè)單獨(dú)的節(jié)點(diǎn)申屹。
像這樣：
abab的后綴有：
abab, bab, ab, b.
其中ab, b都被隱式的包含了，所以在圖中要好好找一找才能找到隧膏。
我們還發(fā)現(xiàn)圖中有兩條虛線箭頭哗讥，這玩意叫Suffix Link, 是后綴樹(shù)中一個(gè)很重要的概念，下文會(huì)詳述胞枕。
現(xiàn)在我們對(duì)后綴樹(shù)已經(jīng)有了一個(gè)直觀感受了杆煞，對(duì)其的一些應(yīng)用想必也很容易理解。比如模式匹配腐泻。在KMP算法中决乎，我們對(duì)模式串進(jìn)行處理，這種方式在模式串?dāng)?shù)量巨大而文本有限時(shí)就會(huì)顯得低效派桩。這個(gè)時(shí)候?qū)ξ谋具M(jìn)行處理的后綴樹(shù)的優(yōu)勢(shì)就體現(xiàn)出來(lái)了瑞驱。
在使用Ukkonen的算法進(jìn)行后綴樹(shù)的構(gòu)造時(shí)，設(shè)文本長(zhǎng)度是n, 則時(shí)間和空間復(fù)雜度都是O(n), 匹配某個(gè)特定長(zhǎng)度為k的模式時(shí)窄坦，時(shí)間復(fù)雜度是O(k)唤反。
Ukkonen's Algorithm的流程
接下來(lái)我們以aaaabbbbaaaabbbb這個(gè)字符串為例凳寺，描述一遍這個(gè)算法的流程。
我們最后構(gòu)造出來(lái)的后綴樹(shù)長(zhǎng)這樣：
聯(lián)系上文我們知道有一部分后綴因?yàn)橹貜?fù)的原因被隱式的包含了彤侍，而我們?cè)趯?shí)踐中并不希望這樣的情況出現(xiàn)肠缨，所以我們用一個(gè)唯一的標(biāo)識(shí)符$來(lái)表示字符串的結(jié)尾，這樣每一個(gè)后綴都有一個(gè)唯一的結(jié)尾標(biāo)識(shí)符盏阶，就只能被顯示的分叉出來(lái)??晒奕。
Let's begin
代碼實(shí)現(xiàn)的上下文：
程序的輸入是需要構(gòu)建后綴樹(shù)的字符串text。
- Index指針名斟，指向字符串中具體的某一個(gè)字符脑慧。
- ActivePoint(active_node, active_edg, active_length), 它是一個(gè)三元組，里面記錄了當(dāng)前活動(dòng)節(jié)點(diǎn)砰盐，活動(dòng)邊闷袒，及活動(dòng)長(zhǎng)度。對(duì)于這個(gè)概念先不要慌岩梳，看下去就能明白是干什么的囊骤，初始值是(root, null, -1)。
- remainder, 表示我們還需要插入多少個(gè)后綴冀值，初始值是0也物。
-
節(jié)點(diǎn)：在這里使用節(jié)點(diǎn)來(lái)保存信息，保存的信息有該節(jié)點(diǎn)中保存的字符串在text中的開(kāi)始和結(jié)束位置列疗，它的子節(jié)點(diǎn)們滑蚯，以及它的SuffixLink鏈接的節(jié)點(diǎn)。
初始化我們的后綴樹(shù)抵栈，讓它有一個(gè)根節(jié)點(diǎn)
空的后綴樹(shù)
Index = 0膘魄，ActivePoint(root, null, -1), remainder = 0
我們需要插入到位置0為止該字符串的所有后綴，即：a竭讳。
Index = 1, ActivePoint(root, aa, 0), remainder = 1
神奇的事情出現(xiàn)了。因?yàn)槲覀兪鞘褂米笥抑羔榿?lái)代表節(jié)點(diǎn)中保存的字符串浙踢，所以有一件事情我們要注意----所有的葉節(jié)點(diǎn)的右指針跟Index指針保持一致绢慢。
當(dāng)Index變成1的時(shí)候，我們需要插入的后綴是：aa, a洛波。
節(jié)點(diǎn)一的右指針隨著Index自動(dòng)加一胰舆，所以aa已經(jīng)在里面了,我們還需要插入a。
這個(gè)時(shí)候我們發(fā)現(xiàn)a已經(jīng)被隱式的包含了蹬挤。
就這么算了缚窿？
當(dāng)然不，我們必須保證所有的后綴都被表示出來(lái)焰扳，所以我們需要remainder來(lái)記錄我們還需要插入多少個(gè)后綴倦零，并用ActivePoint這個(gè)標(biāo)記误续，用來(lái)表示被隱式包含的后綴在哪。所以現(xiàn)在扫茅，remainder變成了1蹋嵌， ActivePoint變成了：root的一個(gè)叫aa的子節(jié)點(diǎn)的0位置。即a葫隙。
Index = 2, ActivePoint(root, aaa, 1), remainder = 2
現(xiàn)在remainder變成2了栽烂，因?yàn)閍a, a被隱式包含了。
Index = 3, ActivePoint(root, aaaa, 2), remainder = 3
Index = 4, ActivePoint(root, aaa, 1), remainder = 3;
這一步發(fā)生了什么：
我們前進(jìn)到位置4時(shí)恋脚，新的字符b出現(xiàn)了腺办，現(xiàn)在待插入的后綴是aaab, aab, ab, b。
如果我們?cè)贏ctivePoint繼續(xù)往下走糟描，我們會(huì)發(fā)現(xiàn)下一個(gè)是a, 跟b不一樣怀喉，當(dāng)前節(jié)點(diǎn)是aaaab, 所以aaab并沒(méi)有被隱式包含。所以樹(shù)要分叉了蚓挤。在 aaaab中插一個(gè)節(jié)點(diǎn)進(jìn)來(lái)磺送，把a(bǔ)aaab分裂成aaa和ab, 這樣我們就插入了aaab。
現(xiàn)在還剩下aab, ab, b灿意。
這個(gè)分叉給我們帶來(lái)了一個(gè)問(wèn)題估灿，在active_node是根節(jié)點(diǎn)的時(shí)候，分叉發(fā)生之后缤剧，我們?cè)趺锤翧ctivePoint?
我們前面說(shuō)過(guò)馅袁，ActivePoint是用來(lái)表示被隱式包含的待插入后綴的，所以荒辕，當(dāng)前位置的隱式包含后綴被插入了汗销，當(dāng)然是當(dāng)前插入的后綴aaab往前進(jìn)一個(gè)位置，刪掉第一個(gè)字符成aab抵窒，即active_length - 1弛针。
由于后綴樹(shù)的特性，當(dāng)更長(zhǎng)aaa的后綴都被隱式包含的時(shí)候李皇，短一個(gè)字符的后綴aaa肯定也被包含了削茁，而且既然前一個(gè)是從root節(jié)點(diǎn)的子節(jié)點(diǎn)，那后一個(gè)肯定也一樣掉房，這個(gè)特性很容易驗(yàn)證茧跋，所以active_node依然是root。
那active_edg又怎么更新呢卓囚？我們此時(shí)就要開(kāi)始尋找active_node的子節(jié)點(diǎn)中以新后綴的開(kāi)頭開(kāi)頭的子節(jié)點(diǎn)了瘾杭，這個(gè)時(shí)候還是以a開(kāi)頭的，所以不變(如果不是以a開(kāi)頭的哪亿，就需要更換active_edg了)粥烁，此時(shí)ActivePoint變成了(root, aaa, 1)贤笆。
aab被隱式包含了嗎？沒(méi)有页徐，所以我們繼續(xù)分叉
并更新ActivePoint為(root, aa, 0); remainder減去1變成2苏潜。
此時(shí)我們注意到a和aa被一個(gè)虛線箭頭鏈接了起來(lái)，這個(gè)箭頭叫SuffixLink, 意義在于比如當(dāng)我們的ActivePoint指向Node1的位置0時(shí)变勇， 即隱式包含了aaaa時(shí)恤左，我們遇到新的字符串$，于是通過(guò)分叉把a(bǔ)aaa$插進(jìn)去搀绣，接下來(lái)插需要插aaa$飞袋，我們只需要跟著suffixLink走就能確定新的ActivePoint的Active_node的位置，而活動(dòng)長(zhǎng)度只需要保持不變链患。(那我們?cè)趺创_認(rèn)是active_node跟哪個(gè)個(gè)子節(jié)點(diǎn)的邊是active_edg的呢巧鸭？不好意思，我們只能遍歷一下找一找麻捻，看看哪個(gè)子節(jié)點(diǎn)是a開(kāi)頭的）纲仍。關(guān)于SuffixLink的使用后面會(huì)有體現(xiàn)。
如果看不懂前面的描述贸毕，只需要先記字５：
在一次插入剩余后綴的流程中后面分裂的節(jié)點(diǎn)都應(yīng)該被前面分裂的節(jié)點(diǎn)用SuffixLink鏈接起來(lái)。
接下來(lái)我們?cè)俣确植娌迦隺b
b沒(méi)有被隱式包含明棍，此時(shí)ActivePoint是(root, null, -1);
直接插入b
因?yàn)殡[式包含的原因乡革，往前走了三步
Index = 7, ActivePoint(root, bbbb, 2), remainder = 3;
Index = 8, ActivePoint(root, null, -1), remainder = 1
重復(fù)上面的分叉流程
插入了bbba, bba, ba
新的問(wèn)題出現(xiàn)了，a這個(gè)后綴被隱式包含了摊腋，所以我們退出這次插入沸版，把活動(dòng)點(diǎn)改成(root, a, 0)。但我們發(fā)現(xiàn)兴蒸，這個(gè)時(shí)候我們的活動(dòng)點(diǎn)指向了Node6的結(jié)尾视粮，所以我們需要將ActivePoint更新位(6, null, -1)。這樣我們才能繼續(xù)隱式包含的查找橙凳。
Index = 8, ActivePoint(6, null, -1), remainder = 1
通過(guò)觀察圖像我們可以預(yù)料到蕾殴，接下來(lái)的aaabbbb全是已經(jīng)在樹(shù)中的，所以我們會(huì)得到：
Index = 15, ActivePoint(2, abbbbaaaabbbb, 4), remainder = 8
接下來(lái)就是我們的$大顯神威的時(shí)候了痕惋，它會(huì)把所有的隱式包含后綴都變成顯式的。
而且現(xiàn)在我們面臨了新的情況娃殖，active_node不是根節(jié)點(diǎn)值戳，所以我們會(huì)探討這個(gè)時(shí)候發(fā)生節(jié)點(diǎn)分裂后怎么更新active_node。
我們也發(fā)現(xiàn)了圖中有大量的SuffixLink, 所以我們也會(huì)探討SuffixLink的使用炉爆。
我們現(xiàn)在的情況堕虹，簡(jiǎn)單一點(diǎn)來(lái)說(shuō)卧晓，就是在Index指向$時(shí)，插入aaaabbbb$的所有后綴赴捞。
Index = 16, ActivePoint(2, bbbbaaaabbbb$, 3), remainder = 8
這一步發(fā)生了什么逼裆？
首先，我們照例分裂了activePoint指定的節(jié)點(diǎn)赦政，插入$, 完成了aaaabbbb$的插入胜宇。
然后發(fā)現(xiàn)，這里沒(méi)有SuffixLink, 但是恢着，既然aaaabbbb都被包含了桐愉，那么aaabbbb一定也已經(jīng)被包含了，所以我們把a(bǔ)ctive_node設(shè)置成了root掰派。
由于接下來(lái)需要插入aaabbbb$, 所以active_length是6(注意對(duì)長(zhǎng)度的計(jì)數(shù)為了實(shí)現(xiàn)的方便也從0開(kāi)始)从诲。
從root開(kāi)始，我們順著aaabbbb在樹(shù)中的路徑一路前進(jìn)靡羡，就能發(fā)現(xiàn)aaabbbb在樹(shù)中的結(jié)尾在2的子節(jié)點(diǎn)bbbbaaaabbbb$的位置3系洛，于是，新的ActivePoint就被確定了：
（2略步，bbbbaaaabbbb$, 3)描扯。
這是比較繁瑣的一步，有了suffixLink的話會(huì)簡(jiǎn)單很多纳像。
Index = 16, ActivePoint(4, bbbbaaaabbbb$, 3), remainder = 7
觀察：SuffixLink的妙用：
我們通過(guò)分裂節(jié)點(diǎn)3（bbbbaaaabbbb$）可以完成aaabbbb$的插入荆烈。
然后跟著SuffixLink把a(bǔ)ctive_node設(shè)置成節(jié)點(diǎn)4，active_length不變竟趾，active_edg也不變憔购。
我們可以驗(yàn)證，通過(guò)suffixLink來(lái)更新 activePoint和通過(guò)把a(bǔ)ctive_node設(shè)置為root然后一步一步往前走得到的結(jié)果是一樣的岔帽。
當(dāng)我們分裂了一個(gè)節(jié)點(diǎn)需要更新active_node的時(shí)候玫鸟，如果當(dāng)前的active_node有suffixLink, 我們直接把a(bǔ)ctive_node更新成被指向的節(jié)點(diǎn)，activePoint的其他數(shù)據(jù)不變犀勒。
于是我們按照上述流程繼續(xù)分裂或插入后綴屎飘，就能得到我們的最終結(jié)果。
再放一遍圖：
以上是對(duì)整個(gè)算法流程的描述贾费，如果覺(jué)得筆者沒(méi)有講清楚钦购，可以到Visualization of Ukkonen's Algorithm上跟一遍完整的流程。喜歡英文資料的童鞋們也可以到stackoveflow上看一下外國(guó)某大佬的解釋??褂萧。不過(guò)最好的學(xué)習(xí)方式當(dāng)然還是自己實(shí)現(xiàn)一遍啦??押桃。
Java實(shí)現(xiàn)
當(dāng)前還只是嘗試性的實(shí)現(xiàn)，并沒(méi)有翻譯成項(xiàng)目用的語(yǔ)言并加入到項(xiàng)目中导犹，有興趣的同學(xué)可以讀一讀測(cè)一測(cè)唱凯，如果能幫忙找出Bug那就真是太感謝了（畢竟整合進(jìn)項(xiàng)目要改就比較爆炸??）
GitHub
