P*******b
发帖数: 1001 | 1 autocomplete是怎么实现的？
像google这样的搜索提示。
比如键入p，提示pandora，powerball，pizza hut，paypal，p
再键入b成了pb，提示pbs，pbs kids，pbr，pbteen，pb
都说用prefix tree，但是选出top 5的词汇呢？
那位大侠给仔细讲讲，我有包子发。谢谢 |
P*******b
发帖数: 1001 | 2 顶一下
【在 P*******b 的大作中提到】
: autocomplete是怎么实现的？
: 像google这样的搜索提示。
: 比如键入p，提示pandora，powerball，pizza hut，paypal，p
: 再键入b成了pb，提示pbs，pbs kids，pbr，pbteen，pb
: 都说用prefix tree，但是选出top 5的词汇呢？
: 那位大侠给仔细讲讲，我有包子发。谢谢
|
h**k
发帖数: 3368 | 3 在prefix tree上的每个节点存一组指针，分别指向前5 popular的满足当前prefix的单
词。
因为这个信息不敏感，所以不需要实时更新popular的数据。可以每半个小时之类的更
新一下。 |
P*******b
发帖数: 1001 | 4 thanks！
请问前5popular的满足当前prefix的单词怎么来？
【在 h**k 的大作中提到】
: 在prefix tree上的每个节点存一组指针，分别指向前5 popular的满足当前prefix的单
: 词。
: 因为这个信息不敏感，所以不需要实时更新popular的数据。可以每半个小时之类的更
: 新一下。
|
h**k
发帖数: 3368 | 5 可以让每个子树都报告5个最popular的单词上来，然后根节点从中选择5个最popular的
单词。
【在 P*******b 的大作中提到】
: thanks！
: 请问前5popular的满足当前prefix的单词怎么来？
|
P*******b
发帖数: 1001 | 6 thanks。
再问一下，在这个设计中，如果错误地输入了bas，给出提示bad。怎么实现？
【在 h**k 的大作中提到】
: 可以让每个子树都报告5个最popular的单词上来，然后根节点从中选择5个最popular的
: 单词。
|
