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实现搜索联想功效（基于字典树算法）的具体内容，更多请关注百分百源码网其它相关文章！
