PHP实现搜索联想功能（基于字典树算法）-php教程

完成原理

搜寻联想性能拆解一下由两局部组成

一、给定一个查问词，找出以他为前缀的其余指标查问词

二、对指标查问词进行排序，选出权重高的若干个查问词

本篇中重点解说一下第一局部的完成，这里应用Trie树，也叫字典树，这个数据构造来处理这个成绩。经过Trie树能够很不便疾速的找到已该字符串为前缀的指标字符串。

甚么是Trie树

Trie树，即字典树，又称单词查找树或键树，是一种树形构造，是一种哈希树的变种。典型使用是用于统计以及排序年夜量的字符串（但不只限于字符串），以是常常被搜寻引擎零碎用于文本词频统计。它的优点是：最年夜限制地缩小无谓的字符串比拟，查问效率往往比哈希表高。

Trie的外围思维是空间换工夫。行使字符串的公共前缀来升高查问工夫的开支以达到进步效率的目的。

它有3个根本性子：

一、根节点没有蕴含字符，除了根节点外每个节点都只蕴含一个字符。

二、从根节点到某一节点，门路上通过的字符衔接起来，为该节点对应的字符串。

三、每一个节点的一切子节点蕴含的字符都没有相反。

如果咱们有以下字符串

hello，hi，today，touch，weak

那末结构进去的Trie树以下图所示

当查问的时分只要要从根开端按字符沿着树进行深度遍历，就能够把已该词为前缀的其余查问词查找进去。

代码完成

用于完成搜寻联想性能的外围办法有两个：

一、将查问词的数据集构建成Trie树

二、查找以某个查问词为前缀的一切查问词

第一步：构建Trie树

留意因为一个字符串有中文有英文，以是对每一个字符串应用如下代码进行了宰割，将字符串转化成为了一个字符的数组

$charArray = preg_split('/(?<!^)(?!$)/u', $str);

而后对每一个字符串执行addWordToTrieTree办法，这个办法将一个词退出到Trie树中，这里用到了递归的办法

    public function buildTrieTree($strList) {
        $tree = [];
        foreach($strList as $str) {
            $charArray = preg_split('/(?<!^)(?!$)/u', $str); 
            $tree = $this->addWordToTrieTree($charArray, $tree);
        }
        return $tree;
    }
    public function addWordToTrieTree($charArray, $tree) {
        if (count($charArray) == 0) {
            return [];
        }
        $char = $charArray[0];
       
        $leftStr = array_slice($charArray, 1);
        $tree[$char] = $this->addWordToTrieTree($leftStr, $tree[$char]);
        
        return $tree;
    }

第二步：查问前缀词

查问前缀词即给定一个字符串，查问树中一切以该串为前缀的字符串，也就是联想的进程。

起首挪用findSubTree办法，从Trie中找到该前缀所正在的子树，而后挪用traverseTree办法，遍历这颗子树，把一切的字符串都提掏出来，这里也是用了递归的办法。

public function queryPrefix($prefix) {
        $charArray = preg_split('/(?<!^)(?!$)/u', $prefix);
        $subTree = $this->findSubTree($charArray, $this->tree);
        
        $words = $this->traverseTree($subTree);
        
        foreach($words as &$word) {
            $word = $prefix . $word;
        }
        return $words;
    }
    public function findSubTree($charArray, $tree) {
        foreach($charArray as $char) {
            if (in_array($char, array_keys($tree))) {
                $tree = $tree[$char];
            } else {
                return [];
            }
        }
        return $tree;
    }
    public function traverseTree($tree) {
        $words = [];
        foreach ($tree as $node => $subTree) {
            if (empty($subTree)) {
                $words[] = $node;
                return $words;
            }
            
            $chars = $this->traverseTree($subTree);
            foreach($chars as $char) {
                $words[] = $node . $char;
            }
        }
        return $words;
    }

代码与测试后果

完好代码：

