如何用PHP实现基于字典树算法的长尾词搜索联想功能？

本文共计1549个文字，预计阅读时间需要7分钟。

搜索联想功能是各大搜索引擎的基础功能，如图所示，这个功能简化了用户的输入行为，并能推荐热门的搜索关键词。下面我们来谈谈如何用PHP实现搜索联想功能。

搜索联想功能是各大搜索引擎具备的基础功能，如下图所示，这个功能简化了用户的输入行为，并且能够给用户推荐热门的搜索词，下面我们来讲一下如何用php实现搜索联想的功能。

实现原理

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

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

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

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

什么是Trie树

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

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

它有3个基本性质：

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

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

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