一道bat面試題：快速替換10億條標題中的5萬個敏感詞，有哪些解決思路？

01-15

有十億個標題，存在一個文件中，一行一個標題。有5萬個敏感詞，存在另一個文件。寫一個程序過濾掉所有標題中的所有敏感詞，保存到另一個文件中。
優化方向先不考慮並行處理，因為並行本質上沒有降低時間複雜度。
常規解法是分批讀取標題，然後一行行匹配並替換，這樣的時間複雜度是：O（標題行數*敏感詞行數*（一行標題的長度+一個敏感詞的長度））

面試官說這樣的時間複雜度太大，有更好的解決辦法嗎？他給的提示是先對敏感詞建一棵樹

謝邀。

把所有敏感詞建立一個 AC 自動機，然後每行標題都在自動機上跑一遍就行了。

顯然，字典樹是不行的，因為有可能敏感詞在標題的中間部分出現。

Aho-Corasick演算法，利用Trie樹構造狀態機，專門解決關鍵詞匹配問題。

Aho-Corasick algorithm

時間複雜度最優的肯定是把敏感詞建一個AC自動機，然後在AC自動機上查就行了。

但是如果怕空間爆炸，可以看一下這個：http://blog.csdn.net/creationaugust/article/details/51203474

不過我最好奇的是，用bat怎麼寫複雜數據結構？

這個看一下grep用的是啥不就得了

http://git.savannah.gnu.org/cgit/grep.git/tree/src/kwset.c

看了好多大牛的回答，受益匪淺，下面我來說一下我的看法，剛看數據結構沒幾周，有什麼常識性問題在所難免，請大家多多包涵。

首先，如果沒有任何提示的情況下，我們只能假定5萬條敏感詞的數據特徵如下：

預：10億條標題每條標題長度為Nmin到Nmax之間

1.敏感詞的長度為1位到Nmax之間都有

2.由於BAT通用語言為漢字，所以敏感詞字符集為Unicode中的漢字全集Ncn+通用字元Nasc全集，數量為Nall=Ncn+Nasc

下面來對需求進行一下進一步分析

題目最迫切需要的並不是讓演算法從10e條進行匹配而是每次給你一個新的標題讓你快速匹配出來。而每天都有無上限的數量級的新標題讓你匹配。這是實際應用。當然也不排除敏感詞庫更新，10e重新遍歷，你早就發出去的內容今天被判定為敏感話題的可能，但如果出現這個更新的需求的話，我們只需要對更新後的數量為Nfew個敏感詞進行匹配就行了，無需對其餘5萬條敏感詞重新匹配一遍。

其次，如果長短關鍵詞都匹配到了，關鍵詞是需要長關鍵詞優先的。但這會增大演算法難度，而如果把短關鍵詞屏蔽掉的了，而實際應用還是能看出來長關鍵詞的含義的話那就再想辦法。暫時以短關鍵詞優先的法則進行模型建立。

現在開始考慮演算法模型：

先說一下AC自動機的優缺點。首先這裡面的失敗索引的線索樹非常有用，可以避免浪費時間在無謂的重複。但是這個樹的數量級太大了，我們沒有理由說有誰家的系統可以滿足(2Nall)^Nmax位元組的內存空間，帶進去幾個可能值看一下，取Nall=10000，Nmax=6，結果為6.4E10GB的空間複雜度必然不可行。如果不做任何哈希函數的話，輕輕鬆鬆內存報表。但是如果你的哈希函數優化的不夠好，即便把Nhash降低到了1000，也有64TB的空間複雜度，這還沒算哈系衝突，當然哈希衝突隊列長度遠遠小於Nhash，但這個數值應該也會對整體空間複雜度產生比較大的影響的。

於是這個問題的重點就轉移到了哈希函數的構造上來了。而分析一下我們就發現，哈希函數的優化真是so easy

我們看一下敏感詞，舉幾個例子。

我還是隨便編幾個吧。

DLP

KJL

KLP

MPC

OLP

然後就可以列出來一個字典樹

然後我們可以得出這麼一個結論

第一層哈希，我們有DKLMO多種選擇，如果放在實際應用里，這一層哈希將是非常龐大的一個空間。

第二層哈系，我們有MJLPE多種選擇，實際上可能例子太小，反應不了太多的情況，按照常理，這一層哈系空間佔用也會很大，但是受到第一層的限制導致第二層的空間將少很多。

第三層哈系，我們有PLC三種選擇，也就是說，層數越多，關鍵詞長度能達到這一層的也就越少，哈希表空間佔用將會越小，並且這個減小方式是呈幾何級數的減小的。

假設關鍵詞最大有N個字(N字關鍵詞&>1,N+1字的關鍵詞只有1個或0個)，假定每層數量遞減率相同，那麼，第一層哈系將佔用假設3000空間（肯定有哈希衝突，一會兒再說），第二層將佔用3000*k，0&將這N個字的空間相乘，空間複雜度將只有O(3000^N*k^(N/2)),條件太多，不好模擬這個數值的大小，但這將遠遠小於O(3000^N)。在該空間複雜度下，如果還不滿足要求，繼續優化參數即可，不過必然會犧牲性能，但相比空間複雜度太大壓根兒無從入手的情況，犧牲時間複雜度又有何妨？下面就開始分析一下如何優化每一層哈系所佔用的空間。

