溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要講解了“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進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
