算法合集之《Trie圖的構(gòu)建活用與改進(jìn)》

1、Trie圖的構(gòu)建、活用與改進(jìn) Maigo 200我們知道trie樹（也叫字母樹）這種數(shù)據(jù)結(jié)構(gòu)。它是詞典的一種存儲方式。詞典中的每一個單詞在trie樹中表現(xiàn)為一條從根結(jié)點出發(fā)的路徑，路徑中邊上的字母連起來就形成對應(yīng)的單詞。圖1就是一棵trie樹，其中含有a,abc,bac,bbc,ca五個單詞。利用trie樹可以對詞典中的單詞進(jìn)行一些適合用樹這種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的操作，如求兩個單詞的公共前綴長度（在樹中表現(xiàn)為求兩個單詞對應(yīng)結(jié)點的最近公共祖先）。其實，如果把trie樹加以改造，多連一些邊，形成的trie圖在解決多模式串匹配問題上會發(fā)揮奇效。左：圖1，一棵含有五個單詞的trie樹。紅色表示單詞終止的位置

2、。右：圖2，由圖1的trie樹改造成的trie圖。紅色表示危險結(jié)點，白色表示真安全結(jié)點，藍(lán)色表示新加的邊。為簡單起見，危險結(jié)點以下的結(jié)點及與之關(guān)聯(lián)的邊沒有畫出。一、Trie圖的構(gòu)建我們通過一個例題來探究trie圖的構(gòu)建方法?！纠?】不良單詞探測器【題目描述】給出一個詞典，其中的單詞為不良單詞。單詞均為小寫字母。再給出一段文本，文本的每一行也由小寫字母構(gòu)成。判斷文本中是否含有任何不良單詞。例如，若rob是不良單詞，那么文本problem含有不良單詞?！据斎搿康谝恍袨橐粋€整數(shù)n，表示不良單詞的個數(shù)。接下來n行是詞典。下面一行為一個整數(shù)m，表示文本的行數(shù)。接下來m行是文本?！据敵觥咳绻谋景涣紗?/p>

3、詞，輸出一行“Yes”，否則輸出一行“No”。【樣例輸入】1rob1internetproblemsolvingcontest【樣例輸出】Yes【備注】因本題只是用來討論trie圖的構(gòu)建方法，故未給出數(shù)據(jù)范圍。【分析】判斷文本是否包含不良單詞可以一行一行地判斷。而判斷長為L的一行文本s是否含有不良單詞可以這樣進(jìn)行：讓i從1變化到L，依次判斷s的前i個字符構(gòu)成的字符串是否以不良單詞結(jié)尾。然而，我們希望在判斷s的前k個字符時，能夠利用前k-1個字符的結(jié)果，即這兩個狀態(tài)間可以方便地進(jìn)行轉(zhuǎn)移。注意到trie樹中的邊正如一個個“方向標(biāo)”，因此我們有了一個美好的設(shè)想：從根結(jié)點出發(fā)，沿著標(biāo)有s1的邊走一步，

4、再沿標(biāo)有s2的邊走一步，一直這樣走下去！現(xiàn)在有了一個問題：如果從當(dāng)前走到的結(jié)點出發(fā)，沒有需要走的邊，該怎么辦？只要“創(chuàng)造”一條這樣的邊即可。那么這條邊應(yīng)該指向哪個結(jié)點呢？如果同樣“創(chuàng)造”一個結(jié)點，那是毫無意義的。解決這個問題，要從我們“沿邊走”的動機談起。我們之所以“沿邊走”，是因為我們把結(jié)點看成了狀態(tài)，把邊看成了狀態(tài)間轉(zhuǎn)移的途徑。要確定新加的邊應(yīng)連到哪個結(jié)點，就需要找我們想走到但去不存在的那個結(jié)點與已有的哪個結(jié)點是等價的。那么“等價”的標(biāo)準(zhǔn)是什么呢？我們先來解決另一個問題：定義trie樹中從根結(jié)點到某個結(jié)點的路徑上的邊上的字符連起來形成的字符串為這個結(jié)點的路徑字符串。如果一個結(jié)點的路徑字符串

