[转载]敏感词过滤，PHP实现的Trie树

renran421

　　原文地址：http://blog.11034.org/2012-07/trie_in_php.html
　　
　　项目需求，要做敏感词过滤，对于敏感词本身就是一个CRUD的模块很简单，比较麻烦的就是对各种输入的敏感词检测了。用Trie树来实现是比较通用的一种办法吧，之前一直没机会用过这种数据结构，正好试着写了一下。
　　因为用PHP实现，关联数组用的很舒服。第一个要解决的是字符集的问题，如果在Java中就比较好办统一的Unicode，在PHP中因为常用 UTF-8字符集，默认有1-4个字节不同的长度来表示一个字符，于是写了个Util类来将普通的UTF-8字符串转换成字符数组，每一个元素是一个 UTF-8串形成的字符。这一点比较容易实现的，根据UTF-8字符集的格式而来就好。




public static function get_chars($utf8_str){
$s = $utf8_str;
$len = strlen($s);
if($len == 0) return array();
$chars = array();
for($i = 0;$i < $len;$i++){
$c = $s[$i];
$n = ord($c);
if(($n >> 7) == 0){//0xxx xxxx, asci, single
$chars[] = $c;
}
else if(($n >> 4) == 15){ //1111 xxxx, first in four char
if($i < $len - 3){
$chars[] = $c.$s[$i + 1].$s[$i + 2].$s[$i + 3];
$i += 3;
}
}
else if(($n >> 5) == 7){ //111x xxxx, first in three char
if($i < $len - 2){
$chars[] = $c.$s[$i + 1].$s[$i + 2];
$i += 2;
}
}
else if(($n >> 6) == 3){ //11xx xxxx, first in two char
if($i < $len - 1){
$chars[] = $c.$s[$i + 1];
$i++;
}
}
}
return $chars;
}

　　



　　字符单位确认以后，就是写Trie树了。简单的算法，从根路径开始给每个字符建一个关联数组，当字符串结束的时候，用一个null表示结尾。
　　删除一个串，只要找到串中任意一个字符的子元素数量为1，就表示只有这个串了，整个删除就好了；若子元素数量大于1，则继续根据字符找下去，直到末尾的null。
　　查找一个串（完全匹配），一直根据字符找到null为止就表明存在，任一字符不存在就表明串不存在。
　　验证一个长串是否含有任一串，这边算法比较挫，按照每个字符开始都在Trie树种搜索一遍，走的回头路比较多，复杂度有O(n * m)，n为长串长度，m为Trie树深度，不过因为中文Trie树深度很浅，勉强还过得去（英文字符串深度很长）。
　　然后因为PHP没有全局缓存的机制，每次都要从数据库中读取全部的敏感词，然后建立Trie树再去匹配串的话太麻烦了，采取的办法是将Trie内部 的关联数组序列化后直接保存在数据库中，每次只要读取这条数据，然后反序列化，Trie树就回来了。当然进行串的插入和删除，将更新这个序列化数据。
　　可改进的地方：

• 当某一条路径只有这个串即关联数组数量为1时，可以压缩子树
  
• 改进Trie树为AC自动机，即每个节点都添加一个失败指针，指向匹配失败后回到树的哪个节点，这样就仅仅是O(n)的复杂度了。建树的过程比较复杂，对每个插入的串的子串进行处理，运行时查询的效率非常高
  

　　贴代码：



class TrieTree{
public $tree = array();
public function insert($utf8_str){
$chars = &UTF8Util::get_chars($utf8_str);
$chars[] = null;//串结尾字符
$count = count($chars);
$T = &$this->tree;
for($i = 0;$i < $count;$i++){
$c = $chars[$i];
if(!array_key_exists($c, $T)){
$T[$c] = array();//插入新字符，关联数组
}
$T = &$T[$c];
}
}
public function remove($utf8_str){
$chars = &UTF8Util::get_chars($utf8_str);
$chars[] = null;
if($this->_find($chars)){//先保证此串在树中
$chars[] = null;
$count = count($chars);
$T = &$this->tree;
for($i = 0;$i < $count;$i++){
$c = $chars[$i];
if(count($T[$c]) == 1){//表明仅有此串
unset($T[$c]);
return;
}
$T = &$T[$c];
}
}
}
private function _find(&$chars){
$count = count($chars);
$T = &$this->tree;
for($i = 0;$i < $count;$i++){
$c = $chars[$i];
if(!array_key_exists($c, $T)){
return false;
}
$T = &$T[$c];
}
return true;
}
public function find($utf8_str){
$chars = &UTF8Util::get_chars($utf8_str);
$chars[] = null;
return $this->_find($chars);
}
public function contain($utf8_str, $do_count = 0){
$chars = &UTF8Util::get_chars($utf8_str);
$chars[] = null;
$len = count($chars);
$Tree = &$this->tree;
$count = 0;
for($i = 0;$i < $len;$i++){
$c = $chars[$i];
if(array_key_exists($c, $Tree)){//起始字符匹配
$T = &$Tree[$c];
for($j = $i + 1;$j < $len;$j++){
$c = $chars[$j];
if(array_key_exists(null, $T)){
if($do_count){
$count++;
}
else{
return true;
}
}
if(!array_key_exists($c, $T)){
break;
}
$T = &$T[$c];
}
}
}
if($do_count){
return $count;
}
else{
return false;
}
}
public function contain_all($str_array){
foreach($str_array as $str){
if($this->contain($str)){
return true;
}
}
return false;
}
public function export(){
return serialize($this->tree);
}
public function import($str){
$this->tree = unserialize($str);
}
}