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] = ‘哈’ …
可以看出我们遍历了一次玩家输入的字符串,就找到了其中的敏感词汇。
DFA算法python实现
class DFA: """DFA 算法 敏感字中“*”代表任意一个字符 """ def __init__(self, sensitive_words: list, skip_words: list): # 对于敏感词sensitive_words及无意义的词skip_words可以通过数据库、文件或者其他存储介质进行保存 self.state_event_dict = self._generate_state_event(sensitive_words) self.skip_words = skip_words def __repr__(self): return "{}".format(self.state_event_dict) @staticmethod def _generate_state_event(sensitive_words) -> dict: state_event_dict = {} for word in sensitive_words: tmp_dict = state_event_dict length = len(word) for index, char in enumerate(word): if char not in tmp_dict: next_dict = {"is_end": False} tmp_dict[char] = next_dict tmp_dict = next_dict else: next_dict = tmp_dict[char] tmp_dict = next_dict if index == length - 1: tmp_dict["is_end"] = True return state_event_dict def match(self, content: str): match_list = [] state_list = [] temp_match_list = [] for char_pos, char in enumerate(content): if char in self.skip_words: continue if char in self.state_event_dict: state_list.append(self.state_event_dict) temp_match_list.append({ "start": char_pos, "match": "" }) for index, state in enumerate(state_list): is_match = False state_char = None if "*" in state: # 对于一些敏感词,比如大傻X,可能是大傻B,大傻×,大傻...,采用通配符*,一个*代表一个字符 state_list[index] = state["*"] state_char = state["*"] is_match = True if char in state: state_list[index] = state[char] state_char = state[char] is_match = True if is_match: if state_char["is_end"]: stop = char_pos + 1 temp_match_list[index]["match"] = content[ temp_match_list[index]["start"]:stop] match_list.append(copy.deepcopy(temp_match_list[index])) if len(state_char.keys()) == 1: state_list.pop(index) temp_match_list.pop(index) else: state_list.pop(index) temp_match_list.pop(index) for index, match_words in enumerate(match_list): print(match_words["start"]) 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行
if "*" in state: # 对于一些敏感词,比如大傻X,可能是大傻B,大傻×,大傻...,采用通配符*,一个*代表一个字符 state_list[index] = state["*"] state_char = state["*"] 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"}]
以上就是Python基于DFA算法实现内容敏感词过滤的详细内容,更多关于Python敏感词过滤的资料请关注脚本之家其它相关文章!
X 关闭
X 关闭
- 15G资费不大降!三大运营商谁提供的5G网速最快?中国信通院给出答案
- 2联想拯救者Y70发布最新预告:售价2970元起 迄今最便宜的骁龙8+旗舰
- 3亚马逊开始大规模推广掌纹支付技术 顾客可使用“挥手付”结账
- 4现代和起亚上半年出口20万辆新能源汽车同比增长30.6%
- 5如何让居民5分钟使用到各种设施?沙特“线性城市”来了
- 6AMD实现连续8个季度的增长 季度营收首次突破60亿美元利润更是翻倍
- 7转转集团发布2022年二季度手机行情报告:二手市场“飘香”
- 8充电宝100Wh等于多少毫安?铁路旅客禁止、限制携带和托运物品目录
- 9好消息!京东与腾讯续签三年战略合作协议 加强技术创新与供应链服务
- 10名创优品拟通过香港IPO全球发售4100万股 全球发售所得款项有什么用处?