基于DFA的中拼混合敏感词过滤算法

Chinese Characters and Pinyin Mixed Sensitive Word Filtering Algorithm Based on DFA

摘要: 本文针对当前网络上通过各种干扰形式“伪装”的敏感词，提出了一种基于DFA的中拼混合敏感词过滤算法，解决了一般的系统过滤方法难以成功检测过滤该类敏感词的问题，提高了包含该类敏感词文本过滤的查全率和查准率。本文提出的算法包括中文拼音敏感词库的扩充算法、敏感词树的构建算法、待检测文本的预处理算法以及敏感词过滤算法，通过实验得到该算法查准率为100%，查全率约为95%~100%，算法复杂度较低，满足实际应用需要。

Abstract: Aiming at the sensitive words that are “camouflaged” through various interference forms on the current network, this paper proposes a Chinese character and Pinyin mixed sensitive word filtering algorithm based on DFA, which solves the problem that the general system filtering methods are difficult to successfully detect and filter such sensitive words, and improves the recall and precision of text filtering containing such sensitive words. The algorithm proposed in this paper includes the expansion algorithm of the Chinese characters and Pinyin mixed sensitive word library, the construction algorithm of the sensitive word tree, the pretreatment algorithm of the text to be detected, and the sensitive word filtering algorithm. Through the experiment, the precision of the algorithm is 100%, and the recall is about 95%~100%. The algorithm complexity is low so this algorithm meets the practical application needs.

1. 引言

如今的互联网已经成为人们工作生活中必不可少的一部分，它能够提供各种类型的服务和信息，但同时互联网的包容和开放也给各种反动、暴力、色情、虚假广告等不良信息提供了良好的生存传播条件，这些不良信息危害着网络环境、人们，尤其是青少年的身心健康以及社会的稳定发展。尤其随着经济的发展，移动设备的使用人群扩大且趋于低龄化，微信、QQ、微博等线上交流的方式更受青少年欢迎，也使得他们更容易受到网络不良信息的影响，因此对这些不良信息的过滤成为了重要的研究内容。

然而，与英文文本相比，中文文本中的字词之间并没有类似空格这样明显的分隔符号，且汉字数量庞大，组成的词语数量更是难以计数，因此中文文本的敏感词过滤较为困难。同时为了避免系统过滤屏蔽，中文敏感词的传播方式也日渐丰富，由原始形式直接传播，到现在的混合无关干扰字符传播、中文拼音混合传播等等，也给中文敏感词过滤增加了不小的难度。

传统的敏感词过滤算法较为简单，主要是单模式匹配和多模式匹配 [1] [2]，后来有学者陆续对传统算法进行了改进，提出了ST-DFA [3] 等算法，但复杂度较高。刘邦国等人提出了一种面向PDF文本内容审查的高效多模式匹配算法 [4]，但只适用于敏感词长度和数量都较大的情况；陈永杰等人提出了一种基于Aho-Corasick算法改进的多模式匹配算法 [5]，但只适用于检测过滤原始形式的敏感词。因此本文提出了一种基于确定有限自动机(deterministic finite automaton, DFA)的中拼混合敏感词过滤算法，能够适用于敏感词长度数量不确定的情况且有效地过滤原始形式敏感词和干扰敏感词。

2. 敏感词过滤相关

2.1. 存在的问题

1) 干扰过滤。为了使包含敏感词的信息不被系统过滤得以传播，发布者通常会对敏感词进行“伪装”，常见的方法有添加无关字符干扰过滤，例如敏感词“金融危机”，可变形为“金@#融￥%危&……机”；使用中文拼音混合的形式干扰过滤，如变形为“jin融wei机”；此外还有同音字替换如“金融尾鸡”，中文拆分如“金融危木几”等干扰方法甚至多种干扰方法混合使用。这些经过干扰方法“伪装”的敏感词大多能在人们阅读时被识别理解，但一般的系统过滤方法难以成功检测过滤。

2) 准确率。出现的敏感词能不能被准确的检测过滤，非敏感词会不会被错误的判断过滤。

2.2. 评价指标

对于敏感词过滤算法的评价指标主要有查全率、准确率和综合评价指标值 [6]。

