0

最近我遇到了一个问题,问有多少位足以用这些假设散列一个网页:

  1. 有 10 亿个网页
  2. 网页平均长度为300字
  3. 我们有 250,000 个英文单词
  4. 页面是 ASCII

显然这个问题没有一个正确的答案,但这个问题的目的是看看一般方法是如何工作的。

4

1 回答 1

2

您还没有定义“散列网页”的含义;该短语出现在这个问题和互联网上的其他几个页面中。在那些其他页面中,它用于表示计算校验和(例如使用sha1sum)以验证内容是否完整。如果这就是你的意思,那么你需要对任何页面的所有位进行“散列”;平均而言,即 300 * 8 * 平均英语单词长度。题目没有说明平均英文字长,但是如果是五个字母加一个空格,那么每页的平均位数是6*300*8或者14400。

如果你的意思是把所有网页的所有单词放入一个索引结构中,以允许搜索找到包含任何给定单词集的所有网页,一个答案是大约 10^13 位:在一个索引结构中有 3000 亿个单词引用十亿页;每个引用使用 log_2(1G) 位,或者大约 30 位,如果引用是天真的存储的话;因此 9 万亿位,或大约 10^13。您还可以计算出十亿个 URL 的原始存储至少比这小一个数量级,即最多 10^12 位。可以使用特殊方法将引用存储减少几个数量级,但由于 URL 更容易压缩或紧凑保存(例如,通过 trie),引用存储可能仍然远远超过存储 URL 所需的存储量.

于 2012-10-11T02:03:38.350 回答