方法一:(最簡單、不提倡)
對要進行檢測的文本,周遊所有敏感詞,逐個檢測輸入的文本中是否含有指定的敏感詞。這種方式是最簡單的敏感詞過濾方案了,實作起來不難
public void test1(){
Set<String> sensitiveWords=new HashSet<>();
sensitiveWords.add("shit");
sensitiveWords.add("傻逼");
sensitiveWords.add("笨蛋");
String text="你是傻逼啊";
for(String sensitiveWord:sensitiveWords){
if(text.contains(sensitiveWord)){
System.out.println("輸入的文本存在敏感詞。——"+sensitiveWord);
break;
}
}
}
注意:這個方案有一個很大的問題是,随着敏感詞數量的增多,敏感詞檢測的時間會呈線性增長。項目的敏感詞數量隻有幾十個,使用這種方案不會存在太大的性能問題。但是如果項目中有成千上萬個敏感詞,使用這種方案就會很耗CPU了。
方案二:( DFA 有窮自動機算法)
DFA的算法,即Deterministic Finite Automaton算法,翻譯成中文就是确定有窮自動機算法。它的基本思想是基于狀态轉移來檢索敏感詞,隻需要掃描一次待檢測文本,就能對所有敏感詞進行檢測,是以效率比方案一高不少。
假設我們有以下5個敏感詞需要檢測:傻逼、傻子、傻大個、壞蛋、壞人。那麼我們可以先把敏感詞中有相同字首的詞組合成一個樹形結構,不同字首的詞分屬不同樹形分支,以上述5個敏感詞為例,可以初始化成如下2棵樹:
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiATN381dsQWZ4lmZf1GLlpXazVmcvwFciV2dsQXYtJ3bm9CX9s2RkBnVHFmb1clWvB3MaVnRtp1XlBXe0xCMy81dvRWYoNHLwEzX5xCMx8FesU2cfdGLwMzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsYTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5iMwQjN3AjM2AjM4MzMkV2YxYzXwADN1cTMxMzLcJTMxIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjLyM3Lc9CX6MHc0RHaiojIsJye.png)
把敏感詞組成成樹形結構有什麼好處呢?最大的好處就是可以減少檢索次數,我們隻需要周遊一次待檢測文本,然後在敏感詞庫中檢索出有沒有該字元對應的子樹就行了,如果沒有相應的子樹,說明目前檢測的字元不在敏感詞庫中,則直接跳過繼續檢測下一個字元;如果有相應的子樹,則接着檢查下一個字元是不是前一個字元對應的子樹的子節點,這樣疊代下去,就能找出待檢測文本中是否包含敏感詞了。
我們以文本“你是不是傻逼”為例,我們依次檢測每個字元,因為前4個字元都不在敏感詞庫裡,找不到相應的子樹,是以直接跳過。當檢測到“傻”字時,發現敏感詞庫中有相應的子樹,我們把他記為tree-1,接着再搜尋下一個字元“逼”是不是子樹tree-1的子節點,發現恰好是,接下來再判斷“逼”這個字元是不是葉子節點,如果是,則說明比對到了一個敏感詞了,在這裡“逼”這個字元剛好是tree-1的葉子節點,是以成功檢索到了敏感詞:“傻逼”。大家發現了沒有,在我們的搜尋過程中,我們隻需要掃描一次被檢測文本就行了,而且對于被檢測文本中不存在的敏感詞,如這個例子中的“壞蛋”和“壞人”,我們完全不會掃描到,是以相比方案一效率大大提升了。
可以用HashMap來存儲上述的樹形結構,以上述敏感詞為例把每個敏感詞字元串拆散成字元,再存儲到HashMap中
{
"傻": {
"逼": {
"isEnd": "Y"
},
"子": {
"isEnd": "Y"
},
"大": {
"個": {
"isEnd": "Y"
}
}
}
}
首先将每個詞的第一個字元作為key,value則是另一個HashMap,value對應的HashMap的key為第二個字元,如果還有第三個字元,則存儲到以第二個字元為key的value中,當然這個value還是一個HashMap,以此類推下去,直到最後一個字元,當然最後一個字元對應的value也是HashMap,隻不過這個HashMap隻需要存儲一個結束标志就行了,像上述的例子中,我們就存了一個{"isEnd","Y"}的HashMap,來表示這個value對應的key是敏感詞的最後一個字元。同理,“壞人”和“壞蛋”這2個敏感詞也是按這樣的方式存儲起來,這裡就不羅列出來了。
用HashMap存儲有什麼好處呢?我們知道HashMap在理想情況下可以以O(1)的時間複雜度進行查詢,是以我們在周遊待檢測字元串的過程中,可以以O(1)的時間複雜度檢索出目前字元是否在敏感詞庫中,效率比方案一提升太多了。
初始化敏感詞庫:
private Map<Object,Object> sensitiveWordsMap;
private static final String END_FLAG="end";
private void initSensitiveWordsMap(Set<String> sensitiveWords){
if(sensitiveWords==null||sensitiveWords.isEmpty()){
throw new IllegalArgumentException("Senditive words must not be empty!");
}
sensitiveWordsMap=new HashMap<>(sensitiveWords.size());
String currentWord;
Map<Object,Object> currentMap;
Map<Object,Object> subMap;
Iterator<String> iterator = sensitiveWords.iterator();
while (iterator.hasNext()){
currentWord=iterator.next();
if(currentWord==null||currentWord.trim().length()<2){ //敏感詞長度必須大于等于2
continue;
}
currentMap=sensitiveWordsMap;
for(int i=0;i<currentWord.length();i++){
char c=currentWord.charAt(i);
subMap=(Map<Object, Object>) currentMap.get(c);
if(subMap==null){
subMap=new HashMap<>();
currentMap.put(c,subMap);
currentMap=subMap;
}else {
currentMap= subMap;
}
if(i==currentWord.length()-1){
//如果是最後一個字元,則put一個結束标志,這裡隻需要儲存key就行了,value為null可以節省空間。
//如果不是最後一個字元,則不需要存這個結束标志,同樣也是為了節省空間。
currentMap.put(END_FLAG,null);
}
}
}
}
代碼的邏輯就是循環敏感詞集合,将他們放到HashMap中。
敏感詞的掃描:
public enum MatchType {
MIN_MATCH("最小比對規則"),MAX_MATCH("最大比對規則");
String desc;
MatchType(String desc) {
this.desc = desc;
}
}
public Set<String> getSensitiveWords(String text,MatchType matchType){
if(text==null||text.trim().length()==0){
throw new IllegalArgumentException("The input text must not be empty.");
}
Set<String> sensitiveWords=new HashSet<>();
for(int i=0;i<text.length();i++){
int sensitiveWordLength = getSensitiveWordLength(text, i, matchType);
if(sensitiveWordLength>0){
String sensitiveWord = text.substring(i, i + sensitiveWordLength);
sensitiveWords.add(sensitiveWord);
if(matchType==MatchType.MIN_MATCH){
break;
}
i=i+sensitiveWordLength-1;
}
}
return sensitiveWords;
}
public int getSensitiveWordLength(String text,int startIndex,MatchType matchType){
if(text==null||text.trim().length()==0){
throw new IllegalArgumentException("The input text must not be empty.");
}
char currentChar;
Map<Object,Object> currentMap=sensitiveWordsMap;
int wordLength=0;
boolean endFlag=false;
for(int i=startIndex;i<text.length();i++){
currentChar=text.charAt(i);
Map<Object,Object> subMap=(Map<Object,Object>) currentMap.get(currentChar);
if(subMap==null){
break;
}else {
wordLength++;
if(subMap.containsKey(END_FLAG)){
endFlag=true;
if(matchType==MatchType.MIN_MATCH){
break;
}else {
currentMap=subMap;
}
}else {
currentMap=subMap;
}
}
}
if(!endFlag){
wordLength=0;
}
return wordLength;
}
MatchType表示比對規則,有時候我們隻需要找到一個敏感詞就可以了,有時候則需要知道待檢測文本中到底包含多少個敏感詞,前者對應的是最小比對原則,後者則是最大比對原則。
getSensitiveWordLength方法的作用是根據給定的待檢測文本及起始下标,還有比對規則,計算出待檢測文本中的敏感詞長度,如果不存在,則傳回0,存在則傳回比對到的敏感詞長度。
getSensitiveWords方法則是掃描一遍待檢測文本,逐個檢測每個字元是否在敏感詞庫中,然後将檢測到的敏感詞截取出來放到集合中傳回給用戶端。
測試用例
public static void main(String[] args) {
Set<String> sensitiveWords=new HashSet<>();
sensitiveWords.add("你是傻逼");
sensitiveWords.add("你是傻逼啊");
sensitiveWords.add("你是壞蛋");
sensitiveWords.add("你個大笨蛋");
sensitiveWords.add("我去年買了個表");
sensitiveWords.add("shit");
TextFilter textFilter=new TextFilter();
textFilter.initSensitiveWordsMap(sensitiveWords);
String text="你你你你是傻逼啊你,說你呢,你個大笨蛋。";
System.out.println(textFilter.getSensitiveWords(text,MatchType.MAX_MATCH));
}
方案三:(對方案二漏洞的優化)
方案二在性能上已經可以滿足需求了,但是卻很容易被破解,比如說,我在待檢測文本中的敏感詞中間加個空格,就可以成功繞過了。要解決這個問題也不難,有一個簡單的方法是初始化一個無效字元庫,比如:空格、*、#、@等字元,然後在檢測文本前,先将待檢測文本中的無效字元去除,這樣的話被檢測字元就不存在這些無效字元了,是以還是可以繼續用方案二進行過濾。隻要被檢測文本不要太長,那麼我們隻要在方案二的基礎上再多掃描一次被檢測文本去除無效字元就行了,這個性能損耗也還是可以接受的。