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 的大作中提到】
: 比如一个搜索引擎，打入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 的大作中提到】
: 既然用trie(prefix tree),每个节点存一定数量的string,比如gg就4个，这样空间也不
: 大吧，当然也存该节点被查询的次数(num),然后每隔一段时间bottom up 更新下，可以
: 用heap来更新,我是这么想的，不知是否符合楼主的要求，不太明白为什么要用Btree
|
p*******8
发帖数: 344 | 6 没有说用btree, 说用类似方法存一定level在内存，剩下的放disk, 其实我也不清楚
内存能不能存下。。我写了半天烙印也不听我解释，一直忙他自己的事，偶尔抬一下头
，我就知道我差不多挂了。。
【在 a******8 的大作中提到】
: 既然用trie(prefix tree),每个节点存一定数量的string,比如gg就4个，这样空间也不
: 大吧，当然也存该节点被查询的次数(num),然后每隔一段时间bottom up 更新下，可以
: 用heap来更新,我是这么想的，不知是否符合楼主的要求，不太明白为什么要用Btree
|
