输入关键字 抓取所有网页(树+TopK算法(二)：Trie树存储)

　　输入关键字 抓取所有网页(树+TopK算法(二)：Trie树存储)

　　方案1 Trie树+TopK算法

　　Trie树是字典树，也称为词搜索树或关键字树。它是一种树结构，是哈希树的一种变体。一个典型的应用是对大量的字符串（但不限于字符串）进行计数和排序，所以经常被搜索引擎系统用于文本词频统计。其优点是：尽量减少不必要的字符串比较，查询效率高于哈希表。Trie 是一棵存储多个字符串的树。相邻节点之间的边代表一个字符，这样树的每个分支代表一个子串，树的叶节点代表一个完整的串。与普通树的区别在于相同的字符串前缀共享相同的分支。例如，给定一组词 inn、int、at、age、adv、ant，我们可以得到以下 Trie：

　　

　　从上图可以看出，当用户输入前缀i时，搜索框可能会显示“in”、“inn”、“int”等以i为前缀的关键词，然后当用户输入前缀a，搜索框可能会提示以a为前缀的“ate”等关键词。这样一来，实现搜索引擎智能建议的第一步就很明确了，就是用trie树来存储大量的字符串。当前缀固定时，存储相对较热的后缀。

　　TopK算法用于解决统计热词问题。解决TopK问题主要有两种策略：hashMap统计+排序，堆排序

　　Hashmap 统计：首先对这批海量数据进行预处理。具体方法是：维护一个HashTable，Key为Query字符串，Value为Query出现的次数，即hash_map(Query, Value)，每次读取一个Query，如果该字符串不在Table中，则添加字符串，并将 Value 值设置为 1；如果字符串在Table中，只需将字符串的计数加1，最后在O(N)时间复杂度内完成与Hash表的统计。

　　堆排序：借助堆的数据结构，找到Top K，时间复杂度为N'logK。也就是说，借助堆结构，我们可以在日志时间中找到并调整/移动。因此，维护一个K（问题是大小为10)的小根堆，然后遍历300万个Query与根元素进行比较。因此，我们最终的时间复杂度为：O(N) + N' * O (logK)，（N 为 1000 万，N' 为 300 万）。

　　这个程序的问题是：

　　方案二 Solr自带Suggest智能提示

　　Solr作为一个被广泛使用的搜索引擎系统，内置了一个叫做Suggest模块的智能提示功能。模块可以选择根据提示词文本进行智能提示，也支持针对索引的某个字段创建索引词典进行智能提示。（详见 solr 的 wiki 页面）

　　这个程序的问题是：

　　方案三 Solrcloud建立单独的集合，使用Solr前缀查询来实现

　　如上所述，上述两种方案的实现都存在一些问题。Trie树+TopK算法在处理汉字suggest时不是很优雅，需要维护两棵Trie树，实现起来比较复杂；Solr 自己的suggest 智能提示组件的问题在于它使用了freq 排序算法。返回结果完全基于索引中字符的出现次数，没有考虑用户搜索词的频率。因此，一些流行词不能排名更高。因此，我们继续寻找更优雅的解决方案来解决这个问题。

　　此时，我们考虑专门为关键字创建一个索引集合，使用Solr前缀查询来实现。solr中的copyField可以很好的解决我们同时索引多个字段（汉字、拼音、缩写）的需求，并且当字段的multiValued属性设置为true时，可以解决多音素组合的问题同一个关键词。配置如下：

　　schema.xml:

------------------multiValued表示字段是多值的-------------------------------------

kw

suggest

说明：

kw为原始关键字

pinyin和abbre的multiValued=true,在使用solrj建此索引时，定义成集合类型即可：如关键字“重庆”的pinyin字段为{chongqing,zhongqing}, abbre字段为{cq, zq}

kwfreq为用户搜索关键的频率，用于查询的时候排序

-------------------------------------------------------

------------------suggest_text----------------------------------

　　KeywordTokenizerFactory：这个分词器不执行任何分词！整个字符流变成了一个标记。String 字段类型也有类似的效果，但不能配置文本分析的其他处理组件，例如大小写转换。对于任何用于排序和大多数分面功能的索引字段，该索引字段在原创字段值中只能有一个单词元素。

　　前缀查询构造：

　　private SolrQuery getSuggestQuery(String prefix, Integer limit) {

SolrQuery solrQuery = new SolrQuery();

StringBuilder sb = new StringBuilder();

sb.append(“suggest:").append(prefix).append("*");

solrQuery.setQuery(sb.toString());

solrQuery.addField("kw");

solrQuery.addField("kwfreq");

solrQuery.addSort("kwfreq", SolrQuery.ORDER.desc);

solrQuery.setStart(0);

solrQuery.setRows(limit);

return solrQuery;

}

　　结果如下图：

　　

　　参考