5、以不良單詞結(jié)尾，那么稱這個結(jié)點為危險結(jié)點，否則稱之為安全結(jié)點。那么如何判斷某個結(jié)點是否危險呢？顯然根結(jié)點是安全結(jié)點。對于一個非根結(jié)點，它是危險結(jié)點的充要條件是：它的路徑字符串本身就是一個不良單詞，或者它的路徑字符串的后綴（一個字符串去掉第一個字符后剩下的部分叫做它的后綴）對應(yīng)的結(jié)點（一個字符串對應(yīng)的結(jié)點是指在trie圖中從根出發(fā)，依次沿該字符串的每個字符走一步所達(dá)到的結(jié)點）是危險結(jié)點。如果稱一個結(jié)點的路徑字符串的后綴對應(yīng)的結(jié)點為它的后綴結(jié)點，那么如何求任一結(jié)點的后綴結(jié)點呢？根結(jié)點的后綴結(jié)點是它本身。處于trie樹第二層的結(jié)點的后綴結(jié)點也是根結(jié)點。對于再往下的某個結(jié)點，設(shè)它的路徑字符串的最后一個

6、字符為c，那么這個結(jié)點的后綴為從它在trie樹中父結(jié)點的后綴結(jié)點出發(fā)，沿標(biāo)有c的邊走一步后到達(dá)的結(jié)點。（下文中稱從x結(jié)點出發(fā)，沿標(biāo)有字符c的邊走一步到達(dá)的結(jié)點為x的c孩子）那么，如果它的父結(jié)點的后綴結(jié)點w沒有c孩子怎么辦呢？到此，我們看到兩個問題已經(jīng)合而為一了。我們假設(shè)w有這樣一個c孩子（記作x），并且從x出發(fā)又繁衍出無數(shù)的子子孫孫。我們來判斷以x為根的子樹中的結(jié)點的危險性。顯然x本身的路徑字符串不是不良單詞，且它的子孫的路徑字符串也不是不良單詞。因此以x為根的子樹中任一結(jié)點y的危險性與y的后綴結(jié)點的危險性相同（回憶一下一個非根結(jié)點是危險結(jié)點的充要條件）。這也就是說，以x為根的子樹與以x的后綴

7、結(jié)點為根的子樹是一模一樣的。因此，我們把需要新建的從w指向x的邊直接指向x的后綴結(jié)點，即w結(jié)點的后綴結(jié)點的c孩子即可。簡言之，由于x本身的路徑字符串既不是不良單詞，又不是某個不良單詞開頭的一部分，所以它的首字母便沒有用了！在這種情況下，x結(jié)點就等價于它的后綴結(jié)點。由此我們可以把trie樹改造成一個有向圖：按層次遍歷trie樹，求出每個結(jié)點的危險性和后綴結(jié)點，并補齊由它出發(fā)的邊。危險性與后綴結(jié)點的求法在【分析】部分第6、7自然段已有說明；若當(dāng)前結(jié)點為根結(jié)點，則補充的邊應(yīng)指向本身，否則若x沒有c孩子，則新建一條這樣的邊，指向x的后綴結(jié)點的c孩子。處理某個結(jié)點的過程中需要用到深度比它小的結(jié)點的后綴結(jié)

8、點及各個孩子。由于我們按層次遍歷trie樹，這些信息都已求得。這樣由trie樹改造成的有向圖就叫做trie圖。圖2就是由圖1的trie樹改造成的trie圖。我們美好的設(shè)想終于變成了現(xiàn)實。由根結(jié)點出發(fā)，按照文本中的字符一步步走下去。若走到一個危險結(jié)點，則發(fā)現(xiàn)了一個不良單詞；若一直沒走到危險結(jié)點，則文本不含不良單詞。本題的算法還可稍加優(yōu)化。把安全結(jié)點分為兩類：如果在trie樹中由根結(jié)點到某個安全結(jié)點的路徑上沒有危險結(jié)點，那么稱這個安全結(jié)點為真安全結(jié)點，否則稱之為假安全結(jié)點。由于新建的邊的終點的深度不會大于起點的深度，因此要到達(dá)一個假安全結(jié)點，必須經(jīng)過一個危險結(jié)點。而在本題中，一旦到達(dá)一個危險結(jié)點，

