算法合集之trie圖的構(gòu)建、活用與改進(jìn)(已修改)
2024-09-09 15:51 本頁(yè)面
【正文】 2006年全國(guó)信息學(xué)冬令營(yíng)講座Trie圖的構(gòu)建、活用與改進(jìn) Maigo 我們知道trie樹(shù)（也叫字母樹(shù)）這種數(shù)據(jù)結(jié)構(gòu)。它是詞典的一種存儲(chǔ)方式。詞典中的每一個(gè)單詞在trie樹(shù)中表現(xiàn)為一條從根結(jié)點(diǎn)出發(fā)的路徑，路徑中邊上的字母連起來(lái)就形成對(duì)應(yīng)的單詞。圖1就是一棵trie樹(shù)，其中含有a,abc,bac,bbc,ca五個(gè)單詞。利用trie樹(shù)可以對(duì)詞典中的單詞進(jìn)行一些適合用樹(shù)這種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的操作，如求兩個(gè)單詞的公共前綴長(zhǎng)度（在樹(shù)中表現(xiàn)為求兩個(gè)單詞對(duì)應(yīng)結(jié)點(diǎn)的最近公共祖先）。其實(shí)，如果把trie樹(shù)加以改造，多連一些邊，形成的trie圖在解決多模式串匹配問(wèn)題上會(huì)發(fā)揮奇效。左：圖1，一棵含有五個(gè)單詞的trie樹(shù)。紅色表示單詞終止的位置。 右：圖2，由圖1的trie樹(shù)改造成的trie圖。紅色表示危險(xiǎn)結(jié)點(diǎn)，白色表示真安全結(jié)點(diǎn)，藍(lán)色表示新加的邊。為簡(jiǎn)單起見(jiàn)，危險(xiǎn)結(jié)點(diǎn)以下的結(jié)點(diǎn)及與之關(guān)聯(lián)的邊沒(méi)有畫(huà)出。一、Trie圖的構(gòu)建我們通過(guò)一個(gè)例題來(lái)探究trie圖的構(gòu)建方法?！纠?】不良單詞探測(cè)器【題目描述】給出一個(gè)詞典，其中的單詞為不良單詞。單詞均為小寫字母。再給出一段文本，文本的每一行也由小寫字母構(gòu)成。判斷文本中是否含有任何不良單詞。例如，若rob是不良單詞，那么文本problem含有不良單詞。【輸入】第一行為一個(gè)整數(shù)n，表示不良單詞的個(gè)數(shù)。接下來(lái)n行是詞典。下面一行為一個(gè)整數(shù)m，表示文本的行數(shù)。接下來(lái)m行是文本?！据敵觥咳绻谋景涣紗卧~，輸出一行“Yes”，否則輸出一行“No”?！緲永斎搿?rob1internetproblemsolvingcontest【樣例輸出】Yes【備注】因本題只是用來(lái)討論trie圖的構(gòu)建方法，故未給出數(shù)據(jù)范圍。【分析】判斷文本是否包含不良單詞可以一行一行地判斷。而判斷長(zhǎng)為L(zhǎng)的一行文本s是否含有不良單詞可以這樣進(jìn)行：讓i從1變化到L，依次判斷s的前i個(gè)字符構(gòu)成的字符串是否以不良單詞結(jié)尾。然而，我們希望在判斷s的前k個(gè)字符時(shí)，能夠利用前k1個(gè)字符的結(jié)果，即這兩個(gè)狀態(tài)間可以方便地進(jìn)行轉(zhuǎn)移。注意到trie樹(shù)中的邊正如一個(gè)個(gè)“方向標(biāo)”，因此我們有了一個(gè)美好的設(shè)想：從根結(jié)點(diǎn)出發(fā)，沿著標(biāo)有s[1]的邊走一步，再沿標(biāo)有s[2]的邊走一步，一直這樣走下去！現(xiàn)在有了一個(gè)問(wèn)題：如果從當(dāng)前走到的結(jié)點(diǎn)出發(fā)，沒(méi)有需要走的邊，該怎么辦？只要“創(chuàng)造”一條這樣的邊即可。那么這條邊應(yīng)該指向哪個(gè)結(jié)點(diǎn)呢？如果同樣“創(chuàng)造”一個(gè)結(jié)點(diǎn)，那是毫無(wú)意義的。解決這個(gè)問(wèn)題，要從我們“沿邊走”的動(dòng)機(jī)談起。我們之所以“沿邊走”，是因?yàn)槲覀儼呀Y(jié)點(diǎn)看成了狀態(tài)，把邊看成了狀態(tài)間轉(zhuǎn)移的途徑。要確定新加的邊應(yīng)連到哪個(gè)結(jié)點(diǎn)，就需要找我們想走到但去不存在的那個(gè)結(jié)點(diǎn)與已有的哪個(gè)結(jié)點(diǎn)是等價(jià)的。那么“等價(jià)”的標(biāo)準(zhǔn)是什么呢？我們先來(lái)解決另一個(gè)問(wèn)題：定義trie樹(shù)中從根結(jié)點(diǎn)到某個(gè)結(jié)點(diǎn)的路徑上的邊上的字符連起來(lái)形成的字符串為這個(gè)結(jié)點(diǎn)的路徑字符串。如果一個(gè)結(jié)點(diǎn)的路徑字符串以不良單詞結(jié)尾，那么稱這個(gè)結(jié)點(diǎn)為危險(xiǎn)結(jié)點(diǎn)，否則稱之為安全結(jié)點(diǎn)。那么如何判斷某個(gè)結(jié)點(diǎn)是否危險(xiǎn)呢？顯然根結(jié)點(diǎn)是安全結(jié)點(diǎn)。對(duì)于一個(gè)非根結(jié)點(diǎn)，它是危險(xiǎn)結(jié)點(diǎn)的充要條件是：它的路徑字符串本身就是一個(gè)不良單詞，或者它的路徑字符串的后綴（一個(gè)字符串去掉第一個(gè)字符后剩下的部分叫做它的后綴）對(duì)應(yīng)的結(jié)點(diǎn)（一個(gè)字符串對(duì)應(yīng)的結(jié)點(diǎn)是指在trie圖中從根出發(fā)，依次沿該字符串的每個(gè)字符走一步所達(dá)到的結(jié)
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1