1)查全率 $R$，其中 $T$ 为文本包含的敏感词个数， $N$ 为算法正确过滤的敏感词个数。

$R=\frac{N}{T}\times 100\%$ (1)

2) 准确率 $P$，其中 $N$ 为算法正确过滤的敏感词个数， $M$ 为算法过滤的敏感词个数。

$P=\frac{N}{M}\times 100\%$ (2)

3) 综合评价指标值 $F$。

$F=\frac{2\times R\times P}{R+P}$ (3)

4) 算法复杂度，即时间复杂度和空间复杂度。

3. 算法设计

3.1. 算法总体设计

本文提出的算法的整体设计如图1。

Figure 1. Overall process of sensitive word filtering algorithm

图1. 敏感词过滤算法整体流程

3.2. 确定有限自动机

DFA即确定有限自动机 [7]，其数学模型为一个五元组 $M=\left(Q,\Sigma ,\delta ,q_0,F\right)$，其中， $Q$ 是一组有限状态的集合， $\forall q\in Q$， $q$ 称为 $M$ 的一个状态； $\Sigma$ 是一组输入符号的集合，称为字符表； $\delta$ 是状态转移函数， $\delta :Q\times \Sigma \to Q$，在一个状态 $q\in Q$ 读取到字符 $w\in \Sigma$，跳转到另一个状态 $p\in Q$，即 $\left(q,p,w\right)\in \delta$ ； $q_0$ 是起始状态； $F\subseteq Q$ 表示一组接受状态的集合。

在DFA中，状态和引起状态转换的事件都是确定的，状态和事件的数量是有限的 [8]。如图2所示，状态 $S$ 读入字符 $a$ 转换为状态 $U$，即 $S\to a\to U$。

Figure 2. State transition

图2. 状态转移

3.3. 中文拼音混合敏感词库扩充算法

为了避免中拼混合敏感词这一人工干扰过滤的情况，该算法利用排列组合的方式生成每个中文敏感词对应的所有中拼混合敏感词，如图3及公式(4)所示，一个中文敏感词由 $n$ 个字符组成，每个字符有汉字和拼音两种形式，因此一个中文敏感词对应的中拼混合敏感词一共有 $2^n$ 个。

Figure 3. Principle of permutation and combination

图3. 排列组合原理

$2\times 2\times 2\times \cdots \times 2=2^n$ (4)

该中文拼音混合敏感词库扩充算法具体如下：

1) 读取原始中文敏感词，以字为单位存入汉字列表line；

2) 使用get_pinyin()获取每个字的对应拼音并以整个拼音为单位存入拼音列表pinyin_list，获取列表长度length；

3) 新建中拼混合列表zhongpin_list用于存放生成的中拼混合敏感词；

4) 使用random.sample()随机选择中拼混合敏感词的第一个字符形式并记录该字符；

5) 使用random.sample()随机选择下一个字符形式并记录该字符，同时在两个字符中间添加空格字符作为分隔符；

6) 重复步骤5)直到生成一个完整的中拼混合敏感词；

7) 使用__contains__()判断生成的中拼混合敏感词是否已经存在于中拼混合列表zhongpin_list，不存在则添加进列表，存在则执行步骤4)；

8) 当中拼混合列表zhongpin_list的长度等于 $2^n$ 时，一个中文敏感词扩充完成，将列表元素写入文件，继续执行步骤1)直到所有中文敏感词扩充完成，得到中文拼音混合敏感词库。

3.4. 敏感词树构建算法

本文采用字典树结构构建敏感词树。

字典树 [9] 又称为Trie树、前缀树，具有以下特点：1) 树的根节点不存储数据，其他节点存储一个字符；2) 从根节点到叶节点的路径上的字符连接起来组成一个词。因此前缀相同的词语使用同一个分支，搜索时从词语的第一个字符开始查找对应的分支，能够显著地减少字符串比较，降低算法复杂度。

以敏感词“金融”和“金融危机”为例构建敏感词树如图4所示，前缀“金融”相同故使用同一分支，对应拼音整体存入一个叶节点，着色节点标志敏感词结束。

Figure 4. Sensitive word tree structure

图4. 敏感词树结构

