基于二分查找的搜索提示实现

用过百度或GOOGLE的人应该都有印象，当你在搜索框输入一些关键字之后，会提示相关的搜索关键词，比如，我输入"g"，会提示"google","gmail"一类以"g"开头的关键词。本文讨论的就是这样的一个功能，在后台算法上应该如何实现。
首先我们会有一个关键词列表，包含了 关键词 和它的搜索次数，如：
good,5
nid,1
google,10
gmail,100
apple, 22
mail,500
把上面的词条是按照编码值从小到大排序，结果如下：
apple, 22,0
good,5,0
google,10,3
gmail,100,1
mail,500,0
nid,1,0
排序后，张每个词条加上一个属性，就是当前词条与前一词条前缀字符相同数量，我称它为PreLength，比如：
good和apple 前缀字符相同数量为0，good和google前缀字符相同数量为3，以此类推，结果如下：
apple, 22,0
good,5,0
google,10,3
gmail,100,1
mail,500,0
nid,1,0

经过上面的预处理 就可以用二分法来查找了。比如用户输入g,输入长度InputLength=1,
用二法定位到第三个词条 google,它的PreLength=5 >= InputLength,加入前一词条good
继续向前遍历,直到PreLength< InputLength

然后向后遍历，直到PreLength< InputLength

这样就收集到了结果
good,5,0
google,10,3
gmail,100,1
再按搜索次数排序，并把前N条记录返回就可以了。当然这里用优先队列实现更好。

要把一个算法用文字描述清楚还是比较的困难呀。。

评论

1 楼 fuliang 2010-12-12  

搜索提示一般使用trie的结构进行前缀匹配。