这篇文章主要讲解了“php如何使用前缀树实现关键词查找 ”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“php如何使用前缀树实现关键词查找 ”吧！
之前旧的php系统有一个关键词查找和敏感词过滤的功能，直接使用了如下代码实现，
foreach ($words as $word){
if(strrpos($content, $word) !== false){
$tags[] = $word;
}
}随着关键词增多，性能上有点拖后腿，一直想优化一下性能。
刚好从网上看到一个比较简单的java版本"利用利用字典树（前缀树）过滤敏感词"(https://blog.csdn.net/qq_37050329/article/details/84276344)的算法文章，感觉按这算法实现可以提升性能。
php第一个版本前缀树过滤迅速实现：
<?php
class Words{
/**
* true 关键词的终结 ； false 继续
*/
private $end = false;
/**
* key下一个字符，value是对应的节点
*/
private $subNodes = array();
/**
* 向指定位置添加节点树
*/
public function addSubNode($key, $node) {
$this->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个。
旧处理方式性能
<?php
function microtime_float()
{
list($usec, $sec) = explode(" ", microtime());
return ((float)$usec + (float)$sec);
}
function readFileByLine ($filename)
{
$words = array();
$fh = fopen($filename, 'r');
while (! feof($fh)) {
$line = fgets($fh);
$words[] = trim($line);
}
fclose($fh);
return $words;
}
function getHtml($url){
$opts = array(
'http'=>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第一个版本前缀树性能
<?php
$content = getHtml('http://baijiahao.baidu.com/s?id=1637904839202713990');
var_dump(strip_tags($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";
//耗时：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如何使用前缀树实现关键词查找 这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
