php如何使用前缀树实现关键词查找
这篇文章主要讲解了“php如何使用前缀树实现关键词查找 ”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“php如何使用前缀树实现关键词查找 ”吧!
成都创新互联公司专注为客户提供全方位的互联网综合服务,包含不限于网站建设、网站设计、普兰网络推广、微信小程序、普兰网络营销、普兰企业策划、普兰品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等,从售前售中售后,我们都将竭诚为您服务,您的肯定,是我们最大的嘉奖;成都创新互联公司为所有大学生创业者提供普兰建站搭建服务,24小时服务热线:18982081108,官方网址:www.cdcxhl.com
之前旧的php系统有一个关键词查找和敏感词过滤的功能,直接使用了如下代码实现,
foreach ($words as $word){ if(strrpos($content, $word) !== false){ $tags[] = $word; } }
随着关键词增多,性能上有点拖后腿,一直想优化一下性能。
刚好从网上看到一个比较简单的java版本"利用利用字典树(前缀树)过滤敏感词"(https://blog.csdn.net/qq_37050329/article/details/84276344)的算法文章,感觉按这算法实现可以提升性能。
php第一个版本前缀树过滤迅速实现:
subNodes[$key] = $node; } /** * 获取下个节点 */ public function getSubNode($key) { return isset($this->subNodes[$key]) == true ? $this->subNodes[$key] : null; } function isKeywordEnd() { return $this->end; } function setKeywordEnd($end) { $this->end = $end; } } class FilterWords{ //根节点 private $rootNode; function __construct() { $this->rootNode = new Words(); } public function isSymbol($c){ $symbol = array('\t', '\r\n', '\r', '\n', 'amp;', '>','。', '?','!',',','、',';',':','丨','|',':','《','》','“','”', '.',',',';',':','?','!',' ',' ','(',')' ); if(in_array($c, $symbol)){ return true; } else{ return false; } } /** * 过滤敏感词 */ function filter($text) { $mblen = mb_strlen($text); if ($mblen == 0) { return null; } $tempNode = $this->rootNode; $begin = 0; // 回滚数 $position = 0; // 当前比较的位置 $tagBuffer = array(); $tempBuffer = ""; while ($position < $mblen) { $c = mb_substr($text, $position, 1); //特殊符号直接跳过 if ($this->isSymbol($c)) { if ($tempNode == $this->rootNode) { ++$begin; } ++$position; continue; } $tempNode = $tempNode->getSubNode($c); // 当前位置的匹配结束 if ($tempNode == null) { // 跳到下一个字符开始测试 $position = $begin + 1; $begin = $position; // 回到树初始节点 $tempNode = $this->rootNode; $tempBuffer = ''; } else if ($tempNode->isKeywordEnd()) { $tempBuffer .= $c; $tagBuffer[] = $tempBuffer; $position = $position + 1; $begin = $position; $tempNode = $this->rootNode; } else { $tempBuffer .= $c; ++$position; } } return $tagBuffer; } /** * 构造字典树 * @param lineTxt */ public function addWord($lineTxt) { $tempNode = $this->rootNode; $mblen = mb_strlen($lineTxt); // 循环每个字节 for ($i = 0; $i < $mblen; ++$i) { $c = mb_substr($lineTxt, $i, 1); // 过滤空格 if ($this->isSymbol($c)) { continue; } $node = $tempNode->getSubNode($c); if ($node == null) { // 没初始化 $node = new Words(); $tempNode->addSubNode($c, $node); } $tempNode = $node; if ($i == mb_strlen($lineTxt) - 1) { $tempNode->setKeywordEnd(true); } } } }
开发完,测试了下,
$filterWords = new FilterWords(); $filterWords->addWord("☺"); $filterWords->addWord("沪伦通"); $filterWords->addWord("中欧"); $tags = $filterWords->filter("????☺????沪伦通首单即将开启 中欧资本融合驶入快车道"); var_dump($tags); 输出: array(3) { [0]=> string(3) "☺" [1]=> string(9) "沪伦通" [2]=> string(6) "中欧" }
性能测试,关键过滤词14600个。
旧处理方式性能
array( 'method'=>"GET", 'header'=>"Accept-Language: zh-CN,zh;q=0.9\r\n" . "User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/74.0.3729.131 Safari/537.36\r\n" ) ); $context = stream_context_create($opts); $file = file_get_contents($url, false, $context); return $file; } $content = getHtml('http://baijiahao.baidu.com/s?id=1637904839202713990'); $content = strip_tags($content); $words = readFileByLine("banned.txt"); $start = microtime_float(); $tags = array(); foreach ($words as $word){ if(strrpos($content, $word) !== false){ $tags[] = $word; } } var_dump($tags); $end = microtime_float(); echo "耗时:$end - $start = ".($end - $start)."\n"; //耗时:1562250442.266 - 1562250441.2643 = 1.0016851425171
第一个版本前缀树性能
addWord($word); } $start = microtime_float(); $tags = $filterWords->filter($content); var_dump($tags); $end = microtime_float(); echo "耗时:$end - $start = ".($end - $start)."\n"; //耗时:1562250499.7439 - 1562250484.4361 = 15.307857036591
使用前缀树的性能比原来strpos慢了10多倍。。。。。。
检查了一翻,怀疑可能是使用mb_substr来把文章分割成字符数组损耗性能利害,在Java中使用统一的Unicode,而在PHP中使用的UTF-8字符集,用1-4个字节不同的长度来表示一个字符,$text[$position]不一定能表示一个完整字符。
增加一个getChars测试方法,先把文本转成字符数组,再把字符数组传到$filterWords->filter($chars)方法,经测试,性能明显比旧的方式好。
public function getChars($lineTxt){ $mblen = mb_strlen($lineTxt); $chars = array(); for($i = 0; $i < $mblen; $i++){ $c = mb_substr($lineTxt, $i, 1, 'UTF-8'); $chars[] = $c; } return $chars; }
这样可以确定前缀树查找算法性能没问题,性能问题是在mb_substr方法上,因些需要改进获取字符的方法。可以通过判断当前字符是多少字节,然后再通过$text[$position]来获取字节拼接成完整字符。
第二个版本优化调整后的前缀树过滤实现:
class FilterWords{ public $rootNode; function __construct() { $this->rootNode = array('_end_'=>false); } public function getChars($lineTxt){ $mblen = mb_strlen($lineTxt); $chars = array(); for($i = 0; $i < $mblen; $i++){ $c = mb_substr($lineTxt, $i, 1, 'UTF-8'); $chars[] = $c; } return $chars; } /** * 构造字典树 * @param $word */ public function addWord($word) { $tempNode = &$this->rootNode; $mblen = mb_strlen($word); // 循环每个字节 for ($i = 0; $i < $mblen; ++$i) { $c = mb_substr($word, $i, 1); if(empty($tempNode[$c]) == true){ $tempNode[$c] = array('_end_'=>false); } $tempNode = &$tempNode[$c]; if ($i == $mblen - 1) { $tempNode['_end_'] = true; } } } function filter($text) { $len = strlen($text); if ($len == 0) { return null; } $tempNode = $this->rootNode; $position = 0; $tags = array(); $temp = ""; while ($position < $len) { $c = $text[$position]; $n = ord($c); if(($n >> 7) == 0){ //1字节 } else if(($n >> 4) == 15 ){ //4字节 if($position < $len - 3){ $c = $c.$text[$position + 1].$text[$position + 2].$text[$position + 3]; $position += 3; } } else if(($n >> 5) == 7){ //3字节 if($position < $len - 2){ $c = $c.$text[$position + 1].$text[$position + 2]; $position += 2; } } else if(($n >> 6) == 3){ //2字节 if($position < $len - 1){ $c = $c.$text[$position + 1]; $position++; } } $tempNode = isset($tempNode[$c]) == true ? $tempNode[$c] : null; // 当前位置的匹配结束 if ($tempNode == null) { $position = $position + 1; // 回到树初始节点 $tempNode = $this->rootNode; $temp = ''; } else if ($tempNode['_end_'] == true) { $temp .= $c; $tags[] = $temp; $temp = ''; $position = $position + 1; $tempNode = $this->rootNode; } else { $temp .= $c; ++$position; } } return $tags; } }
第二个版本前缀树性能:
$content = getHtml('http://baijiahao.baidu.com/s?id=1637904839202713990'); $content = strip_tags($content); var_dump($content); $words = readFileByLine("banned.txt"); $filterWords = new FilterWords(); foreach($words as $word){ $filterWords->addWord($word); } $start = microtime_float(); $tags = $filterWords->filter($content); var_dump($tags); $end = microtime_float(); echo "耗时:$end - $start = ".($end - $start)."\n"; 耗时:1562250534.7054 - 1562250534.6888 = 0.016629934310913
耗时0.016629934310913,比旧方式的耗时1.0016851425171性能提升了一大截。
后期继续调整代码优化。
感谢各位的阅读,以上就是“php如何使用前缀树实现关键词查找 ”的内容了,经过本文的学习后,相信大家对php如何使用前缀树实现关键词查找 这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是创新互联,小编将为大家推送更多相关知识点的文章,欢迎关注!
当前文章:php如何使用前缀树实现关键词查找
分享地址:http://scyanting.com/article/pppchh.html