php如何使用前缀树实现关键词查找

这篇文章主要讲解了"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第一个版本前缀树过滤迅速实现：

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如何使用前缀树实现关键词查找 这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是，小编将为大家推送更多相关知识点的文章，欢迎关注！