p*******8 发帖数: 344 | 1 比如一个搜索引擎,打入auto,就会在下拉菜单中出现一连串的词,我们可以用trie列
出所有单词,但是
1)有什么好的方法只列出一定数量的单词?比如10个;
2)还有如果内存存不下所有单词,有什么解决方法?我想了下能不能用类似B-Tree的
方法,存比如2个level的node在内存里,剩下的放disk上,或者用多个机器,比如26台
,每台存相应字母(a-z)开头的单词
大家来讨论下吧 |
p*****p 发帖数: 379 | 2 1) dfs就行了吧
【在 p*******8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 比如一个搜索引擎,打入auto,就会在下拉菜单中出现一连串的词,我们可以用trie列 : 出所有单词,但是 : 1)有什么好的方法只列出一定数量的单词?比如10个; : 2)还有如果内存存不下所有单词,有什么解决方法?我想了下能不能用类似B-Tree的 : 方法,存比如2个level的node在内存里,剩下的放disk上,或者用多个机器,比如26台 : ,每台存相应字母(a-z)开头的单词 : 大家来讨论下吧
|
a******8 发帖数: 90 | 3 既然用trie(prefix tree),每个节点存一定数量的string,比如gg就4个,这样空间也不
大吧,当然也存该节点被查询的次数(num),然后每隔一段时间bottom up 更新下,可以
用heap来更新,我是这么想的,不知是否符合楼主的要求,不太明白为什么要用Btree |
a******8 发帖数: 90 | 4 我顺便练个:只贴关键的设计部分,欢迎大家提改进意见
class Node
{
char last_c;
int num;
Node* parent;
Node* child[26];
list lsugg;
hash_map msugg;
};
class PrefixTree
{
private:
Node* m_root;
public:
PrefixTree(){m_root = NULL;}
list giveSugg(string word)
{
Node* cur = m_root;
list empty;
for(int i = 0; i < word.size(); i++)
{
cur = cur->child[word[i]];
if(!cur)return empty;
}
return cur->lsugg;
}
void suggInsert(Node* cur,string word)//当前用户选择了suggestion里的
{
cur->msugg[word]->num++;
//reorder the list
}
void gInsert(string word);//一般插入新的
list updateSugg(Node* root)//run every period of time
{
priority_queue heap;//heap_size set to 4 like google
for(int i = 0; i < 26; i++)
{
//merge heap with all root->child[i].updateSugg();
}
list res(from heap);
return res;
}
} |
P*******b 发帖数: 1001 | 5 如果内存不是问题我觉得这样做挺好的。但是如果内存紧张的话,这个bottom up好像比
较expensive阿
【在 a******8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 既然用trie(prefix tree),每个节点存一定数量的string,比如gg就4个,这样空间也不 : 大吧,当然也存该节点被查询的次数(num),然后每隔一段时间bottom up 更新下,可以 : 用heap来更新,我是这么想的,不知是否符合楼主的要求,不太明白为什么要用Btree
|
p*******8 发帖数: 344 | 6 没有说用btree, 说用类似方法存一定level在内存,剩下的放disk, 其实我也不清楚
内存能不能存下。。我写了半天烙印也不听我解释,一直忙他自己的事,偶尔抬一下头
,我就知道我差不多挂了。。
【在 a******8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 既然用trie(prefix tree),每个节点存一定数量的string,比如gg就4个,这样空间也不 : 大吧,当然也存该节点被查询的次数(num),然后每隔一段时间bottom up 更新下,可以 : 用heap来更新,我是这么想的,不知是否符合楼主的要求,不太明白为什么要用Btree
|