如果脫離了5萬敏感詞，下面的分析將無從談起。所以，假定我們分析了5萬關鍵詞，得出字典樹的每一層哈系的各個字元出現的分布律如下

第一層：

A:0.15

B:0.10

C:0.05

D:0.02

....

第二層：

C:0.20

B:0.15

D:0.10

M:0.05

...

第三層：

。。。

然後就是開始建模，分別建立每一層的哈系函數，使得哈希函數最終能達到如下幾個目的：

1.該層哈系表佔用的空間儘可能小

2.高頻字元不要衝突，比如第一層的A和B不要命中在一起。否則時間複雜度將受很多大影響。

3.低頻字元隨便衝突。如果幾個幾乎不怎麼出現的關鍵字命中在一個哈希值，那就把隊列遍歷一下不就OK了。本身低頻，這個時間複雜度並不會特別高。即便出現太多次衝突，總體時間複雜度和空間複雜度也是可以求出來最和諧的方案的。

4.哈希函數盡量採用初等機器運算，比如位運算等，撒個種子，做個位與，等等，具體怎麼做，實踐決定一切。

由於每層的字元結構不同，因此每層產生的哈希函數應該不一樣才對。

哈希函數的產生也是一個大工程。但是如果產生了足夠好的哈希函數，這對於每天上億條的信息處理來說也是利大於弊的。

可以採用求出來一系列哈希函數的方法，然後對每一種方法的實際檢驗的結果做一下評估，比如有的效率高，有的效率低，如果採用種子作為初始條件，不同的種子也將產生不同的效率，可以自己執行一個標準，有的演算法評分可以達到47分，有的只有60分，那就啟用60分的，如果有大牛製作出更高效的80分的哈希函數那就更好。這個問題就開放了。

最後，為了滿足實際需要，每天人們提交的信息也是動態的，關鍵詞分布律受到輿情的影響也很嚴重，因此這個演算法如果繼續鑽牛角尖的話，哈希函數還是要根據實際情況每隔一段時間更新一下比較好。

拋個磚，寫個思路，權當樂呵

顯然，需要替換的詞相對所有詞來說是少了幾個數量級，所以我的思路是要用盡量少的時間複雜度定位敏感詞。

首先考慮hash表，但是按敏感詞字典有10萬算，32bit的地址佔4M byte，考慮1倍餘量要8M，而且還要考慮碰撞，並且可能不能完全利用cpu的cache。

其次，猜測敏感詞不會太長，如果最長的詞有4個字，則建立4個長度分別為1，2，3，4的敏感詞的bloom filter，然後走4輪就能找出所有『』疑似敏感詞『』，簡直不要太完美了。疑似敏感詞通過敏感片語成的hash表或是字典樹，就可以搞定了。

分析一下時間複雜度：

10億*4+5萬疑似敏感詞*log(10萬敏感詞，字典)，大概40億+30萬，妥妥的

乍一看多模式匹配演算法。

AC自動機。

ac自動機，，在字典樹上跑kmp。。。

還BAT的面試題，你就直說是那個B不行嗎

這個題目其實這些一億條標題，五萬個敏感詞都是唬人的，就是想考你，給你一個敏感詞表，然後從一個文本中找出是否有敏感詞，至於替換是順手的事情，標題數量多也是要一個個做。核心就是根據敏感詞表建一個樹可以快速的判斷字元串是否有敏感詞。這一般是bat這種公司過濾敏感詞的一個功能，這其實考不了啥的，沒做過的話一下怎麼想的到

toolgood/ToolGood.Words

Aho-Corasick演算法（個人認為是BFS演算法）

.Net實現，優化演算法，效率很高。

直觀來看，AC演算法就是這個題目的考察點。

如果考慮到敏感字會追加，標題會追加，就有些意思了。

要做快速匹配，參考rsync的循環快速校驗演算法。

敏感詞5萬個可以用循環校驗和crc為key，建立bitmap或者hashmap，查詢時間為O(1)。

敏感詞肯定有個長度限制，設為m，比如長度範圍為2-128，建立一個循環校驗數組。

對每行從第一個字元掃描，計算循環校驗和，然後查找是否存在於hashmap中，存在則進一步kmp或其他演算法匹配。假設每行長度為k，演算法複雜度為O(km)。

假設有n行，則總複雜度為O(nkm)。空間複雜度為詞庫數。

直接用字元串做hash不好，字元串的equals會比較慢，要用hashcode，但詞庫變長，hashcode會存在很多重複計算，所以要用循環crc。

5萬個敏感詞，想辦法構造出一個正則表達式就可以大大提高速度了。

正則表達式本質上和DFA是等價的，可能就是他們所說的AC自動機。只是這個東西該怎麼構造，得好好想想。

好像能搜到一些正則表達式自動生成的工具的，看看塞進去五萬個敏感詞會發生什麼情況。

先看看敏感詞表的特點，如果大部分敏感詞處於2到3字的長度，直接用hash表做，每次遍歷標題查找是否在hash表中。對於部分長度超過3個字的，每次遇到做些額外匹配就行。

@Barty 回答下面的評論比答主明白

cat bigfile | grep - f pattern.txt

敏感詞建樹是什麼鬼？要不題主是記錯了，要不面試官是個半瓶子水。@Barty 自動機是正解，自動機對付很多計算機問題真乃神器。

這個面試題很不道德，應該拒絕回答。