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實現搜尋聯想功能（基於字典樹演算法）的詳細內容，更多請關注TW511.COM其它相關文章！