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

?

???????? s1=minimize

???????? s2=inimize

???????? s3=nimize

???????? s4=imize

???????? s5=mize

???????? s6=ize

???????? s7=ze

???????? s8=e

?

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

?

?

Suffix Trie的創(chuàng)建?

?

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

?

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

?

Suffix Trie的子串查詢

?

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

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

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

???? (3) 假如N3結(jié)點(diǎn)的關(guān)鍵字K3第一個(gè)字符與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é)點(diǎn)繼續(xù)重復(fù)(1)~(3)的步驟。直到匹配完P(guān)1的所有字符，則匹配成功。否則匹配失敗。

?

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

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

?

Suffix Trie的應(yīng)用

?

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

?

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

?

?

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