1樓：Sails
每天一百萬篇文章，每篇文章一百萬字，換算成流量也不足100Mbps，十萬關鍵字，一台筆記本就能搞定的需求吧。
用正規表示式吧，關鍵字全相容。
2樓：iammutex
由於敏感詞範圍有限，可以按位元組將所有詞分成N段。每位元組共256種可能，維護一棵trie樹，節點為256個指標。每個指標標識一位元組，（比如第3個指標表示0x03這個字元）。
所以乙個M個位元組的詞被切成M份，為trie樹中從根節點到第M層的一條鏈路。將所有待過濾詞全部輸入後，就能形成一棵查詢trie樹。其中敏感詞對應的路徑為通的，並且最後乙個是頁節點（比如abcde是敏感詞，那麼第5層的e對應的指標就是空的）。
如果非敏感詞，則無此通路或者有此通路但還有後續節點
比如abcde是敏感詞，abcdf不是
abcdf***是乙個待過濾的字串，在前四個位元組匹配後，在第四層的f對應那個指標就為空。匹配失敗
abc對應的c節點還有後續節點，那麼abc也就不在敏感詞中
在查詢時，通過將文章按位元組在trie樹中進行查詢，如果能一直有路徑到葉節點，那麼目前這條從根節點到葉節點的路徑就是第三詞
如果不是，很明顯我們需要將文章向後移一位再做對比。這樣其實複雜度非常高
解決這個問題可以引入KMP演算法並將其擴充套件，將每個節點在匹配失敗後，文章的下一位元組應該到哪個節點重新開始匹配計算出來，將文章下一位元組直接與這個節點進行匹配，這樣每次文章只需要遍歷一次。複雜度為O(n)，n為文章長度。
至於空間複雜度，最壞的情況下，當所有敏感詞鏈路沒有交集時，由於使用trie樹結構，整個資料會膨脹(256+256)＊4 = 2048 倍，兩個256分別表示乙個節點中的兩套指標（子節點指標與KMP需要的指標），4表示乙個位元組變成了4個位元組（如果是32位機器的話）。 當然，如果將所有節點在乙個陣列下分配的話，就不需要存指標了，存陣列位置即可。資料小陣列可以2^16長，這時就變成2位元組了，資料大2^32個節點差不多也夠了吧。
而且在64位機下也一樣。
所以10w級別的詞，按每個詞平均10位元組算，一共1M，最壞情況下需要2G記憶體實現。
3樓：大雄
這個有很多辦法，其實跟分詞不一樣，就是乙個字串匹配問題。
方法1，雙雜湊：
有2個雜湊表，第乙個是縮小範圍的判定雜湊，第二個是不同字數遮蔽詞的雜湊表。
每當我們讀到乙個字，就到第乙個表裡取一下，可以得到以這個字開頭的遮蔽詞的長度分別有哪些，比如(2，3，5)。然後分別從這個字開始，分2，3，5個字的詞，去查第二個雜湊表，查到了則返回危險，否則繼續判定下乙個字。
複雜度：O(L*n)，L為以每個字開頭的詞長度的平均個數，n為輸入流長度。（真繞）
方法2，有限自動機：
有限自動機說白了就是手工展開的正規表示式，把詞表綜合成乙個巨大的有限自動機，每輸入乙個字就到自動機裡查表，跳轉狀態，到匹配狀態則為危險句子，到結束符則不危險。
時間複雜度：O(n)
空間複雜度：不可估計，可能會很大
方法3，一些其它字串匹配演算法的變形：
具體沒細想，類似kmp，rk，bm的變形或許也能解決這個問題。
總之，最笨的方法是前向最大匹配，複雜度O(m*max(L))，其中max(L)為最長遮蔽詞的長度。
乙個好的匹配演算法可以減少L的長度，檢測並跳過沒必要的計算。
如何看待位元組跳動招聘收到的演算法工程師簡歷的數量遠超需求？
Otems 主要是很多投遞的簡歷都不滿足技術部門的要求，即使還有特別多的HC BTW，大家要是有興趣來位元組做演算法，可以私戳我內推 所在部門在大規模擴張中，發展空間巨大。 ECUSTJared 我也來強行回答一波。本人19年畢業，現在在某家工作一年，算上實習就是兩年了。讀研的時候發了兩篇trans...
好的PHP工程師為什麼不好招聘到？
wtw 把月薪加到30k，招聘標準改為PHP Vue全棧或者PHP Go。高階的PHP程式設計師不以PHPer自居，因為那樣顯得low不好要價。 hileon 確實啊，今年php和前端都很難找啊，難道都去做網際網路 了？打車發一下我們的招聘資訊 http www. 因為，公司不需要大牛，又要便宜又要...
為什麼網路工程師招聘要求網路以外的知識
主標題回答 因為HR不專業，不清楚要什麼條件的人。最後的回答 有這樣的人，例如合作夥伴的肥佬主管，合作夥伴的不同方向的工程師貌似都懟不贏他。最後，其實都不難，隨著工作經驗增長，你會覺得也就那樣。 葉煥新 AP無線 F5負載均衡器難道不是網路裝置麼？至於伺服器的在整合專案中，讓網工做的基本上都是組個r...