敏感词树构建具体算法如下：

1) 读取敏感词，使用split()以空格为分隔符分割敏感词字符串，获取字符串列表；

2) 获取列表长度length，定义now_node指向当前节点，初始值为根节点root。定义i表示列表的第i个元素 $\left(0\le \text{i}\le \text{length}\right)$，初始值为0；

3) 判断列表元素word[i]是否存在于now_node.keys()中，存在则进行赋值now_node = now_node.get(word[i])，继续执行步骤3)；不存在则新建节点new_node，判断该节点是否为敏感词结束节点，是则进行标记，同时进行赋值now_node[word[i]] = new_node，now_node = new_node；

4) 重复步骤3)直至i = length − 1，完成一个敏感词的添加；

5) 继续执行步骤1)直至整个敏感词库添加完成，完成敏感词树的构建。

3.5. 待检测文本预处理算法

待检测文本中的拼音部分往往是连在一起没有明显分割的，这种情况不会影响人们阅读理解但是对于系统识别会产生影响导致无法准确过滤，因此需要对待检测文本进行处理分割出单个拼音。

单个拼音由声母和韵母组成，本文采用将声母大写的方法，根据大写字母分割出单个拼音。

同时识别并删除待检测文本中的无关干扰字符以免影响后续检测过滤。

具体算法如下：

1) 使用正则表达式去除掉除汉字、字母和数字外的字符；

2) 建立声母列表smlist，判断待检测文本中是否包含列表元素，有则使用upper()替换为大写；

3) 建立nosm列表，判断步骤2)中是否将韵母中的r，n，g错误大写，有则使用lower()替换回小写；

4) 建立rep字典，判断步骤2)中是否将翘舌音声母中的h错误大写，有则替换回小写；

5) r，n，g既可以作为韵母的结尾，也可以作为声母，故需要判断后一个字母是否为smlist列表中的元素，是则表示此处的r，n，g为韵母的结尾，保持小写，否则表示此处的r，n，g为声母，替换为大写；

6) 使用正则表达式以空格分隔汉字和拼音；

7) 使用split()以空格为分割符分割字符串得到与原文本顺序一致、以单个汉字及单个拼音为元素的detected列表。

后续的敏感词检测过滤操作使用处理后的detected列表，可以直接将列表元素与敏感词树的节点进行匹配，提高匹配的准确性，匹配拼音节点时还可以提高匹配速度，减少匹配时间。

3.6. 敏感词过滤算法

使用上述算法完成词树构建和文本的预处理，根据敏感词树的结构，对处理后的文本进行敏感词检测过滤，将检测到的敏感词用符号“*”进行替换，检测算法基于DFA匹配模式，采用最小匹配规则。

具体算法如下：

1) 定义matched_word_list列表存放匹配到的完整的敏感词；now_map表示构建的敏感词树；begin_index表示检测的起始位置，初始值为0；flag表示是否检测到完整的敏感词，初始值为False；tmp_flag表示detected列表中匹配到的元素个数，初始值为0；length表示detected列表长度；i表示当前detected列表元素位置 $\left(0\le \text{i}\le \text{length}\right)$。从detected列表的第一个元素开始执行以下操作，直到最后一个元素执行完成；

2) 获取detected列表的第i个元素detected[i]，now_map.get(detected[i].lower())判断敏感词树上是否存在该节点，不存在则tmp_flag = 0，begin_index = begin_index + 1，继续执行步骤2)，存在则now_map = now_map.get(detected[i])指向该节点，tmp_flag = tmp_flag + 1，判断该节点是否为敏感词结束节点，否则继续执行步骤2)，是则flag = True，将detected列表从detected[begin_index]开始切片，长度为tmp_flag，使用join()转换成字符串格式，添加进列表matched_word_list，begin_index = begin_index + tmp_flag；

3) 重复上述操作直至检测完成，得到匹配到的敏感词列表matched_word_list，列表中元素的顺序与文本中敏感词的顺序一致；

4) 根据matched_word_list列表，将去除掉无关字符的文本中的敏感词使用replace(num = 1)替换为相同长度的“*”字符串，得到过滤后的文本result_txt。

4. 实验及结果分析

