搜索聯想功能是各大搜索引擎具備的基礎功能，如下圖所示，這個功能簡化了用戶的輸入行為，并且能夠給用戶推薦熱門的搜索詞，下面我們來講一下如何用php實現搜索聯想的功能。
實現原理
搜索聯想功能拆解一下由兩部分組成
1、給定一個查詢詞，找出以他為前綴的其他目標查詢詞
2、對目標查詢詞進行排序，選出權重高的若干個查詢詞
本篇中重點講解一下第一部分的實現，這里使用Trie樹，也叫字典樹，這個數據結構來解決這個問題。通過Trie樹可以很方便快速的找到已該字符串為前綴的目標字符串。
什么是Trie樹
Trie樹，即字典樹，又稱單詞查找樹或鍵樹，是一種樹形結構，是一種哈希樹的變種。典型應用是用于統計和排序大量的字符串（但不僅限于字符串），所以經常被搜索引擎系統用于文本詞頻統計。它的優點是：最大限度地減少無謂的字符串比較，查詢效率往往比哈希表高。
Trie的核心思想是空間換時間。利用字符串的公共前綴來降低查詢時間的開銷以達到提高效率的目的。
它有3個基本性質：
1、根節點不包含字符，除根節點外每一個節點都只包含一個字符。
2、從根節點到某一節點，路徑上經過的字符連接起來，為該節點對應的字符串。
3、每個節點的所有子節點包含的字符都不相同。
假如我們有如下字符串
hello，hi，today，touch，weak
那么構造出來的Trie樹如下圖所示
當查詢的時候只需要從根開始按字符沿著樹進行深度遍歷，就可以把已該詞為前綴的其他查詢詞查找出來。
代碼實現
用于實現搜索聯想功能的核心方法有兩個：
1、將查詢詞的數據集構建成Trie樹
2、查找以某個查詢詞為前綴的所有查詢詞
第一步：構建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實現搜索聯想功能（基于字典樹算法）的詳細內容，希望對大家有所幫助。
