[[408420]]

本文轉(zhuǎn)載自微信公眾號(hào)「帥地玩編程」，作者帥地。轉(zhuǎn)載本文請(qǐng)聯(lián)系帥地玩編程公眾號(hào)。

Trie 樹(shù)大家了解一下原理和應(yīng)用即可，有時(shí)候面試的時(shí)候會(huì)問(wèn)到，下面我用面試的情景跟大家講解 trie 樹(shù)。

面試官：玩過(guò)王者榮耀吧?了解過(guò)敏感詞過(guò)濾嗎?，例如在游戲里，如果我們發(fā)送“你在干嘛?麻痹演員啊你?”，由于“麻痹”是一個(gè)敏感詞，所以當(dāng)你把聊天發(fā)出來(lái)之后，我們會(huì)用“**”來(lái)代表“麻痹”這次詞，所以發(fā)送出來(lái)的聊天會(huì)變成這樣：“你在干嘛?**演員啊你?”。

小秋：聽(tīng)說(shuō)過(guò)啊，在各大社區(qū)也經(jīng)?？吹?，例如評(píng)論一個(gè)問(wèn)題等，一些粗話經(jīng)常被過(guò)濾掉了。

面試官：嗯，如果我給你一段文字，以及給你一些需要過(guò)濾的敏感詞，你會(huì)怎么來(lái)實(shí)現(xiàn)這個(gè)敏感詞過(guò)濾的算法呢?例如我給你一段字符串“abcdefghi",以及三個(gè)敏感詞"de", "bca", "bcf"。

小秋：(敏感詞過(guò)來(lái)算法??不就是字符串匹配嗎?)我可以通過(guò)字符串匹配算法，例如在字符串”abcdefghi"在查找是否存在字串“de"，如果找到了就把”de“用"**"代替。通過(guò)三次匹配之后，接變成這樣了：“abc ** fghi"。

面試官：可以說(shuō)說(shuō)你采用哪種字符串匹配算法嗎?

小秋：最簡(jiǎn)單的方法就是采用兩個(gè)for循環(huán)保留求解了，不過(guò)每次匹配的都時(shí)間復(fù)雜度為O(n*m)，我可以采用 KMP 字符串匹配算法，這樣時(shí)間復(fù)雜度是 O(m+n)。

n 表示字符串的長(zhǎng)度，m 表示每個(gè)敏感詞的長(zhǎng)度。

面試官：這是一個(gè)方法，對(duì)于敏感詞過(guò)濾，你還有其他方法嗎?

小秋：(其他方法?說(shuō)實(shí)話，我也覺(jué)得不是采用這種 KMP 算法來(lái)匹配的了，可是，之前也沒(méi)去了解過(guò)敏感詞，這下要涼)對(duì)敏感詞過(guò)來(lái)之前也沒(méi)了解過(guò)，暫時(shí)沒(méi)想到其他方法。

trie 樹(shù)

面試官：了解過(guò) trie 樹(shù)嗎?

小秋：(嘿嘿，數(shù)據(jù)結(jié)構(gòu)這方法，我得爭(zhēng)氣點(diǎn))了解過(guò)，我還用代碼實(shí)現(xiàn)過(guò)。

面試官：可以說(shuō)說(shuō)它的特點(diǎn)嗎?

小秋：trie 樹(shù)也稱為字典樹(shù)、單詞查找樹(shù)，最大的特點(diǎn)就是共享字符串的公共前綴來(lái)達(dá)到節(jié)省空間的目的了。例如，字符串 "abc"和"abd"構(gòu)成的 trie 樹(shù)如下：

trie 樹(shù)的根節(jié)點(diǎn)不存任何數(shù)據(jù)，每整個(gè)個(gè)分支代表一個(gè)完整的字符串。像 abc 和 abd 有公共前綴 ab，所以我們可以共享節(jié)點(diǎn) ab。如果再插入 abf，則變成這樣：

如果我再插入 bc，則是這樣(bc 和其他三個(gè)字符串沒(méi)有公共前綴)。

面試官：那如果再插入 "ab" 這個(gè)字符串呢?

小秋：差點(diǎn)說(shuō)了，每個(gè)分支的內(nèi)部可能也含有完整的字符串，所以我們可以對(duì)于那些是某個(gè)字符串結(jié)尾的節(jié)點(diǎn)做一個(gè)標(biāo)記，例如 abc, abd,abf 都包含了字符串 ab,所以我們可以在節(jié)點(diǎn) b 這里做一個(gè)標(biāo)記。如下(我用紅色作為標(biāo)記)：

面試官：可以說(shuō)說(shuō) trie 樹(shù)有哪些應(yīng)用嗎?

小秋：trie 最大的特點(diǎn)就是利用了字符串的公共前綴，像我們有時(shí)候在百度、谷歌輸入某個(gè)關(guān)鍵字的時(shí)候，它會(huì)給我們列舉出很多相關(guān)的信息

這種就是通過(guò) trie 樹(shù)來(lái)實(shí)現(xiàn)的。

小秋：(嗯?trie 又稱為單詞查找樹(shù)，好像可以用 trie 來(lái)實(shí)現(xiàn)剛才的敏感詞匹配?面試官無(wú)緣無(wú)故提 trie 樹(shù)難道別有用意?)

面試官：剛才的敏感詞過(guò)濾，其實(shí)也可以采用 trie 來(lái)實(shí)現(xiàn)，你知道怎么實(shí)現(xiàn)嗎?

