当前位置:首页 > PHP教程 > php高级应用 > 列表

PHP实现搜索联想功能(基于字典树算法)

发布:smiling 来源: PHP粉丝网  添加日期:2022-06-30 09:19:26 浏览: 评论:0 
搜索联想功能是各大搜索引擎具备的基础功能,如下图所示,这个功能简化了用户的输入行为,并且能够给用户推荐热门的搜索词,下面我们来讲一下如何用php实现搜索联想的功能。

企业微信截图_15922885713947.png

实现原理

搜索联想功能拆解一下由两部分组成

1、给定一个查询词,找出以他为前缀的其他目标查询词

2、对目标查询词进行排序,选出权重高的若干个查询词

本篇中重点讲解一下第一部分的实现,这里使用Trie树,也叫字典树,这个数据结构来解决这个问题。通过Trie树可以很方便快速的找到已该字符串为前缀的目标字符串。

什么是Trie树

Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率往往比哈希表高。

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

它有3个基本性质:

1、根节点不包含字符,除根节点外每一个节点都只包含一个字符。

2、从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。

3、每个节点的所有子节点包含的字符都不相同。

假如我们有如下字符串

hello,hi,today,touch,weak

那么构造出来的Trie树如下图所示

企业微信截图_15922885809834.png

当查询的时候只需要从根开始按字符沿着树进行深度遍历,就可以把已该词为前缀的其他查询词查找出来。

代码实现

用于实现搜索联想功能的核心方法有两个:

1、将查询词的数据集构建成Trie树

2、查找以某个查询词为前缀的所有查询词

第一步:构建Trie树

注意由于一个字符串有中文有英文,所以对每个字符串使用以下代码进行了分割,将字符串转化成了一个字符的数组

$charArray = preg_split('/(?<!^)(?!$)/u', $str);

