设计一个查询词提示系统

[问答题]

查询词提示是现代搜索引擎中广泛使用的一种技术,当用户输入查询词前缀时,会给出一系列相关的查询词推荐,例如在搜索框内输入"中国",会提示"中国好声音","中国银行", "中国联通"等,尝试设计一个查询词提示系统,回答以下问题:

1.给定一个查询词集合,用何种数据结构和算法来构建最基本的提示系统?要求输入中文和拼音都能正常工作

2.用户输入的前缀下可能有很多可提示的查询词,如何对这些查询词进行排序,将用户选择概率更高的词放在前面?

小虎牙

解析见：

http://tech.meituan.com/pinyin-suggest.html

它详细的分析了这个问题，用trieTree

发表于 2015-11-22 17:01:23 回复(1)

7厘海岸

发表于 2017-07-07 13:30:22 回复(0)

小白debug

借鉴楼上发的帖子，复制粘贴整理了一下

typedef struct TrieNode

{

int count; //用来统计单词前缀出现的次数

struct TrieNode* next[26]; //指向各个子树的指针

bool exist; //标记该节点处是否构成单词

char trans[11]; //当前节点对应的单词

}TrieNode ,*Trie;

1.用tire树的数据结构+topK算法来构建，建索引和查询的时候都要把汉字转换成拼音，查询完成后还得把拼音转换成汉字显示；

2.即解决TopK问题： hashMap统计+排序

（1）hashmap统计: 先对这批海量数据预处理。具体方法是：维护一个Key为Query字串，Value为该Query出现次数的HashTable，即hash_map(Query，Value)，每次读取一个Query，如果该字串不在Table中，那么加入该字串，并且将Value值设为1；如果该字串在Table中，那么将该字串的计数加一即可，最终在O(N)的时间复杂度内用Hash表完成了统计。
（2）排序：借助堆这个数据结构，找出Top K，时间复杂度为N‘logK。即借助堆结构，我们可以在log量级的时间内查找和调整/移动。因此，维护一个K(该题目中是10)大小的小根堆，然后遍历300万的Query，分别和根元素进行对比。所以，我们最终的时间复杂度是：O（N） + N' * O（logK），（N为1000万，N’为300万）。

发表于 2016-09-29 16:58:28 回复(0)