trie 樹(shù)來(lái)實(shí)現(xiàn)敏感詞過(guò)濾

小秋：(果然，面試官真是個(gè)好人啊，直接提示了，要是還不知道怎么實(shí)現(xiàn)，那不真涼?)我想想……..我知道了，

我可以這樣來(lái)實(shí)現(xiàn)：

先把你給我的三個(gè)敏感詞："de", "bca", "bcf" 建立一顆 trie 樹(shù)，如下：

接著我們可以采用三個(gè)指針來(lái)遍歷，我直接用上面你給你例子來(lái)演示吧。

1、首先指針 p1 指向 root，指針 p2 和 p3 指向字符串第一個(gè)字符

2、然后從字符串的 a 開(kāi)始，檢測(cè)有沒(méi)有以 a 作為前綴的敏感詞，直接判斷 p1 的孩子節(jié)點(diǎn)中是否有 a 這個(gè)節(jié)點(diǎn)就可以了，顯然這里沒(méi)有。接著把指針 p2 和 p3 向右移動(dòng)一格。

3、然后從字符串 b 開(kāi)始查找，看看是否有以 b 作為前綴的字符串，p1 的孩子節(jié)點(diǎn)中有 b，這時(shí)，我們把 p1 指向節(jié)點(diǎn) b，p2 向右移動(dòng)一格，不過(guò)，p3不動(dòng)。

4、判斷 p1 的孩子節(jié)點(diǎn)中是否存在 p2 指向的字符c，顯然有。我們把 p1 指向節(jié)點(diǎn) c，p2 向右移動(dòng)一格，p3不動(dòng)。

5、判斷 p1 的孩子節(jié)點(diǎn)中是否存在 p2 指向的字符d，這里沒(méi)有。這意味著，不存在以字符b作為前綴的敏感詞。這時(shí)我們把p2和p3都移向字符c，p1 還是還原到最開(kāi)始指向 root。

6、和前面的步驟一樣，判斷有沒(méi)以 c 作為前綴的字符串，顯然這里沒(méi)有，所以把 p2 和 p3 移到字符 d。

7、然后從字符串 d 開(kāi)始查找，看看是否有以 d 作為前綴的字符串，p1 的孩子節(jié)點(diǎn)中有 d，這時(shí)，我們把 p1 指向節(jié)點(diǎn) d，p2 向右移動(dòng)一格，不過(guò)，p3和剛才一樣不動(dòng)。(看到這里，我猜你已經(jīng)懂了)

8、判斷 p1 的孩子節(jié)點(diǎn)中是否存在 p2 指向的字符e，顯然有。我們把 p1 指向節(jié)點(diǎn) e，并且，這里e是最后一個(gè)節(jié)點(diǎn)了，查找結(jié)束，所以存在敏感詞de，即 p3 和 p2 這個(gè)區(qū)間指向的就是敏感詞了，把 p2 和 p3 指向的區(qū)間那些字符替換成 *。并且把 p2 和 p3 移向字符 f。如下：

9、接著還是重復(fù)同樣的步驟，知道 p3 指向最后一個(gè)字符。

復(fù)雜度分析

面試官：可以說(shuō)說(shuō)時(shí)間復(fù)雜度嗎?

小秋：如果敏感詞的長(zhǎng)度為 m，則每個(gè)敏感詞的查找時(shí)間復(fù)雜度是 O(m)，字符串的長(zhǎng)度為 n，我們需要遍歷 n 遍，所以敏感詞查找這個(gè)過(guò)程的時(shí)間復(fù)雜度是 O(n * m)。如果有 t 個(gè)敏感詞的話，構(gòu)建 trie 樹(shù)的時(shí)間復(fù)雜度是 O(t * m)。

這里我說(shuō)明一下，在實(shí)際的應(yīng)用中，構(gòu)建 trie 樹(shù)的時(shí)間復(fù)雜度我覺(jué)得可以忽略，因?yàn)?trie 樹(shù)我們可以在一開(kāi)始就構(gòu)建了，以后可以無(wú)數(shù)次重復(fù)利用的了。而剛才的 kmp 算法時(shí)間復(fù)雜度是 t *(m+n)，不過(guò)kmp需要維護(hù) next 數(shù)組比較費(fèi)空間，而且在實(shí)際情況中,敏感詞的數(shù)量 t 是比較大，而 n 反而比較小的吧。

10、如果讓你來(lái) 構(gòu)建 trie 樹(shù)，你會(huì)用什么數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)?

小秋：我一般使用 Java，我會(huì)采用 HashMap 來(lái)實(shí)現(xiàn)，因?yàn)橐粋€(gè)節(jié)點(diǎn)的字節(jié)點(diǎn)個(gè)數(shù)未知，采用 HashMap 可以動(dòng)態(tài)拓展，而且可以在 O(1) 復(fù)雜度內(nèi)判斷某個(gè)子節(jié)點(diǎn)是否存在。

面試官：嗯，回去等通知吧。

總結(jié)

今天主要將了 trie 樹(shù)以及 trie 樹(shù)的一些應(yīng)用，還要就是如何通過(guò) trie 樹(shù)來(lái)實(shí)現(xiàn)敏感詞的過(guò)濾，至于代碼的實(shí)現(xiàn)，我這里就不給出了，在實(shí)現(xiàn)的時(shí)候，為了防止這種”麻 痹"或者“麻￥痹”等，我們也要對(duì)特殊字符進(jìn)行過(guò)濾等，有興趣的可以去實(shí)現(xiàn)一波。