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://azwzsj.com/article/pppchh.html