<?php
class TrieTree {
    private $tree;
    public function __construct($strList) {
        $this->tree = $this->buildTrieTree($strList);
    }
    public function queryPrefix($prefix) {
        $charArray = preg_split('/(?<!^)(?!$)/u', $prefix);
        $subTree = $this->findSubTree($charArray, $this->tree);
        
        $words = $this->traverseTree($subTree);
        
        foreach($words as &$word) {
            $word = $prefix . $word;
        }
        return $words;
    }
    public function findSubTree($charArray, $tree) {
        foreach($charArray as $char) {
            if (in_array($char, array_keys($tree))) {
                $tree = $tree[$char];
            } else {
                return [];
            }
        }
        return $tree;
    }
    public function traverseTree($tree) {
        $words = [];
        foreach ($tree as $node => $subTree) {
            if (empty($subTree)) {
                $words[] = $node;
                return $words;
            }
            
            $chars = $this->traverseTree($subTree);
            foreach($chars as $char) {
                $words[] = $node . $char;
            }
        }
        return $words;
    }
    /**
     * 将字符串的数组构建成Trie树
     *
     * @param [array] $strList
     * @return void
     */
    public function buildTrieTree($strList) {
        $tree = [];
        foreach($strList as $str) {
            $charArray = preg_split('/(?<!^)(?!$)/u', $str); 
            $tree = $this->addWordToTrieTree($charArray, $tree);
        }
        return $tree;
    }
    /**
     * 把一个词退出到Trie树中
     *
     * @param [type] $charArray
     * @param [type] $tree
     * @return void
     */
    public function addWordToTrieTree($charArray, $tree) {
        if (count($charArray) == 0) {
            return [];
        }
        $char = $charArray[0];
       
        $leftStr = array_slice($charArray, 1);
        $tree[$char] = $this->addWordToTrieTree($leftStr, $tree[$char]);
        
        return $tree;
    }
    public function getTree() {
        return $this->tree;
    }
}
$strList = ['春风十里','春天正在那里','一百万个可能','一千年当前','起初','起初的咱们','春天里','后会无期'];
$trieTree = new TrieTree($strList);
print_r($trieTree->getTree());
$prefix = '春';
$queryRes = $trieTree->queryPrefix($prefix);
print_r($queryRes);

将’春风十里’,‘春天正在那里’,‘一百万个可能’,‘一千年当前’,‘起初’,‘起初的咱们’,‘春天里’,'后会无期’这些歌名作为数据集，构建一个Trie树并进行测试。

能够看到输入如下后果

Trie树：

Array
(
    [春] => Array
        (
            [风] => Array
                (
                    [十] => Array
                        (
                            [里] => Array
                                (
                                )
                        )
                )
            [天] => Array
                (
                    [正在] => Array
                        (
                            [哪] => Array
                                (
                                    [里] => Array
                                        (
                                        )
                                )
                        )
                    [里] => Array
                        (
                        )
                )
        )
    [一] => Array
        (
            [百] => Array
                (
                    [万] => Array
                        (
                            [个] => Array
                                (
                                    [可] => Array
                                        (
                                            [能] => Array
                                                (
                                                )
                                        )
                                )
                        )
                )
            [千] => Array
                (
                    [年] => Array
                        (
                            [以] => Array
                                (
                                    [后] => Array
                                        (
                                        )
                                )
                        )
                )
        )
    [后] => Array
        (
            [来] => Array
                (
                    [的] => Array
                        (
                            [我] => Array
                                (
                                    [们] => Array
                                        (
                                        )
                                )
                        )
                )
            [会] => Array
                (
                    [无] => Array
                        (
                            [期] => Array
                                (
                                )
                        )
                )
        )
)

查问以“春为前缀的字符串”

Array
(
    [0] => 春风十里
    [1] => 春天正在那里
    [2] => 春天里
)

以上就是PHP完成搜寻联想性能（基于字典树算法）的具体内容，更多请存眷资源魔其它相干文章！