Last-Modified:2019-05-1015:25:35参考文章c++使用map实现Trie树关键词过滤扩展，用于检测某段中是否出现敏感词正文，基于Double-ArrayTrie树实现↑现成的php扩展，并支持php5、php7从Trie到DoubleArrayTrie↑深入浅出前缀树匹配DoubleArrayTrietrie_filter扩展+swoole实现敏感词过滤↑简单高-后台项目中php的性能实现需要对用户发送的聊天文本进行过滤。由于有将近20000个敏感词，如果用str_replace来处理，就会被炸掉。我是在网上了解到的。在性能要求不高的情况下，可以自己构造一颗Trie树（字典树）。这就是这篇文章的由来。Trie树是一种搜索树，也叫词典树、词搜索树。DFA可以理解为DFA（DeterministicFiniteAutomaton），也就是这里借用一张图来解释Trie树的结构：Trie可以理解为确定有限状态自动机，即DFA。在Trie树中，每个节点代表一个状态，每条边代表一个字符，从根节点到叶节点的边代表一个条目。查找一个条目所花费的最长时间只受条目长度的影响，所以Trie的搜索性能非常高，可以与哈希算法相媲美。上面其实保存了abcdabdbbcdefghij的特点：只保存一份所有条目的公共前缀，只需要一份待检测的文本。搜索时间只与待检测文本的长度有关，与字典大小无关。使用数组存储树形结构，以下面的敏感词词典为例：大傻大傻↑内容纯属举例……游戏聊天日常屏蔽内容存储为{"big":{"stupid":{"end":true"Sub":{"end":true}}},"Silly":{"Sub":{"end":true},}}对于其他更简单的语言，你可以考虑使用HashMap之类的实现或者参考这篇文章，使用Four-ArrayTrie，Triple-ArrayTrie和Double-ArrayTrie结构来设计（名称与内部使用的数组个数有关）字符串切分是否是构建字典树或者过滤敏感文本需要拆分的时候，需要考虑unicode字符有一个简单的方法：$str="astupid123";//要拆分的文本$arr=preg_split("//u",$str,-1,PREG_SPLIT_NO_EMPTY);//拆分文本//输出数组(6){[0]=>string(1)"a"[1]=>string(3)"stupid"[2]=>string(3)"egg"[3]=>string(1)"1"[4]=>string(1)"2"[5]=>string(1)"3"}匹配规则需要加u修饰符，/u表示根据unicode(utf-8)（主要针对汉字等多字节字符），否则无法正常工作，如下例子↓$str="astupid123";//要拆分的文本$arr=preg_split("//",$str,-1,PREG_SPLIT_NO_EMPTY);//拆分文本//array(10){[0]=>字符串(1)"a"[1]=>字符串(1)"?"[2]=>字符串(1)"?"[3]=>字符串(1)"?"[4]=>string(1)"?"[5]=>string(1)"?"[6]=>string(1)"?"[7]=>string(1)"1"[8]=>string(1)"2"[9]=>string(1)"3"}示例代码php构建：1.分割敏感词2.将分割的次数一一添加到树中使用：分割单词和句子待处理的Trie树的根节点开始匹配classSensitiveWordFilter{protected$dict;受保护的$dictFile；/***@paramstring$dictFile字典文件路径，每行一句话*/publicfunction__construct($dictFile){$this->dictFile=$dictFile;$this->dict=[];}publicfunctionloadData($cache=true){$memcache=newMemcache();$内存缓存->pconnect("127.0.0.1",11212);$cacheKey=__CLASS__。“_”。md5($this->dictFile);if($cache&&false!==($this->dict=$memcache->get($cacheKey))){返回;}$this->loadDataFromFile();如果（$cache）{$memcache->set($cacheKey,$this->dict,null,3600);}}/***从文件中加载字典数据，构建trie树*/publicfunctionloadDataFromFile(){$file=$this->dictFile;if(!file_exists($file)){thrownewInvalidArgumentException("字典文件不存在");}$handle=@fopen($file,"r");if(!is_resource($handle)){thrownewRuntimeException("字典文件无法打开");}while(!feof($handle)){$line=fgets($handle);如果（空（$line））{继续；}$this->addWords(trim($line));}fclose($handle);}/***拆分文本（注意ascii占1字节，unicode...）**@paramstring$str**@returnstring[]*/protectedfunctionsplitStr($str){returnpreg_split("//u",$str,-1,PREG_SPLIT_NO_EMPTY);}/***添加语句到字典树**@param$wordArr*/protectedfunctionaddWords($words){$wordArr=$this->splitStr($words);$curNode=&$this->dict;foreach($wordArras$char){如果(!isset($curNode)){$curNode[$char]=[];}$curNode=&$curNode[$char];}//将当前节点的完整路径标记为“敏感词”$curNode['end']++;}/***过滤文本**@paramstring$str原始文本*@paramstring$replace敏感词替换字符*@paramint$skipDistance严格：检测时允许跳过的区间**@returnstring返回过滤后的字符串text*/publicfunctionfilter($str,$replace='*',$skipDistance=0){$maxDistance=max($skipDistance,0)+1;$strArr=$this->splitStr($str);$length=count($strArr);对于($i=0;$i<$length;$i++){$char=$strArr[$i];如果(!isset($this->dict[$char])){继续；$curNode=&$this->dict[$char];$距离=0；$matchIndex=[$i];对于($j=$i+1;$j<$length&&$dist<$maxDistance;$j++){if(!isset($curNode[$strArr[$j]])){$dist++;继续;}$matchIndex[]=$j;$curNode=&$curNode[$strArr[$j]];}//匹配if(isset($curNode['end'])){//Log::Write("match");foreach($matchIndexas$index){$strArr[$index]=$replace;}$i=max($matchIndex);}}返回implode('',$strArr);}/***确认给定的句子是否为敏感词**@param$strArr**@returnbool|mixed*/publicfunctionisMatch($strArr){$strArr=is_array($strArr)?$strArr:$this->splitStr($strArr);$curNode=&$this->dict;foreach($strArras$char){if(!isset($curNode[$char])){返回假；}}//返回$curNode['end']??错误的;//php7返回isset($curNode['end'])?$curNode['结束']：假；}}词典文件示例：敏感词1敏感词2敏感词3...示例：$filter=newSensitiveWordFilter(PATH_APP.'/config/dirty_words.txt');$filter->loadData()$filter->filter("Test123Text",'*',2)优化缓存字典树原始敏感词文件大小：194KB（约20647行）生成字典树后占用内存（约）:7MB构建字典树耗时：140ms+!!!php内存占用这一点...先把构建字典树耗时，可以优化：缓存！由于php脚本不是常驻内存类型，每次有新的请求过来，都需要构建字典树。我们将生成好的字典树数组缓存（memcached或redis），在后续请求中每次都从缓存中读取，可以大大提高性能。经过测试，构建字典树的时间从140ms+减少到6ms以内。注意：memcached会自动将缓存的数组序列化（serialize），取出时自动反序列化（unserialize）。如果是redis，需要手动，上面生成的Trie数组序列化后可以选择json访问字符长度：serialize:426KBjson:241KB提示：因此如果整个字典过大，导致超出大小限制memcached中存储单个值（默认1M），可以考虑手动json序列化数组然后保存。↑...刚刚发现memcache在存值的时候提供了压缩功能，可以考虑如果常驻服务作为常驻内存服务独立过滤敏感词功能，构建字典树的过程只需要做一次，后面的值需要处理过滤文本的请求。如果是PHP，可以考虑使用Swoole，因为项目目前的敏感词词库只有2W左右，访问瓶颈不在这里，所以暂时采用上面的方案。ab测试时，单词词库达百万，那估计得考虑做成常驻内存的服务了。这里有一篇文章测试了Swoole(swoole_http_server)+trie-filter扩展的使用，词汇量200W
