Google : 搜索提示功能实现

这个问题我见过Google问了好几次了：
就是像Google和百度那种搜索关键字输入的框框，你输入一半字符串它会在下拉列表里按搜索频率高低显示关键词。比如你输入"hel",下拉框显示"hello","hell","hellokitty", "hellokitty 藏尸案"....

设计一个系统，实现这个提示功能

这个不是ajax的典型应用么。。。

没什么标准答案。
是不是有个服务器对所有搜索的关键字排序，当用户键入prefix的时候，把prefix发给服务器，服务器对已排好序的关键字做二分查找，找出以这个prefix开头的第一个关键字，时间开销log(n)。假设下拉框显示最频繁的k个关键字，则从这个找出的第一个关键字开始向后搜，到最后一个不以这个prefix开头的关键字结束，找出这个区间的Top(k)个关键字显示在用户的下拉框？？ 感觉还是太慢了...

我猜是用trie tree index的

我猜是用trie tree index的
MontagueHu 发表于 2011-6-20 09:00

    不知道google怎么实现的，我感觉不过直观上感觉就是trie tree. 问题是trie tree可以方便的找到所有特定字符串开头的搜索项。然后用O(n)的复杂度找出这些搜索项中最频繁的k个搜索