不超过 20 行，搞定关键词屏蔽功能！
众所周知，前两天刷爆程序员朋友圈的思否网站无法访问问题被放大了 N 倍。按说，思否的架构师也是非常厉害的大牛，但是在关键词屏蔽功能上偷了懒，也很可能当初就没设计过这个功能，给遗漏了。
互联网在方便我们的同时，也成为了不法之徒的“法外之地”。所以关键词屏蔽功能是所有网站都急迫需要的一个功能，本文我们就一起来设计一个关键词屏蔽功能。
DFA敏感词过滤算法
敏感词过滤必不可少的就是敏感词库，我们需要一个包含了大量敏感词的词库来匹配鉴别敏感词。而最简单的办法就是把需要检测的文本里的词汇和词库里的词一一匹配，如果有相同的词，就证明有敏感词存在。
但是敏感词库一般很大，包含几万个敏感词，如果每个词都进行一一匹配，效率会极其的低下。为了提高效率，我们可以用DFA的过滤算法。在实现文字过滤的算法中，DFA是比较好的实现算法。
什么是DFA呢？DFA即Deterministic Finite Automaton，也就是确定有穷自动机。DFA主要由state(状态)和event(事件)构成。它是通过event和当前的state得到下一个state，即event+state -> next state。
上图中的“自动机”就是一个DFA，S, U, V, P就是我们提到的State（状态），而state之间的单向箭头就是Event(事件). 通过S我们可以查找到U和V，又可以从U查找到V和P，从V处查找到U和P. 用更实际一些的例子来看，比如我们的敏感词词库中有“炸鸡腿”和“炸鸡翅中”，则通过“炸”字我们可以查找到“鸡”，又可以通过“鸡”字查找到“腿”和“翅”，最后可以通过“翅”查找到“中”。图示如下：
以这样的方式，我们可以将敏感词库转化成一颗一颗的树。这样当我们匹配敏感词时，只需要通过第一个字来寻找相应的树，大大的减少了检索的范围。用更加直观的例子来表现的话，比如敏感词库内有十个词，分别是：AA,AB,AC,AD,BA,BB,BC,CC,DD,DE. 当我们判别词语FF是不是敏感词的时候，如果用最简单的线性匹配，我们需要用FF和这十个词一一配对，总共要进行10次匹配，但是如果用DFA算法，我们只需要匹配首字母，也就是分别用首字母’F’去匹配A,B,C,D, 一共四次，极大的加快了我们的过滤速度，减少匹配时间。
下面我已Java中的HashMap为例来实现DFA算法。具体过程如下：
以“炸鸡腿，炸鸡翅中”为我们例子中的敏感词库。
1、在hashMap中查询“炸”看其是否在hashMap中存在，如果不存在，则证明已“炸”开头的敏感词还不存在，则我们直接构建这样的一棵树。跳至3。
2、如果在hashMap中查找到了，表明存在以“炸”开头的敏感词，设置hashMap = hashMap.get(“炸”)，跳至1，依次匹配“鸡”、“腿”。
3、判断该字是否为该词中的最后一个字。若是表示敏感词结束，设置标志位isEnd = 1，否则设置标志位isEnd = 0。
流程图如下：
具体的用代码构建思路如下：
创建完敏感词树以后，检索过程无非就是HashMap的get实现，找到就证明该词为敏感词，否则不为敏感词。
语义相似度
在DFA算法的帮助下，我们可以以一个较高的效率鉴别敏感词。但是敏感词库毕竟是一个有限的集合，不可能包含所有的敏感词。比如我们的词库里只有“赌博”而没有赌场，中国澳门很多线上赌场”就会躲过我们的火眼金睛。这样的场景下，我们就需要语义相似度来帮助我们识别这些漏网之鱼。
语义相似度，顾名思义就是用一个[0, 1]的数字来展现两个词语之间的相似性、关联性，以达到筛选敏感词的目的并加以屏蔽。但是语义相似度的作用远不止于此。语义相似度计算在自然语言处理、智能检索、文本聚类、文本分类、自动应答、词义排歧和机器翻译等领域都有着广泛的应用，是自然语言处理(NLP)的基础研究课题。
NLP (Natural Language Processing) 是人工智能里的一个热门领域，同时也是最为困难的一个领域。NLP是计算机基于深度学习以一种聪明而有用的方式分析，理解和从人类语言中获取意义的一种方式。NLP涵盖了非常多的子领域：语音识别（Speech recognition），句法分析（Parsing），机器翻译（Machine translation），问答系统（Question answering）等等。而语义相似度同样也是NLP中非常重要的一个主题。
目前，国内外语义相似度计算的一个重要方法就是基于语义词典的词语相似度计算。举例来说，英文方面比较有代表性有 WordNet, FrameNet, MindNet等；在汉语方面，有同义词词林、“知网”(HowNet)、“中文概念词典”(CCD: Chinese Concept Dictionary)等。
除此之外，字面编辑距离法也是一个计算语义相似度的方法。
词林编码法相似度
01
顾名思义，词林编码法是基于《同义词词林》，通过计算两个词语的词林编码以及它们在词林中的路径结构来计算相似度。同义词词林按照树状的层次结构把所有收录的词条组织到一起。这些词根据语义的远近和相关性分成了若干个词群（段落），每个段落中的词语又进一步分成了很多行。同一行的词语要么语义相同，要么词义有很强的相关性。例如，“西红柿”和“番茄”在同一行，因为这两个词同义。“大豆”、“毛豆”和“黄豆”在同一行，因为这些词词义相近。
编码部分，同义词词林共提供了5层编码，来展示词语在词林树结构中的具体位置。第一级用大写英文字母表示；第二级用小写英文字母表示；第三级用二位十进制整数表；第四级用大写英文字母表示；第五级用二位十进制数表示。具体的编码含义如下表所示：
由于第五级有的行是同义词，有的行是相关词，分类结果需要单独说明。于是我们在编码最后用三个不同的符号’=’, ‘#’, ‘@’ 区分。’=’代表用同义词， ‘#’代表有相关词，‘@’表示无同义词和相关词。
而在同义词词林编码法中，一般用词语间的语义距离衡量词语的相似度。具体地说，词语距离是一个[0,∞)的实数。一个词语与其本身的距离为0.两个词语的距离越小，相似度越高，距离越大，相似度越低。
而同义词词林将所有的词组织几棵树状的层次结构中。我们知道，在一棵树形图中，任何两个结点之间有且只有一条路径。于是，这条路径的长度就可以作为这两个概念的语义距离的一种度量。
知网词语相似度
02
《知网》是一部比较详尽的语义知识词典。不过，由于《知网》中对于一个词的语义采用的是一种多维的知识表示形式，这给词语相似度的计算带来了麻烦。这一点与WordNet和《同义词词林》不同。在WordNet和《同义词词林》中，所有同类的语义项（WordNet的synset或《同义词词林》的词群）构成一个树状结构，要计算语义项之间的距离，只要计算树状结构中相应结点的距离即可。
而在《知网》中，是用“概念”来对汉语中的每一个词语进行描述和定义的，而构成这种概念描述语言的核心词汇就是“义原”。但是每一个词拥有着多个义原，而且义原之间并不平等，它们之间有着复杂的关系，通过一种专门的知识描述语言来表示。这给相似度的计算带来了极大的难度。
鉴于之前提到的原因，知网的相似度计算方法有所不同。在该种方法下，词语的相似度体现为描述词语的概念之间的相似度。
对于两个汉语词语W1和W2，如果W1有n个义项（概念）：S11，S12，……，S1n，W2有m个义项（概念）：S21，S22，……，S2m，我们规定，W1和W2的相似度各个概念的相似度之最大值，也就是说：
这样，我们就把两个词语之间的相似度问题归结到了两个概念之间的相似度 问题。
字面编辑距离法
03
编辑距离，又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数，如果它们的距离越大，说明它们越是不同。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
而在汉语中，我们则需要计算词语的拼音之间的编辑距离，来得出词语之间的相似度。
概况来说，词林编码法关注词语之间的语义和词义的相关性，知网是利用词语所包含义原的距离来计算相似度，而字面编辑距离法则计算由一个词语的拼音转变成另一个词语所需要的步骤及繁琐度。
Github上有一个用Java实现的语义相似度计算工具包：https://github.com/shibing624/similarity
该工具包包含了上面提到的三种语义相似度的计算方法。具体的使用方式也很简单。首先我们可以在Maven项目中添加依赖，如下图所示：
在dependencies中添加一个新的dependency。
之后的使用方法也极其简单，只需要导入similarity包，调用相应的方法即可。
以“教师”和“教授”举例，用以上三种计算语义相似度的方法来分别计算：
01
词林编码法
代码：
结果：
02
知网
代码：
结果：
03
字面编辑距离法
代码：
结果：