9、程序就會停止，因此假安全結(jié)點是沒有用的，也就是說，在本題trie圖的構(gòu)建過程中，若發(fā)現(xiàn)一個危險結(jié)點，那么它及它的子孫的屬性都不必計算了。如果用L1、L2分別表示不良單詞和文本的總長度，用a表示字符集中字符的個數(shù)，那么trie圖的時間復(fù)雜度為O(L1a+L2)，空間復(fù)雜度為O(L1a)。二、Trie圖的活用在上面的例題中，我們在trie圖中記錄了每個結(jié)點的危險性、后綴結(jié)點，并通過按層次遍歷得到了圖中結(jié)點的一個BFS序。其實，trie圖中可以記錄的信息不止這些；得到的BFS序也并不是毫無用處。【例2】字謎（題目來源：SPOJ WPUZZLES）【題目描述】給定一個L行C列的、由大寫字母構(gòu)成的矩陣，

10、以及W個單詞。每個單詞可在矩陣中的任何位置朝著任何方向出現(xiàn)，且僅出現(xiàn)一次。編程找出每個單詞的首字母在矩陣中的位置，以及單詞的朝向?！据斎耄?biāo)準(zhǔn)輸入）】第一行為一個整數(shù)T，表示數(shù)據(jù)的組數(shù)。下面有T組數(shù)據(jù)。每組數(shù)據(jù)中：第1行為三個不超過1000的整數(shù)L、C、W。下面L行，每行C個大寫字母，表示矩陣。下面W行，每行一個單詞。【輸出（標(biāo)準(zhǔn)輸出）】對每組數(shù)據(jù)，輸出W行，每行為兩個整數(shù)和一個字母，之間用一個空格隔開。第i行的兩個整數(shù)表示第i個單詞首字母的行號和列號（從上至下依次為第0至L-1行，從左往右依次為第0至C-1列）；字母表示單詞的朝向，對應(yīng)關(guān)系如下：字母ABCDEFGH朝向上右上右右下下左下左左

11、上相鄰兩組數(shù)據(jù)的輸出之間用一個空行隔開?！緲永斎搿?4 5 4MAIGOQKRPTAREMOWERTYAKIMAIGOARMARMY【樣例輸出】2 0 B0 0 C0 1 D0 1 D【分析】本題中多模式匹配的模型是顯而易見的。由于要求的是每個單詞首字母的位置，我們在建trie圖時，把每個單詞都反過來，如單詞MAIGO變成OGIAM。對每個方向的每一串字母進(jìn)行一次多模式匹配，就可以找到所有的單詞了。在本題的trie圖中，僅僅記錄每個結(jié)點的危險性是不夠的，還要記下每個結(jié)點的危險性是由哪個單詞引起的。我們定義危險結(jié)點x的危險源：若x的路徑字符串本身就是不良單詞，那么它的危險源就是該單詞；否則x的

12、危險源就是它后綴結(jié)點的危險源。每個結(jié)點的危險源可以在后綴結(jié)點的過程中求出。那么，是不是每走到一個危險結(jié)點，便記下危險源的位置及朝向就可以了呢？不是的。比如在樣例中，當(dāng)我們沿著左上方向掃描(3,4)-(0,1)這個字符串（YMRA），到達(dá)字母A時，由于該結(jié)點的危險源是YMRA，我們便記下了ARMY的位置和朝向。但同時我們就把單詞ARM漏掉了。正確的做法是，當(dāng)遇到一個危險結(jié)點時，記下它的危險源的位置和朝向，同時繼續(xù)檢查危險源對應(yīng)結(jié)點的后綴結(jié)點，直到到達(dá)一個安全結(jié)點為止。【注】本題的字符集雖然只有26個字母，但trie圖中結(jié)點的數(shù)目可能達(dá)到1,000,000，內(nèi)存復(fù)雜度太高。這個問題留待第三部分解決

