PHP怎么制作搜索聯(lián)想功能

PHP怎么制作搜索聯(lián)想功能？相信很多新手小白還沒學(xué)會這個技能，通過這篇文章的總結(jié)，希望你能學(xué)會學(xué)會這個技能。以下資料是實現(xiàn)的步驟。

搜索聯(lián)想功能是各大搜索引擎具備的基礎(chǔ)功能，如下圖所示，這個功能簡化了用戶的輸入行為，并且能夠給用戶推薦熱門的搜索詞。

實現(xiàn)原理

搜索聯(lián)想功能拆解一下由兩部分組成

1、給定一個查詢詞，找出以他為前綴的其他目標(biāo)查詢詞

2、對目標(biāo)查詢詞進行排序，選出權(quán)重高的若干個查詢詞

本篇中重點講解一下第一部分的實現(xiàn)，這里使用Trie樹，也叫字典樹，這個數(shù)據(jù)結(jié)構(gòu)來解決這個問題。通過Trie樹可以很方便快速的找到已該字符串為前綴的目標(biāo)字符串。

什么是Trie樹

Trie樹，即字典樹，又稱單詞查找樹或鍵樹，是一種樹形結(jié)構(gòu)，是一種哈希樹的變種。典型應(yīng)用是用于統(tǒng)計和排序大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計。它的優(yōu)點是：最大限度地減少無謂的字符串比較，查詢效率往往比哈希表高。

Trie的核心思想是空間換時間。利用字符串的公共前綴來降低查詢時間的開銷以達到提高效率的目的。

它有3個基本性質(zhì)：

1、根節(jié)點不包含字符，除根節(jié)點外每一個節(jié)點都只包含一個字符。

2、從根節(jié)點到某一節(jié)點，路徑上經(jīng)過的字符連接起來，為該節(jié)點對應(yīng)的字符串。

3、每個節(jié)點的所有子節(jié)點包含的字符都不相同。

假如我們有如下字符串

hello，hi，today，touch，weak

那么構(gòu)造出來的Trie樹如下圖所示

當(dāng)查詢的時候只需要從根開始按字符沿著樹進行深度遍歷，就可以把已該詞為前綴的其他查詢詞查找出來。

代碼實現(xiàn)

用于實現(xiàn)搜索聯(lián)想功能的核心方法有兩個：

1、將查詢詞的數(shù)據(jù)集構(gòu)建成Trie樹

2、查找以某個查詢詞為前綴的所有查詢詞

第一步：構(gòu)建Trie樹

注意由于一個字符串有中文有英文，所以對每個字符串使用以下代碼進行了分割，將字符串轉(zhuǎn)化成了一個字符的數(shù)組

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

然后對每個字符串執(zhí)行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;
    }

第二步：查詢前綴詞

查詢前綴詞即給定一個字符串，查詢樹中所有以該串為前綴的字符串，也就是聯(lián)想的過程。

首先調(diào)用findSubTree方法，從Trie中找到該前綴所在的子樹，然后調(diào)用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;
    }

代碼與測試結(jié)果

完整代碼：

<?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;
    }
    /**
     * 將字符串的數(shù)組構(gòu)建成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 = ['春風(fēng)十里','春天在哪里','一百萬個可能','一千年以后','后來','后來的我們','春天里','后會無期'];
$trieTree = new TrieTree($strList);
print_r($trieTree->getTree());
$prefix = '春';
$queryRes = $trieTree->queryPrefix($prefix);
print_r($queryRes);

將’春風(fēng)十里’,‘春天在哪里’,‘一百萬個可能’,‘一千年以后’,‘后來’,‘后來的我們’,‘春天里’,'后會無期’這些歌名作為數(shù)據(jù)集，構(gòu)建一個Trie樹并進行測試。

可以看到輸出以下結(jié)果

Trie樹：

Array
(
    [春] => Array
        (
            [風(fēng)] => 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] => 春風(fēng)十里
    [1] => 春天在哪里
    [2] => 春天里
)

上述就是小編為大家分享的PHP制作搜索聯(lián)想功能的方法了，如果您也有類似的疑惑，不妨參照上述方法進行嘗試。如果想了解更多相關(guān)內(nèi)容，請關(guān)注億速云行業(yè)資訊。