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个字母的引用确实容易出问题，但是这个我觉得也要实测才
: 知道。。
:
: 的数
|
