Redian新闻
>
用trie统计字符串的疑惑
avatar
用trie统计字符串的疑惑# JobHunting - 待字闺中
c*t
1
经常看到面经里说统计查询字符串的频率用trie结构。
比如统计所有用户在google search上的查询字符串的频率。
我的疑惑就是memory能存下这样一个trie结构吗?如果能需要多大?我的想法是就算字
符串长度最多255,那也是 26^255数量级吧。
同样,有的设计,把字典单词都放在一个trie里,我也很困惑。
求解释。
多谢!
avatar
l*b
2
trie的节点大部分都没有26个用满吧, 应该是个链表一样的结构, 只有几个

【在 c********t 的大作中提到】
: 经常看到面经里说统计查询字符串的频率用trie结构。
: 比如统计所有用户在google search上的查询字符串的频率。
: 我的疑惑就是memory能存下这样一个trie结构吗?如果能需要多大?我的想法是就算字
: 符串长度最多255,那也是 26^255数量级吧。
: 同样,有的设计,把字典单词都放在一个trie里,我也很困惑。
: 求解释。
: 多谢!

avatar
c*t
3
我说的26^255不对,是对字典说的
字典可能还可以,算平均 k个,最长单词为n,是k^n
但是搜寻可以组合到300多万个查询,放进trie,memory可以
吗?

【在 l*******b 的大作中提到】
: trie的节点大部分都没有26个用满吧, 应该是个链表一样的结构, 只有几个
avatar
l*b
4
300万一点也不大吧,char是一个字节,加上指针什么的算4个字节,就是一个3,4百万的数
组那么大.就是3,4M的事情
修改下,指针很长的, 还有些长度标识, 大概,3,4个64 bit integer肯定够了吧

吗?

【在 c********t 的大作中提到】
: 我说的26^255不对,是对字典说的
: 字典可能还可以,算平均 k个,最长单词为n,是k^n
: 但是搜寻可以组合到300多万个查询,放进trie,memory可以
: 吗?

avatar
l*b
5
应该不是单词做node吧,是字符做node,然后标识,从root到这个node的path 是否构成一
个单词. Sedgewick的书上好像是这样

【在 c********t 的大作中提到】
: 我说的26^255不对,是对字典说的
: 字典可能还可以,算平均 k个,最长单词为n,是k^n
: 但是搜寻可以组合到300多万个查询,放进trie,memory可以
: 吗?

avatar
w*x
6

不会的,你一个查询字符串可以hash到不同的机器,一个机器维护一个big trie

【在 c********t 的大作中提到】
: 经常看到面经里说统计查询字符串的频率用trie结构。
: 比如统计所有用户在google search上的查询字符串的频率。
: 我的疑惑就是memory能存下这样一个trie结构吗?如果能需要多大?我的想法是就算字
: 符串长度最多255,那也是 26^255数量级吧。
: 同样,有的设计,把字典单词都放在一个trie里,我也很困惑。
: 求解释。
: 多谢!

avatar
c*t
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肯定够了吧
:
: 吗?

avatar
c*t
8
你说得对。我也发现了,在你说之前改了。

【在 l*******b 的大作中提到】
: 应该不是单词做node吧,是字符做node,然后标识,从root到这个node的path 是否构成一
: 个单词. Sedgewick的书上好像是这样

avatar
c*t
9
嗯,这样可以,多谢!

【在 w****x 的大作中提到】
:
: 不会的,你一个查询字符串可以hash到不同的机器,一个机器维护一个big trie

avatar
l*b
10
节点数目小于所有leaf个数乘以深度吧,貌似会多点,但也不太多呀

【在 c********t 的大作中提到】
: 不是啊,300万是我在一个题里看的,说一个网站搜索一天大概有300万不同的搜寻词
: 实际上我也不知道google统计数字,我是这么想,你看对不对?
: 像你说的,没个分支不会都用26个字母,就算4个吧,平均搜索长度算15吧
: 每个节点像你说的用4个字节 4*4^15=2^60 bytes. 那也远远超过了TB的memory啊。

avatar
t*h
11
用trie是因为很多查询有over lap吧 存储效率很高

【在 c********t 的大作中提到】
: 经常看到面经里说统计查询字符串的频率用trie结构。
: 比如统计所有用户在google search上的查询字符串的频率。
: 我的疑惑就是memory能存下这样一个trie结构吗?如果能需要多大?我的想法是就算字
: 符串长度最多255,那也是 26^255数量级吧。
: 同样,有的设计,把字典单词都放在一个trie里,我也很困惑。
: 求解释。
: 多谢!

avatar
d*x
12
可以实测一下嘛。。扒个字典也不难。。
再说做一个简单的估算,每个节点是一个字符的话,树的节点个数其实是小于原字典中
的字符数目的,所以不会爆。如果不理解的话,想一想我们树里的每一个节点都是从字
典里面来的就明白了。
如果一个节点里面存指向26个字母的引用确实容易出问题,但是这个我觉得也要实测才
知道。。

的数

【在 c********t 的大作中提到】
: 不是啊,300万是我在一个题里看的,说一个网站搜索一天大概有300万不同的搜寻词
: 实际上我也不知道google统计数字,我是这么想,你看对不对?
: 像你说的,没个分支不会都用26个字母,就算4个吧,平均搜索长度算15吧
: 每个节点像你说的用4个字节 4*4^15=2^60 bytes. 那也远远超过了TB的memory啊。

avatar
c*t
13
嗯,有空我试试。

【在 d**********x 的大作中提到】
: 可以实测一下嘛。。扒个字典也不难。。
: 再说做一个简单的估算,每个节点是一个字符的话,树的节点个数其实是小于原字典中
: 的字符数目的,所以不会爆。如果不理解的话,想一想我们树里的每一个节点都是从字
: 典里面来的就明白了。
: 如果一个节点里面存指向26个字母的引用确实容易出问题,但是这个我觉得也要实测才
: 知道。。
:
: 的数

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。