13、。通過字謎一題我們學(xué)會了如何在trie圖中記下更多的信息。下面簡述一下對BFS序的應(yīng)用。在做多模式匹配時，有時僅僅找到不良單詞是不夠的，還要統(tǒng)計出每個單詞出現(xiàn)的次數(shù)。進(jìn)行這項工作時，我們并不需要判斷每個結(jié)點的危險性，而只需累加經(jīng)過每個結(jié)點的次數(shù)。但這時有單詞對應(yīng)的結(jié)點的訪問次數(shù)并不就是這個單詞出現(xiàn)的次數(shù)，比如在圖2中，單詞a出現(xiàn)時光標(biāo)完全可能在結(jié)點ba上。因此我們自底向上地把每個結(jié)點的訪問次數(shù)加到它的后綴結(jié)點上。這樣處理之后，有單詞對應(yīng)的結(jié)點的訪問次數(shù)就代表這個單詞出現(xiàn)的次數(shù)了。上面介紹了trie圖的一些初步活用。但如果僅僅用trie圖來做多模式匹配，那就太大材小用了。下面再通過幾個例題來說明

14、trie圖的更靈活的應(yīng)用。從例1可以看到，危險結(jié)點在圖中往往是一些障礙，在許多用到trie圖的問題中，有用的結(jié)點只有真安全結(jié)點。我們把trie圖中的真安全結(jié)點以及它們之間的邊構(gòu)成的子圖叫做安全圖?！纠?】病毒（題目來源：POI #7）【題目描述】已知某些特定的01串是病毒的特征代碼。如果一個01串不含有任何病毒特征代碼，則稱它為一段安全代碼。給定病毒特征庫，判斷是否存在無限長的安全代碼?！据斎耄ㄎ募ir.in）】第一行為一個整數(shù)n，表示病毒特征代碼的條數(shù)。下面n行，每行一段病毒特征代碼。所有代碼長度之和不超過30000。【輸出（文件wir.out）】若存在無限長的安全代碼，輸出一行“TAK”

15、，否則輸出一行“NIE”?！緲永斎搿?011100000【樣例輸出】NIE【分析】“無限長”的安全代碼是什么意思呢？就是說從根結(jié)點出發(fā)，在安全圖中可以走無限步?！盁o限步”又是什么意思呢？就是說安全圖中有環(huán)。因此我們建立一個trie圖并對其安全圖進(jìn)行拓?fù)渑判颍舫晒?，則安全圖無環(huán)，輸出“NIE”，否則輸出“TAK”。【例4】Censored!（題目來源：Ural 1158）【題目描述】已知一個由n(1<=n<=50)個字符組成的字符集及p(0<=p<=10)個不良單詞（長度均不超過10），求長度為m(1<=m<=50)且不含不良單詞的字符串的數(shù)目?！据斎耄?biāo)

16、準(zhǔn)輸入）】第一行為三個整數(shù)n,m,p。第二行為n個字符，表示字符集。下面p行，每行一個不良單詞?！据敵觯?biāo)準(zhǔn)輸出）】一個整數(shù)，表示長度為m且不含不良單詞的字符串的數(shù)目。【樣例輸入】3 3 3QWEQQWEEQ【樣例輸出】7【分析】求長度為m且不含不良單詞的字符串的數(shù)目，就是求在安全圖中從根結(jié)點出發(fā)走m步有多少種走法。用countstep,x表示從根結(jié)點出發(fā)走step步到結(jié)點x的走法數(shù)，則容易寫出下面的偽代碼：fillchar(count,sizeof(count),0);count0,根:=1;for step:=1 to m dofor 安全圖中每條邊(i,j) do inc(countst

17、ep,j,countstep-1,i);ans:=0;for 安全圖中每個結(jié)點x doinc(ans,countm,x);顯然，本題還需要用高精度。我們看到，trie圖的安全圖上還是大有文章可做的。Trie圖（或其安全圖）作為一個有向圖，它具有一般有向圖具有的性質(zhì)，因此在它上面可以進(jìn)行拓?fù)渑判?。同樣，它的有向性也可以成為動態(tài)規(guī)劃劃分階段的依據(jù)。三、Trie圖的改進(jìn)Trie圖的空間復(fù)雜度是比較高的，當(dāng)trie圖中結(jié)點個數(shù)較多或字符集較大時，內(nèi)存根本無法承受。下面探討這個問題的解決方法?！纠?】不良單詞過濾器（題目來源：Ural 1269）【題目描述】給出一個詞典，其中的單詞為不良單詞。再給出一段

