安全開發第二講-如何實作敏感詞組的快速比對

敏感詞詞組的例子模式

今天&早上&吃飯      

詞組模式可以将句子比對詞組化，進而減少純句子比對帶來的漏報

設待檢測文本的大小為分詞之後存在500個詞語

假如你手上有百萬級的檢測詞組庫，你能想到哪些方案快速檢測（1秒内響應）？

1、set集合

首先我們來想一想集合是否可行，首先我們可以将詞組通過&拆分，然後形成詞語，每個詞組是由多個詞語構成的

AA&BB&CC => AA BB CC      

拆分之後的詞語對象應該至少包含兩個屬性：詞語名+詞語所在的詞組id清單，這樣的對應關系需要額外的結構來存儲。然後百萬級的詞庫将産生百萬級的對象（有多少個詞就會産生多少個這樣的對象），然後我們把這些詞語全部存儲到一個set集合中。我們知道，在Java8中，HashSet是基于HashMap實作的，而HashMap是基于連結清單+紅黑樹實作的，初始時，HashMap内部是連結清單的結構，當達到一定門檻值的時候，就會轉成紅黑樹來存儲節點。同時，HashMap為了減少碰撞率，需要通過荷載因子進行擴容（即達到多少的荷載就進行一次擴容），當HashMap中存儲的節點越多，擴容帶來的影響就越大。在我們的場景中，如果讓一個HashMap去存儲百萬級的對象，暫且不考慮是否會出現OOM或者棧溢出。光是每次擴容帶來的影響就很頭大了。

集合的平均查找時間複雜度是O(Logn)，對于百萬級，也就是說一個詞語需要查詢6-7次，然後再從詞語名->詞語所在的詞組id清單的對應關系中取出(一般使用hashMap存儲)，也需要6-7次查詢。也就是說，一個詞語需要12-14次左右的查詢。一篇文章大約一共需要12*500=6000次比對，存儲方面需要使用HashSet存儲詞，用HashMap存儲詞語和其所在id清單對應關系。

看起來這樣的結果卻是還是可以令人接受的，那麼你還可以提出别的方法嗎？

2、Trie樹

和上面一樣，詞組需要進行拆分

AA&BB&CC&AAB => AA BB CC AAB      

trie樹的每個節點都是一個字兒，對于 AA 和 AAB這兩個詞，最終的結構将是 root->A->A->B，其中在B和第二個A裡面會标記為詞語結束節點。每個處于結束位置的節點需要指定目前詞組的id，進而形成所屬的id清單。在百萬級的詞庫下，我們需要拆分出每個詞，也就是節點數大約是3*n（n為詞庫的大小），不需要額外的其他存儲。從查詢角度出發，對于一個詞，隻需要拆分為字序，然後按照順序比對即可，如果比對不到，說明該詞不在目前Trie樹中，如果比對結束，但是末尾節點在目前Trie樹中不是結尾字元，那麼也判定為結果不存在，時間複雜度為O(e),e為詞語的長度。可見，Trie樹的時間複雜度非常低，完全是依靠空間換時間的方法，在我們的開發應用環境中，記憶體等實體資源往往都是比較大的，節約時間，提高效率是每一個api提供者必要的修行。

以java為例，我們可以使用apache的包來實作這樣的功能

<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-collections4</artifactId>
    <version>4.4</version>
</dependency>