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

1、Trie圖的構(gòu)建、活用與改進(jìn) Maigo 200我們知道trie樹（也叫字母樹）這種數(shù)據(jù)結(jié)構(gòu)。它是詞典的一種存儲方式。詞典中的每一個單詞在trie樹中表現(xiàn)為一條從根結(jié)點(diǎn)出發(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é)點(diǎn)的最近公共祖先）。其實(shí)，如果把trie樹加以改造，多連一些邊，形成的trie圖在解決多模式串匹配問題上會發(fā)揮奇效。左：圖1，一棵含有五個單詞的trie樹。紅色表示單詞終止的位置

2、。右：圖2，由圖1的trie樹改造成的trie圖。紅色表示危險結(jié)點(diǎn)，白色表示真安全結(jié)點(diǎn)，藍(lán)色表示新加的邊。為簡單起見，危險結(jié)點(diǎn)以下的結(jié)點(diǎn)及與之關(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”?！緲永斎搿?rob1internetproblemsolvingcontest【樣例輸出】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é)點(diǎn)出發(fā)，沿著標(biāo)有s1的邊走一步，

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

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

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

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

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

9、程序就會停止，因此假安全結(jié)點(diǎn)是沒有用的，也就是說，在本題trie圖的構(gòu)建過程中，若發(fā)現(xiàn)一個危險結(jié)點(diǎn)，那么它及它的子孫的屬性都不必計(jì)算了。如果用L1、L2分別表示不良單詞和文本的總長度，用a表示字符集中字符的個數(shù)，那么trie圖的時間復(fù)雜度為O(L1a+L2)，空間復(fù)雜度為O(L1a)。二、Trie圖的活用在上面的例題中，我們在trie圖中記錄了每個結(jié)點(diǎn)的危險性、后綴結(jié)點(diǎn)，并通過按層次遍歷得到了圖中結(jié)點(diǎn)的一個BFS序。其實(shí)，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é)點(diǎn)的危險性是不夠的，還要記下每個結(jié)點(diǎn)的危險性是由哪個單詞引起的。我們定義危險結(jié)點(diǎn)x的危險源：若x的路徑字符串本身就是不良單詞，那么它的危險源就是該單詞；否則x的

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

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

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

15、，否則輸出一行“NIE”?！緲永斎搿?011100000【樣例輸出】NIE【分析】“無限長”的安全代碼是什么意思呢？就是說從根結(jié)點(diǎn)出發(fā)，在安全圖中可以走無限步。“無限步”又是什么意思呢？就是說安全圖中有環(huán)。因此我們建立一個trie圖并對其安全圖進(jìn)行拓?fù)渑判?，若成功，則安全圖無環(huán)，輸出“NIE”，否則輸出“TAK”?！纠?】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 3QWEQQWEEQ【樣例輸出】7【分析】求長度為m且不含不良單詞的字符串的數(shù)目，就是求在安全圖中從根結(jié)點(diǎn)出發(fā)走m步有多少種走法。用countstep,x表示從根結(jié)點(diǎn)出發(fā)走step步到結(jié)點(diǎn)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é)點(diǎn)x doinc(ans,countm,x);顯然，本題還需要用高精度。我們看到，trie圖的安全圖上還是大有文章可做的。Trie圖（或其安全圖）作為一個有向圖，它具有一般有向圖具有的性質(zhì)，因此在它上面可以進(jìn)行拓?fù)渑判颉Ｍ瑯?，它的有向性也可以成為動態(tài)規(guī)劃劃分階段的依據(jù)。三、Trie圖的改進(jìn)Trie圖的空間復(fù)雜度是比較高的，當(dāng)trie圖中結(jié)點(diǎn)個數(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不是一模一樣的嗎？其實(shí)不然。與例1相比，這道題的字符集大得多，如果直接建trie圖，從每個結(jié)點(diǎn)出發(fā)要建253條邊，而結(jié)點(diǎn)數(shù)最多為100000，嚴(yán)重超內(nèi)存。試想一下，如果要做一個漢字的多模式匹配系統(tǒng)，豈不是要從每個結(jié)點(diǎn)出發(fā)建幾千幾萬條邊呢？所以，為解決此問題，trie圖的改進(jìn)勢在必行。我們看到，在本題中，算法的瓶頸

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

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