c********t 发帖数: 5706 | 1 经常看到面经里说统计查询字符串的频率用trie结构。
比如统计所有用户在google search上的查询字符串的频率。
我的疑惑就是memory能存下这样一个trie结构吗?如果能需要多大?我的想法是就算字
符串长度最多255,那也是 26^255数量级吧。
同样,有的设计,把字典单词都放在一个trie里,我也很困惑。
求解释。
多谢! |
l*******b 发帖数: 2586 | 2 trie的节点大部分都没有26个用满吧, 应该是个链表一样的结构, 只有几个
【在 c********t 的大作中提到】 : 经常看到面经里说统计查询字符串的频率用trie结构。 : 比如统计所有用户在google search上的查询字符串的频率。 : 我的疑惑就是memory能存下这样一个trie结构吗?如果能需要多大?我的想法是就算字 : 符串长度最多255,那也是 26^255数量级吧。 : 同样,有的设计,把字典单词都放在一个trie里,我也很困惑。 : 求解释。 : 多谢!
|
c********t 发帖数: 5706 | 3 我说的26^255不对,是对字典说的
字典可能还可以,算平均 k个,最长单词为n,是k^n
但是搜寻可以组合到300多万个查询,放进trie,memory可以
吗?
【在 l*******b 的大作中提到】 : trie的节点大部分都没有26个用满吧, 应该是个链表一样的结构, 只有几个
|
l*******b 发帖数: 2586 | 4 300万一点也不大吧,char是一个字节,加上指针什么的算4个字节,就是一个3,4百万的数
组那么大.就是3,4M的事情
修改下,指针很长的, 还有些长度标识, 大概,3,4个64 bit integer肯定够了吧
吗?
【在 c********t 的大作中提到】 : 我说的26^255不对,是对字典说的 : 字典可能还可以,算平均 k个,最长单词为n,是k^n : 但是搜寻可以组合到300多万个查询,放进trie,memory可以 : 吗?
|
l*******b 发帖数: 2586 | 5 应该不是单词做node吧,是字符做node,然后标识,从root到这个node的path 是否构成一
个单词. Sedgewick的书上好像是这样
【在 c********t 的大作中提到】 : 我说的26^255不对,是对字典说的 : 字典可能还可以,算平均 k个,最长单词为n,是k^n : 但是搜寻可以组合到300多万个查询,放进trie,memory可以 : 吗?
|
w****x 发帖数: 2483 | 6
不会的,你一个查询字符串可以hash到不同的机器,一个机器维护一个big trie
【在 c********t 的大作中提到】 : 经常看到面经里说统计查询字符串的频率用trie结构。 : 比如统计所有用户在google search上的查询字符串的频率。 : 我的疑惑就是memory能存下这样一个trie结构吗?如果能需要多大?我的想法是就算字 : 符串长度最多255,那也是 26^255数量级吧。 : 同样,有的设计,把字典单词都放在一个trie里,我也很困惑。 : 求解释。 : 多谢!
|
c********t 发帖数: 5706 | 7 不是啊,300万是我在一个题里看的,说一个网站搜索一天大概有300万不同的搜寻词
实际上我也不知道google统计数字,我是这么想,你看对不对?
像你说的,没个分支不会都用26个字母,就算4个吧,平均搜索长度算15吧
每个节点像你说的用4个字节 4*4^15=2^60 bytes. 那也远远超过了TB的memory啊。
【在 l*******b 的大作中提到】 : 300万一点也不大吧,char是一个字节,加上指针什么的算4个字节,就是一个3,4百万的数 : 组那么大.就是3,4M的事情 : 修改下,指针很长的, 还有些长度标识, 大概,3,4个64 bit integer肯定够了吧 : : 吗?
|
c********t 发帖数: 5706 | 8 你说得对。我也发现了,在你说之前改了。
【在 l*******b 的大作中提到】 : 应该不是单词做node吧,是字符做node,然后标识,从root到这个node的path 是否构成一 : 个单词. Sedgewick的书上好像是这样
|
c********t 发帖数: 5706 | 9 嗯,这样可以,多谢!
【在 w****x 的大作中提到】 : : 不会的,你一个查询字符串可以hash到不同的机器,一个机器维护一个big trie
|
l*******b 发帖数: 2586 | 10 节点数目小于所有leaf个数乘以深度吧,貌似会多点,但也不太多呀
【在 c********t 的大作中提到】 : 不是啊,300万是我在一个题里看的,说一个网站搜索一天大概有300万不同的搜寻词 : 实际上我也不知道google统计数字,我是这么想,你看对不对? : 像你说的,没个分支不会都用26个字母,就算4个吧,平均搜索长度算15吧 : 每个节点像你说的用4个字节 4*4^15=2^60 bytes. 那也远远超过了TB的memory啊。
|
t*********h 发帖数: 941 | 11 用trie是因为很多查询有over lap吧 存储效率很高
【在 c********t 的大作中提到】 : 经常看到面经里说统计查询字符串的频率用trie结构。 : 比如统计所有用户在google search上的查询字符串的频率。 : 我的疑惑就是memory能存下这样一个trie结构吗?如果能需要多大?我的想法是就算字 : 符串长度最多255,那也是 26^255数量级吧。 : 同样,有的设计,把字典单词都放在一个trie里,我也很困惑。 : 求解释。 : 多谢!
|
d**********x 发帖数: 4083 | 12 可以实测一下嘛。。扒个字典也不难。。
再说做一个简单的估算,每个节点是一个字符的话,树的节点个数其实是小于原字典中
的字符数目的,所以不会爆。如果不理解的话,想一想我们树里的每一个节点都是从字
典里面来的就明白了。
如果一个节点里面存指向26个字母的引用确实容易出问题,但是这个我觉得也要实测才
知道。。
的数
【在 c********t 的大作中提到】 : 不是啊,300万是我在一个题里看的,说一个网站搜索一天大概有300万不同的搜寻词 : 实际上我也不知道google统计数字,我是这么想,你看对不对? : 像你说的,没个分支不会都用26个字母,就算4个吧,平均搜索长度算15吧 : 每个节点像你说的用4个字节 4*4^15=2^60 bytes. 那也远远超过了TB的memory啊。
|
c********t 发帖数: 5706 | 13 嗯,有空我试试。
【在 d**********x 的大作中提到】 : 可以实测一下嘛。。扒个字典也不难。。 : 再说做一个简单的估算,每个节点是一个字符的话,树的节点个数其实是小于原字典中 : 的字符数目的,所以不会爆。如果不理解的话,想一想我们树里的每一个节点都是从字 : 典里面来的就明白了。 : 如果一个节点里面存指向26个字母的引用确实容易出问题,但是这个我觉得也要实测才 : 知道。。 : : 的数
|