然后对每个字符串执行addWordToTrieTree方法,这个方法将一个词加入到Trie树中,这里用到了递归的方法

  1. public function buildTrieTree($strList) { 
  2.  
  3.     $tree = []; 
  4.  
  5.     foreach($strList as $str) { 
  6.  
  7.         $charArray = preg_split('/(?<!^)(?!$)/u'$str);  
  8.  
  9.         $tree = $this->addWordToTrieTree($charArray$tree); 
  10.  
  11.     } 
  12.  
  13.     return $tree
  14.  
  15.  
  16. public function addWordToTrieTree($charArray$tree) { 
  17.  
  18.     if (count($charArray) == 0) { 
  19.  
  20.         return []; 
  21.  
  22.     } 
  23.  
  24.     $char = $charArray[0]; 
  25.  
  26.      
  27.  
  28.     $leftStr = array_slice($charArray, 1); 
  29.  
  30.     $tree[$char] = $this->addWordToTrieTree($leftStr$tree[$char]); 
  31.  
  32.       
  33.  
  34.     return $tree
  35.  

第二步:查询前缀词

查询前缀词即给定一个字符串,查询树中所有以该串为前缀的字符串,也就是联想的过程。

首先调用findSubTree方法,从Trie中找到该前缀所在的子树,然后调用traverseTree方法,遍历这颗子树,把所有的字符串都提取出来,这里也是用了递归的方法。

  1. public function queryPrefix($prefix) { 
  2.  
  3.         $charArray = preg_split('/(?<!^)(?!$)/u'$prefix); 
  4.  
  5.         $subTree = $this->findSubTree($charArray$this->tree); 
  6.  
  7.           
  8.  
  9.         $words = $this->traverseTree($subTree); 
  10.  
  11.           
  12.  
  13.         foreach($words as &$word) { 
  14.  
  15.             $word = $prefix . $word
  16.  
  17.         } 
  18.  
  19.         return $words
  20.  
  21.     } 
  22.  
  23.     public function findSubTree($charArray$tree) { 
  24.  
  25.         foreach($charArray as $char) { 
  26.  
  27.             if (in_array($chararray_keys($tree))) { 
  28.  
  29.                 $tree = $tree[$char]; 
  30.  
  31.             } else { 
  32.  
  33.                 return []; 
  34.  
  35.             } 
  36.  
  37.         } 
  38.  
  39.         return $tree
  40.  
  41.     } 
  42.  
  43.     public function traverseTree($tree) { 
  44.  
  45.         $words = []; 
  46.  
  47.         foreach ($tree as $node => $subTree) { 
  48.  
  49.             if (emptyempty($subTree)) { 
  50.  
  51.                 $words[] = $node
  52.  
  53.                 return $words
  54.  
  55.             } 
  56.  
  57.               
  58.  
  59.             $chars = $this->traverseTree($subTree); 
  60.  
  61.             foreach($chars as $char) { 
  62.  
  63.                 $words[] = $node . $char
  64.  
  65.             } 
  66.  
  67.         } 
  68.  
  69.         return $words
  70.  
  71.     } 

代码与测试结果

完整代码:

  1. <?php 
  2.  
  3. class TrieTree { 
  4.  
  5.     private $tree
  6.  
  7.     public function __construct($strList) { 
  8.  
  9.         $this->tree = $this->buildTrieTree($strList); 
  10.  
  11.     } 
  12.  
  13.     public function queryPrefix($prefix) { 
  14.  
  15.         $charArray = preg_split('/(?<!^)(?!$)/u'$prefix); 
  16.  
  17.         $subTree = $this->findSubTree($charArray$this->tree); 
  18.  
  19.           
  20.  
  21.         $words = $this->traverseTree($subTree); 
  22.  
  23.           
  24.  
  25.         foreach($words as &$word) { 
  26.  
  27.             $word = $prefix . $word
  28.  
  29.         } 
  30.  
  31.         return $words
  32.  
  33.     } 
  34.  
  35.     public function findSubTree($charArray$tree) { 
  36.  
  37.         foreach($charArray as $char) { 
  38.  
  39.             if (in_array($chararray_keys($tree))) { 
  40.  
  41.                 $tree = $tree[$char]; 
  42.  
  43.             } else { 
  44.  
  45.                 return []; 
  46.  
  47.             } 
  48.  
  49.         } 
  50.  
  51.         return $tree
  52.  
  53.     } 
  54.  
  55.     public function traverseTree($tree) { 
  56.  
  57.         $words = []; 
  58.  
  59.         foreach ($tree as $node => $subTree) { 
  60.  
  61.             if (emptyempty($subTree)) { 
  62.  
  63.                 $words[] = $node
  64.  
  65.                 return $words
  66.  
  67.             } 
  68.  
  69.               
  70.  
  71.             $chars = $this->traverseTree($subTree); 
  72.  
  73.             foreach($chars as $char) { 
  74.  
  75.                 $words[] = $node . $char
  76.  
  77.             } 
  78.  
  79.         } 
  80.  
  81.         return $words
  82.  
  83.     } 
  84.  
  85.     /** 
  86.  
  87.      * 将字符串的数组构建成Trie树 
  88.  
  89.      * 
  90.  
  91.      * @param [array] $strList 
  92.  
  93.      * @return void 
  94.  
  95.      */ 
  96.  
  97.     public function buildTrieTree($strList) { 
  98.  
  99.         $tree = []; 
  100.  
  101.         foreach($strList as $str) { 
  102.  
  103.             $charArray = preg_split('/(?<!^)(?!$)/u'$str);  
  104.  
  105.             $tree = $this->addWordToTrieTree($charArray$tree); 
  106.  
  107.         } 
  108.  
  109.         return $tree
  110.  
  111.     } 
  112.  
  113.     /** 
  114.  
  115.      * 把一个词加入到Trie树中 
  116.  
  117.      * 
  118.  
  119.      * @param [type] $charArray 
  120.  
  121.      * @param [type] $tree 
  122.  
  123.      * @return void 
  124.  
  125.      */ 
  126.  
  127.     public function addWordToTrieTree($charArray$tree) { 
  128.  
  129.         if (count($charArray) == 0) { 
  130.  
  131.             return []; 
  132.  
  133.         } 
  134.  
  135.         $char = $charArray[0]; 
  136.  
  137.          
  138.  
  139.         $leftStr = array_slice($charArray, 1); 
  140.  
  141.         $tree[$char] = $this->addWordToTrieTree($leftStr$tree[$char]); 
  142.  
  143.           
  144.  
  145.         return $tree
  146.  
  147.     } 
  148.  
  149.     public function getTree() { 
  150.  
  151.         return $this->tree; 
  152.  
  153.     } 
  154.  
  155.  
  156. $strList = ['春风十里','春天在哪里','一百万个可能','一千年以后','后来','后来的我们','春天里','后会无期']; 
  157.  
  158. $trieTree = new TrieTree($strList); 
  159.  
  160. print_r($trieTree->getTree()); 
  161.  
  162. $prefix = '春'
  163.  
  164. $queryRes = $trieTree->queryPrefix($prefix); 
  165.  
  166. print_r($queryRes); 

将’春风十里’,‘春天在哪里’,‘一百万个可能’,‘一千年以后’,‘后来’,‘后来的我们’,‘春天里’,'后会无期’这些歌名作为数据集,构建一个Trie树并进行测试。

可以看到输出以下结果

Trie树:

  1. Array 
  2.  
  3.  
  4.     [春] => Array 
  5.  
  6.         ( 
  7.  
  8.             [风] => Array 
  9.  
  10.                 ( 
  11.  
  12.                     [十] => Array 
  13.  
  14.                         ( 
  15.  
  16.                             [里] => Array 
  17.  
  18.                                 ( 
  19.  
  20.                                 ) 
  21.  
  22.                         ) 
  23.  
  24.                 ) 
  25.  
  26.             [天] => Array 
  27.  
  28.                 ( 
  29.  
  30.                     [在] => Array 
  31.  
  32.                         ( 
  33.  
  34.                             [哪] => Array 
  35.  
  36.                                 ( 
  37.  
  38.                                     [里] => Array 
  39.  
  40.                                         ( 
  41.  
  42.                                         ) 
  43.  
  44.                                 ) 
  45.  
  46.                         ) 
  47.  
  48.                     [里] => Array 
  49.  
  50.                         ( 
  51.  
  52.                         ) 
  53.  
  54.                 ) 
  55.  
  56.         ) 
  57.  
  58.     [一] => Array 
  59.  
  60.         ( 
  61.  
  62.             [百] => Array 
  63.  
  64.                 ( 
  65.  
  66.                     [万] => Array 
  67.  
  68.                         ( 
  69.  
  70.                             [个] => Array 
  71.  
  72.                                 ( 
  73.  
  74.                                     [可] => Array 
  75.  
  76.                                         ( 
  77.  
  78.                                             [能] => Array 
  79.  
  80.                                                 ( 
  81.  
  82.                                                 ) 
  83.  
  84.                                         ) 
  85.  
  86.                                 ) 
  87.  
  88.                         ) 
  89.  
  90.                 ) 
  91.  
  92.             [千] => Array 
  93.  
  94.                 ( 
  95.  
  96.                     [年] => Array 
  97.  
  98.                         ( 
  99.  
  100.                             [以] => Array 
  101.  
  102.                                 ( 
  103.  
  104.                                     [后] => Array 
  105.  
  106.                                         ( 
  107.  
  108.                                         ) 
  109.  
  110.                                 ) 
  111.  
  112.                         ) 
  113.  
  114.                 ) 
  115.  
  116.         ) 
  117.  
  118.     [后] => Array 
  119.  
  120.         ( 
  121.  
  122.             [来] => Array 
  123.  
  124.                 ( 
  125.  
  126.                     [的] => Array 
  127.  
  128.                         ( 
  129.  
  130.                             [我] => Array 
  131.  
  132.                                 ( 
  133.  
  134.                                     [们] => Array 
  135.  
  136.                                         ( 
  137.  
  138.                                         ) 
  139.  
  140.                                 ) 
  141.  
  142.                         ) 
  143.  
  144.                 ) 
  145.  
  146.             [会] => Array 
  147.  
  148.                 ( 
  149.  
  150.                     [无] => Array 
  151.  
  152.                         ( 
  153.  
  154.                             [期] => Array 
  155.  
  156.                                 ( 
  157.  
  158.                                 ) 
  159.  
  160.                         ) 
  161.  
  162.                 ) 
  163.  
  164.         ) 
  165.  

查询以“春为前缀的字符串”

  1. Array 
  2.  
  3.  
  4.     [0] => 春风十里 
  5.  
  6.     [1] => 春天在哪里 
  7.  
  8.     [2] => 春天里 
  9.  
  10. )

Tags: PHP搜索联想 PHP字典树算法

分享到: