Suffix Trie ： 又稱后綴Trie或后綴樹。它與Trie樹的最大不同在于，后綴Trie的字符串集合是由指定字符串的后綴子串構(gòu)成的。比如、完整字符串"minimize"的后綴子串組成的集合S分別如下：

?

???????? s1=minimize

???????? s2=inimize

???????? s3=nimize

???????? s4=imize

???????? s5=mize

???????? s6=ize

???????? s7=ze

???????? s8=e

?

????? 然后把這些子串的公共前綴作為內(nèi)部結(jié)點構(gòu)成一棵"minimize"的后綴樹，如圖所示，其中上圖是Trie樹的字符表示，下圖是壓縮表示(詳細(xì)見《 Trie樹 》)。 可見Suffic Trie是一種很適合操作字符串子串的數(shù)據(jù)結(jié)構(gòu)。 它和PAT tree在這一點上類似。

?

?

Suffix Trie的創(chuàng)建?

?

????? 標(biāo)準(zhǔn)Tire樹的每一個內(nèi)部結(jié)點只有一個字符，也就是說公共前綴每一次只找一個。而Suffix Trie的公共前綴可以是多個字符，因此在創(chuàng)建Suffix Trie的時候，每插入一個后綴子串，就可能對內(nèi)部結(jié)點造成一次分類。下面我們我們看一種后綴樹構(gòu)造算法。以"minimize"為例：

?

????? 當(dāng)插入子串時，發(fā)現(xiàn)葉子結(jié)點中的關(guān)鍵字與子串有公共前綴，則需要將該葉子結(jié)點分裂。如上圖第3到4步。否則，重新創(chuàng)建一個葉子結(jié)點來存放后綴，如上圖第1到2步

?

Suffix Trie的子串查詢

?

???? 如果在后綴樹T中查找子串P，我們需要這樣的過程：

???? (1) 從根結(jié)點root出發(fā)，遍歷所有的根的孩子結(jié)點：N1,N2,N3....

???? (2) 如果所有孩子結(jié)點中的關(guān)鍵字的第一個字符都和P的第一個字符不匹配，則沒有這個子串，查找結(jié)束。

???? (3) 假如N3結(jié)點的關(guān)鍵字K3第一個字符與P的相同，則匹配K3和P。

????????? 若 K3.length>=P.length? 并且K3.subString(0,P.length-1)=P，則匹配成功，否則匹配失敗。

????????? 若 K3.length<=P.length? 并且K3=P.subString(0, K3.length-1)，則將子串P1=P.subString(K3.length, P.length); 即取出P中排除K3之后的子串。然后P1以N3為根結(jié)點繼續(xù)重復(fù)(1)~(3)的步驟。直到匹配完P(guān)1的所有字符，則匹配成功。否則匹配失敗。

?

????? 查詢效率：很顯然，在上面的算法中。匹配成功正好比較了P.length次字符。而定位結(jié)點的孩子指針，和Trie情況類似，假如字母表數(shù)量為d。則查詢效率為O(d*m)，實際上，d是固定常數(shù)，如果使用Hash表直接定位，則d=1.

????? 因此，后綴樹查詢子串P的時間復(fù)雜度為O(m)，其中m為P的長度。

?

Suffix Trie的應(yīng)用

?

????? 標(biāo)準(zhǔn)Trie樹只適合前綴匹配和全字匹配，并不適合 后綴和子串匹配。而后綴樹在這方面則非常合適。

?

????? 另外 后綴樹也可以進(jìn)行前綴匹配。 如果模式串P是字符串S的前綴的話，那么從根結(jié)點出發(fā)遍歷后綴樹，一定能夠?qū)ふ业揭粭l路徑完全匹配完P(guān)。比如上圖： 模式串P=“mini”，主串S="minimize"。P從根節(jié)點出發(fā)，首先匹配到結(jié)點mi，然后再匹配孩子結(jié)點nimize。直到P中所有的字符都找到為止。所以P是S的前綴。

?

?

【串和序列處理 4】Suffix Trie 子串匹配結(jié)構(gòu)