溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
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制作搜索聯想功能的方法了，如果您也有類似的疑惑，不妨參照上述方法進行嘗試。如果想了解更多相關內容，請關注億速云行業資訊。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
