DFA 演算法是通過提前構造出一個 樹狀查找結構，之后根據輸入在該樹狀結構中就可以進行非常高效的查找，
設我們有一個敏感詞庫，詞酷中的詞匯為：
我愛你
我愛他
我愛她
我愛你呀
我愛他呀
我愛她呀
我愛她啊
那么就可以構造出這樣的樹狀結構：
設玩家輸入的字串為：白菊我愛你呀哈哈哈
我們遍歷玩家輸入的字串 str，并設指標 i 指向樹狀結構的根節點，即最左邊的空白節點：
str[0] = ‘白’ 時，此時 tree[i] 沒有指向值為 ‘白’ 的節點，所以不滿足匹配條件，繼續往下遍歷
str[1] = ‘菊’，同樣不滿足匹配條件，繼續遍歷
str[2] = ‘我’，此時 tree[i] 有一條路徑連接著 ‘我’ 這個節點，滿足匹配條件，i 指向 ‘我’ 這個節點，然后繼續遍歷
str[3] = ‘愛’，此時 tree[i] 有一條路徑連著 ‘愛’ 這個節點，滿足匹配條件，i 指向 ‘愛’，繼續遍歷
str[4] = ‘你’，同樣有路徑，i 指向 ‘你’，繼續遍歷
str[5] = ‘呀’，同樣有路徑，i 指向 ‘呀’
此時，我們的指標 i 已經指向了樹狀結構的末尾，即此時已經完成了一次敏感詞判斷，我們可以用變數來記錄下這次敏感詞匹配開始時玩家輸入字串的下標，和匹配結束時的下標，然后再遍歷一次將字符替換為 * 即可，
結束一次匹配后，我們把指標 i 重新指向樹狀結構的根節點處，
此時我們玩家輸入的字串還沒有遍歷到頭，所以繼續遍歷：
str[6] = ‘哈’，不滿足匹配條件，繼續遍歷
str[7] = ‘哈’ …
str[8] = ‘哈’ …
可以看出我們遍歷了一次玩家輸入的字串，就找到了其中的敏感詞匯，
設玩家輸入的字串為：白菊我愛你呀哈哈哈
我們遍歷玩家輸入的字串 str，并設指標 i 指向樹狀結構的根節點，即最左邊的空白節點：
str[0] = ‘白’ 時，此時 tree[i] 沒有指向值為 ‘白’ 的節點，所以不滿足匹配條件，繼續往下遍歷
str[1] = ‘菊’，同樣不滿足匹配條件，繼續遍歷
str[2] = ‘我’，此時 tree[i] 有一條路徑連接著 ‘我’ 這個節點，滿足匹配條件，i 指向 ‘我’ 這個節點，然后繼續遍歷
str[3] = ‘愛’，此時 tree[i] 有一條路徑連著 ‘愛’ 這個節點，滿足匹配條件，i 指向 ‘愛’，繼續遍歷
str[4] = ‘你’，同樣有路徑，i 指向 ‘你’，繼續遍歷
str[5] = ‘呀’，同樣有路徑，i 指向 ‘呀’
此時，我們的指標 i 已經指向了樹狀結構的末尾，即此時已經完成了一次敏感詞判斷，我們可以用變數來記錄下這次敏感詞匹配開始時玩家輸入字串的下標，和匹配結束時的下標，然后再遍歷一次將字符替換為 * 即可，
結束一次匹配后，我們把指標 i 重新指向樹狀結構的根節點處，
此時我們玩家輸入的字串還沒有遍歷到頭，所以繼續遍歷：
str[6] = ‘哈’，不滿足匹配條件，繼續遍歷
str[7] = ‘哈’ …
str[8] = ‘哈’ …
可以看出我們遍歷了一次玩家輸入的字串，就找到了其中的敏感詞匯，
DFA演算法python實作：
1 class DFA: 2 """DFA 演算法 3 敏感字中“*”代表任意一個字符 4 """ 5 6 def __init__(self, sensitive_words: list, skip_words: list): # 對于敏感詞sensitive_words及無意義的詞skip_words可以通過資料庫、檔案或者其他存盤介質進行保存 7 self.state_event_dict = self._generate_state_event(sensitive_words) 8 self.skip_words = skip_words 9 10 def __repr__(self): 11 return '{}'.format(self.state_event_dict) 12 13 @staticmethod 14 def _generate_state_event(sensitive_words) -> dict: 15 state_event_dict = {} 16 for word in sensitive_words: 17 tmp_dict = state_event_dict 18 length = len(word) 19 for index, char in enumerate(word): 20 if char not in tmp_dict: 21 next_dict = {'is_end': False} 22 tmp_dict[char] = next_dict 23 tmp_dict = next_dict 24 else: 25 next_dict = tmp_dict[char] 26 tmp_dict = next_dict 27 if index == length - 1: 28 tmp_dict['is_end'] = True 29 return state_event_dict 30 31 def match(self, content: str): 32 match_list = [] 33 state_list = [] 34 temp_match_list = [] 35 36 for char_pos, char in enumerate(content): 37 if char in self.skip_words: 38 continue 39 if char in self.state_event_dict: 40 state_list.append(self.state_event_dict) 41 temp_match_list.append({ 42 "start": char_pos, 43 "match": "" 44 }) 45 for index, state in enumerate(state_list): 46 is_match = False 47 state_char = None 48 if '*' in state: # 對于一些敏感詞，比如大傻X，可能是大傻B，大傻×，大傻...，采用通配符*，一個*代表一個字符 49 state_list[index] = state['*'] 50 state_char = state['*'] 51 is_match = True 52 if char in state: 53 state_list[index] = state[char] 54 state_char = state[char] 55 is_match = True 56 if is_match: 57 if state_char["is_end"]: 58 stop = char_pos + 1 59 temp_match_list[index]['match'] = content[ 60 temp_match_list[index]['start']:stop] 61 match_list.append(copy.deepcopy(temp_match_list[index])) 62 if len(state_char.keys()) == 1: 63 state_list.pop(index) 64 temp_match_list.pop(index) 65 else: 66 state_list.pop(index) 67 temp_match_list.pop(index) 68 for index, match_words in enumerate(match_list): 69 print(match_words['start']) 70 return match_list
_generate_state_event方法生成敏感詞的樹狀結構，（以字典保存），對于上面的例子，生成的樹狀結構保存如下：
if __name__ == '__main__': dfa = DFA(['我愛你', '我愛他', '我愛她', '我愛你呀', '我愛他呀', '我愛她呀', '我愛她啊'], skip_words=[]) # 暫時不配置skip_words print(dfa)
結果：
{'我': {'is_end': False, '愛': {'is_end': False, '你': {'is_end': True, '呀': {'is_end': True}}, '他': {'is_end': True, '呀': {'is_end': True}}, '她': {'is_end': True, '呀': {'is_end': True}, '啊': {'is_end': True}}}}}
然后呼叫match方法，輸入內容進行敏感詞匹配：
if __name__ == '__main__': dfa = DFA(['我愛你', '我愛他', '我愛她', '我愛你呀', '我愛他呀', '我愛她呀', '我愛她啊'], ['\n', '\r\n', '\r']) # print(dfa) print(dfa.match('白菊我愛你呀哈哈哈'))
結果：
[{'start': 2, 'match': '我愛你'}, {'start': 2, 'match': '我愛你呀'}]
而對于一些敏感詞，比如大傻X，可能是大傻B，大傻×，大傻...，那是不是可以通過一個通配符*來解決？
見代碼：48 ~51行
DFA 演算法是通過提前構造出一個 樹狀查找結構，之后根據輸入在該樹狀結構中就可以進行非常高效的查找，
設我們有一個敏感詞庫，詞酷中的詞匯為：
我愛你
我愛他
我愛她
我愛你呀
我愛他呀
我愛她呀
我愛她啊
那么就可以構造出這樣的樹狀結構：
設玩家輸入的字串為：白菊我愛你呀哈哈哈
我們遍歷玩家輸入的字串 str，并設指標 i 指向樹狀結構的根節點，即最左邊的空白節點：
str[0] = ‘白’ 時，此時 tree[i] 沒有指向值為 ‘白’ 的節點，所以不滿足匹配條件，繼續往下遍歷
str[1] = ‘菊’，同樣不滿足匹配條件，繼續遍歷
str[2] = ‘我’，此時 tree[i] 有一條路徑連接著 ‘我’ 這個節點，滿足匹配條件，i 指向 ‘我’ 這個節點，然后繼續遍歷
str[3] = ‘愛’，此時 tree[i] 有一條路徑連著 ‘愛’ 這個節點，滿足匹配條件，i 指向 ‘愛’，繼續遍歷
str[4] = ‘你’，同樣有路徑，i 指向 ‘你’，繼續遍歷
str[5] = ‘呀’，同樣有路徑，i 指向 ‘呀’
此時，我們的指標 i 已經指向了樹狀結構的末尾，即此時已經完成了一次敏感詞判斷，我們可以用變數來記錄下這次敏感詞匹配開始時玩家輸入字串的下標，和匹配結束時的下標，然后再遍歷一次將字符替換為 * 即可，
結束一次匹配后，我們把指標 i 重新指向樹狀結構的根節點處，
此時我們玩家輸入的字串還沒有遍歷到頭，所以繼續遍歷：
str[6] = ‘哈’，不滿足匹配條件，繼續遍歷
str[7] = ‘哈’ …
str[8] = ‘哈’ …
可以看出我們遍歷了一次玩家輸入的字串，就找到了其中的敏感詞匯，
設玩家輸入的字串為：白菊我愛你呀哈哈哈
我們遍歷玩家輸入的字串 str，并設指標 i 指向樹狀結構的根節點，即最左邊的空白節點：
str[0] = ‘白’ 時，此時 tree[i] 沒有指向值為 ‘白’ 的節點，所以不滿足匹配條件，繼續往下遍歷
str[1] = ‘菊’，同樣不滿足匹配條件，繼續遍歷
str[2] = ‘我’，此時 tree[i] 有一條路徑連接著 ‘我’ 這個節點，滿足匹配條件，i 指向 ‘我’ 這個節點，然后繼續遍歷
str[3] = ‘愛’，此時 tree[i] 有一條路徑連著 ‘愛’ 這個節點，滿足匹配條件，i 指向 ‘愛’，繼續遍歷
str[4] = ‘你’，同樣有路徑，i 指向 ‘你’，繼續遍歷
str[5] = ‘呀’，同樣有路徑，i 指向 ‘呀’
此時，我們的指標 i 已經指向了樹狀結構的末尾，即此時已經完成了一次敏感詞判斷，我們可以用變數來記錄下這次敏感詞匹配開始時玩家輸入字串的下標，和匹配結束時的下標，然后再遍歷一次將字符替換為 * 即可，
結束一次匹配后，我們把指標 i 重新指向樹狀結構的根節點處，
此時我們玩家輸入的字串還沒有遍歷到頭，所以繼續遍歷：
str[6] = ‘哈’，不滿足匹配條件，繼續遍歷
str[7] = ‘哈’ …
str[8] = ‘哈’ …
可以看出我們遍歷了一次玩家輸入的字串，就找到了其中的敏感詞匯，
DFA演算法python實作：
1 class DFA: 2 """DFA 演算法 3 敏感字中“*”代表任意一個字符 4 """ 5 6 def __init__(self, sensitive_words: list, skip_words: list): 7 self.state_event_dict = self._generate_state_event(sensitive_words) 8 self.skip_words = skip_words 9 10 def __repr__(self): 11 return '{}'.format(self.state_event_dict) 12 13 @staticmethod 14 def _generate_state_event(sensitive_words) -> dict: 15 state_event_dict = {} 16 for word in sensitive_words: 17 tmp_dict = state_event_dict 18 length = len(word) 19 for index, char in enumerate(word): 20 if char not in tmp_dict: 21 next_dict = {'is_end': False} 22 tmp_dict[char] = next_dict 23 tmp_dict = next_dict 24 else: 25 next_dict = tmp_dict[char] 26 tmp_dict = next_dict 27 if index == length - 1: 28 tmp_dict['is_end'] = True 29 return state_event_dict 30 31 def match(self, content: str): 32 match_list = [] 33 state_list = [] 34 temp_match_list = [] 35 36 for char_pos, char in enumerate(content): 37 if char in self.skip_words: 38 continue 39 if char in self.state_event_dict: 40 state_list.append(self.state_event_dict) 41 temp_match_list.append({ 42 "start": char_pos, 43 "match": "" 44 }) 45 for index, state in enumerate(state_list): 46 is_match = False 47 state_char = None 48 if '*' in state: 49 state_list[index] = state['*'] 50 state_char = state['*'] 51 is_match = True 52 if char in state: 53 state_list[index] = state[char] 54 state_char = state[char] 55 is_match = True 56 if is_match: 57 if state_char["is_end"]: 58 stop = char_pos + 1 59 temp_match_list[index]['match'] = content[ 60 temp_match_list[index]['start']:stop] 61 match_list.append(copy.deepcopy(temp_match_list[index])) 62 if len(state_char.keys()) == 1: 63 state_list.pop(index) 64 temp_match_list.pop(index) 65 else: 66 state_list.pop(index) 67 temp_match_list.pop(index) 68 return match_listView Code
_generate_state_event方法生成敏感詞的樹狀結構，（以字典保存），對于上面的例子，生成的樹狀結構保存如下：
if __name__ == '__main__':
dfa = DFA(['我愛你', '我愛他', '我愛她', '我愛你呀', '我愛他呀', '我愛她呀', '我愛她啊'], skip_words=[]) # 暫時不配置skip_words
print(dfa)
結果：
{'我': {'is_end': False, '愛': {'is_end': False, '你': {'is_end': True, '呀': {'is_end': True}}, '他': {'is_end': True, '呀': {'is_end': True}}, '她': {'is_end': True, '呀': {'is_end': True}, '啊': {'is_end': True}}}}}
然后呼叫match方法，輸入內容進行敏感詞匹配：
if __name__ == '__main__':
dfa = DFA(['我愛你', '我愛他', '我愛她', '我愛你呀', '我愛他呀', '我愛她呀', '我愛她啊'], ['\n', '\r\n', '\r'])
# print(dfa)
print(dfa.match('白菊我愛你呀哈哈哈'))
結果：
[{'start': 2, 'match': '我愛你'}, {'start': 2, 'match': '我愛你呀'}]
而對于一些敏感詞，比如大傻X，可能是大傻B，大傻×，大傻...，那是不是可以通過一個通配符*來解決？
見代碼：48 ~51行
48 if '*' in state: # 對于一些敏感詞，比如大傻X，可能是大傻B，大傻×，大傻...，采用通配符*，一個*代表一個字符
49 state_list[index] = state['*']
50 state_char = state['*']
51 is_match = True
驗證一下：
if __name__ == '__main__':
dfa = DFA(['大傻*'], [])
print(dfa)
print(dfa.match('大傻X安樂飛大傻B'))
結果：
{'大': {'is_end': False, '傻': {'is_end': False, '*': {'is_end': True}}}}
[{'start': 0, 'match': '大傻X'}, {'start': 6, 'match': '大傻B'}]
上列中如果輸入的內容中，“大傻X安樂飛大傻B”寫成“大%傻X安樂飛大&傻B”，看看是否能識別出敏感詞呢？識別不出了！
if __name__ == '__main__':
dfa = DFA(['大傻*'], [])
print(dfa)
print(dfa.match('大%傻X安樂飛大&傻B'))
結果：
{'大': {'is_end': False, '傻': {'is_end': False, '*': {'is_end': True}}}}
[
諸如“,&,!,！,@,#,$,￥,*,^,%,?,？,<,>,《,》"，這些特殊符號無實際意義，但是可以在敏感詞中間插入而破壞敏感詞的結構規避敏感詞檢查
進行無意義詞配置，再進行敏感詞檢查，如下，可見對于被破壞的敏感詞也能識別
if __name__ == '__main__':
dfa = DFA(['大傻*'], ['%', '&'])
print(dfa)
print(dfa.match('大%傻X安樂飛大&傻B'))
結果：
{'大': {'is_end': False, '傻': {'is_end': False, '*': {'is_end': True}}}}
[{'start': 0, 'match': '大%傻X'}, {'start': 7, 'match': '大&傻B'}]
48 if '*' in state: # 對于一些敏感詞，比如大傻X，可能是大傻B，大傻×，大傻...，采用通配符*，一個*代表一個字符
49 state_list[index] = state['*']
50 state_char = state['*']
51 is_match = True
驗證一下：
if __name__ == '__main__': dfa = DFA(['大傻*'], []) print(dfa) print(dfa.match('大傻X安樂飛大傻B'))
結果：
{'大': {'is_end': False, '傻': {'is_end': False, '*': {'is_end': True}}}}
[{'start': 0, 'match': '大傻X'}, {'start': 6, 'match': '大傻B'}]
上列中如果輸入的內容中，“大傻X安樂飛大傻B”寫成“大%傻X安樂飛大&傻B”，看看是否能識別出敏感詞呢？識別不出了！
if __name__ == '__main__': dfa = DFA(['大傻*'], []) print(dfa) print(dfa.match('大%傻X安樂飛大&傻B'))
結果：
{'大': {'is_end': False, '傻': {'is_end': False, '*': {'is_end': True}}}}
[
諸如“,&,!,！,@,#,$,￥,*,^,%,?,？,<,>,《,》"，這些特殊符號無實際意義，但是可以在敏感詞中間插入而破壞敏感詞的結構規避敏感詞檢查
進行無意義詞配置，再進行敏感詞檢查，如下，可見對于被破壞的敏感詞也能識別
if __name__ == '__main__': dfa = DFA(['大傻*'], ['%', '&']) print(dfa) print(dfa.match('大%傻X安樂飛大&傻B'))
結果：
{'大': {'is_end': False, '傻': {'is_end': False, '*': {'is_end': True}}}}
[{'start': 0, 'match': '大%傻X'}, {'start': 7, 'match': '大&傻B'}]
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/460775.html
標籤：其他