PHP實作搜尋聯想功能（基於字典樹演算法）
- 藏色散人轉載
- 2020-06-16 14:28:174118瀏覽
搜尋聯想功能是各大搜尋引擎具備的基礎功能，如下圖所示，這個功能簡化了用戶的輸入行為，並且能夠給用戶推薦熱門的搜尋字詞，下面我們來講一下如何用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;
}程式碼與測試結果
完整程式碼：
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實作搜尋聯想功能（基於字典樹演算法）的詳細內容。更多資訊請關注PHP中文網其他相關文章！