18、文本，文本的每一行可能包含除chr(0),chr(10),chr(13)外的任何字符。若文本中有不良單詞，找出文本中不良單詞第一次出現(xiàn)的位置，若沒有，輸出一行“Passed”?！据斎耄?biāo)準(zhǔn)輸入）】第一行為一個整數(shù)n(1<=n<=10000)，表示不良單詞的個數(shù)。接下來n行是詞典。詞典的大小不超過100KB，每個不良單詞的長度不超過10000。下面一行為一個整數(shù)m，表示文本的行數(shù)。接下來m行是文本。文本的大小不超過900KB?！据敵觯?biāo)準(zhǔn)輸出）】若文本中有不良單詞，輸出一行兩個整數(shù)，表示不良單詞第一次出現(xiàn)的行和列，用一個空格隔開。若文本中無不良單詞，輸入一行“Passed”?！緲永?/p>

19、入】2robProblem1Internet Problem Solving Contest【樣例輸出】1 10【注意】樣例中“第一次出現(xiàn)”的不良單詞是Problem而不是rob，雖然rob比Problem先結(jié)束?！緯r間限制】1s?！緝?nèi)存限制】5000KB?！痉治觥空б豢矗@道題與例1不是一模一樣的嗎？其實不然。與例1相比，這道題的字符集大得多，如果直接建trie圖，從每個結(jié)點出發(fā)要建253條邊，而結(jié)點數(shù)最多為100000，嚴(yán)重超內(nèi)存。試想一下，如果要做一個漢字的多模式匹配系統(tǒng)，豈不是要從每個結(jié)點出發(fā)建幾千幾萬條邊呢？所以，為解決此問題，trie圖的改進(jìn)勢在必行。我們看到，在本題中，算法的瓶頸

20、在于從每個結(jié)點出發(fā)的邊數(shù)。那么我們自然會想到：一定要存儲所有的邊嗎？答案是否定的。Trie樹中的邊自然是要存儲的（用左孩子右兄弟表示法），但新建的邊則不必存儲。如果不存儲新建的邊，那么如何實現(xiàn)狀態(tài)間的轉(zhuǎn)移呢？我們用一個函數(shù)child(x,c)來獲得結(jié)點x的c孩子。函數(shù)內(nèi)部的程序其實完全是按照加邊的原則編寫的：如果x本來就有c孩子，那么就返回這個孩子；如果x沒有c孩子，根據(jù)加邊的原則，函數(shù)應(yīng)該返回x的后綴結(jié)點的c孩子，也就是令x為它的后綴結(jié)點，重新執(zhí)行函數(shù)。如果x變成了根結(jié)點仍然沒有c孩子，同樣根據(jù)加邊的原則，函數(shù)的返回值就應(yīng)該是根結(jié)點本身。經(jīng)過這樣的處理，算法的空間復(fù)雜度由O(L1a)降到了O

21、(L1)，對于本題來說是足夠低的了。但是，由于child函數(shù)的執(zhí)行時間的不確定性，我們對算法的時間復(fù)雜度產(chǎn)生了疑問。其實，算法的時間復(fù)雜度為O(L1+L2)，數(shù)量級并沒有受到影響，只是增加了一點常數(shù)系數(shù)。為什么呢？顯然，在調(diào)用child(x,c)的時候，只有當(dāng)x沒有c孩子，需要重復(fù)執(zhí)行child函數(shù)時運行時間才會增加。我們分別討論增加的這點時間對建圖過程和文本檢查過程所需時間的影響：² 建圖過程：由于我們并不存儲一個結(jié)點的所有孩子指針，所以建圖的過程其實就是求每個結(jié)點的后綴結(jié)點的過程。若b是trie樹中a結(jié)點的一個孩子，那么b的后綴結(jié)點的深度至多比a的后綴結(jié)點大1。如果把trie樹中某條路徑上的結(jié)點的后綴結(jié)點的深度排成一個數(shù)列，那么相鄰兩項中，后一項減一項的差一定小于等于1。當(dāng)后一項減前一項的差小于1