4.1. 实验

在网络上随机选取一段文本并随机插入不同数量的中文敏感词、无关字符干扰、中文拼音混合敏感词以及两种干扰方式混合的敏感词，然后使用本文提出的算法对该文本进行检测过滤。

本文实验使用的原始中文敏感词库为Github提供的开源中文敏感词库，先对词库进行去重，得到的无重复的中文敏感词库内共有1140个敏感词，其中暴恐类164个，色情类305个，政治宗教类336个，虚假广告类251个，脏话类84个。

使用本文提出的算法进行实验：1) 对中文敏感词库进行扩充得到中拼混合敏感词库；2) 构建敏感词树；3) 预处理待检测文本；4) 敏感词检测过滤。实验结果见图5、表1、表2。

4.2. 实验结果分析

本文提出的敏感词过滤算法能够检测过滤长度较短、敏感词的数量长度较小的文本，也能够检测过滤长度较长、敏感词的数量长度较大的文本，即适用于文本长度以及敏感词长度数量不确定的情况。

由上述实验可知，本文提出的敏感词过滤算法对中文敏感词以及干扰“伪装”后的敏感词均有较好的过滤效果且并不会破坏文本中的对非敏感内容。

使用本文算法对含有不同数量的带有干扰的敏感词的文本的进行实验时，由表2的数据可知，文本较短且包含敏感词数量较少时，算法的查全率和准确率可以达到100%，当待检测文本字符数以及所包含的敏感词数增大时，准确率维持在100%，查全率稍有降低，在最极端即文本内容全为敏感词的情况下，本文算法的查全率为95.3%，故在其他情况下本文算法的查全率要高于95.3%。

Figure 5. Results of sensitive word filtering experiment

图5. 敏感词过滤实验结果

Table 1. Experimental results of vocabulary expansion and word tree construction

表1. 词库扩充和词树构建实验结果

Table 2. Results of sensitive word filtering experiment

表2. 敏感词过滤实验结果

4.3. 算法复杂度分析

1) 中文拼音敏感词库扩充算法的时间复杂度。

本文中文拼音敏感词库扩充算法原理为排列组合，其时间复杂度与原始中文敏感词库中敏感词个数和长度有关，即时间复杂度为 $O\left(n\times 2^{\overline{len}}\right)$，其中 $n$ 为原始中文敏感词库中敏感词个数， $\overline{len}$ 为原始中文敏感词库中敏感词的平均长度。

2) 敏感词树构建算法的空间复杂度。

本文使用字典树结构构建敏感词树，构建时将整个拼音看作一个字符存储在一个节点中，如图6，对比原始存储方式能够进一步节省存储空间，降低空间复杂度。

Figure 6. Comparison of branch structure of sensitive word tree

图6. 敏感词树分支结构对比

本文敏感词树构建算法的空间复杂度为 $O\left(N\times L\right)$ [10]，其中 $N$ 为敏感词树节点数量， $L$ 为节点长度。

3) 敏感词树构建算法的时间复杂度。

由于单个拼音存储在一个节点中，本文敏感词树构建算法的时间复杂度为 $O\left(n^{\prime }\times \overline{le{n}^{\prime }}\right)$，其中 $n^{\prime }$ 为中文拼音混合敏感词库中敏感词个数， $\overline{le{n}^{\prime }}$ 为敏感词的平均长度。

4) 敏感词过滤算法的时间复杂度。

本文敏感词过滤算法的检测过滤时间与待检测文本的长度有关，即时间复杂度为 $O\left(l\right)$，其中 $l$ 为待检测文本长度。

5. 结论

本文针对当前网络上通过各种干扰形式“伪装”的敏感词，提出了一种基于DFA的中拼混合敏感词过滤算法，扩充了原始中文敏感词库使得词库更加完善便于算法进行后续工作；对文本长度以及敏感词长度数量没有要求，能够有效地对检测文本中的中文敏感词以及干扰“伪装”后的敏感词进行检测过滤，且不会破坏文本中的非敏感内容，解决了一般的系统过滤方法难以成功检测过滤干扰“伪装”后的敏感词的问题；算法复杂度较低满足实际应用需求。

参考文献