winston 发表于 2009-9-18 09:11:01

URL字符串的相同内容检索问题

诸如:两个文件a,b每个文件中存有50亿条url,每条url大小为64字节,内存空间限制为4G,找出a,b所有相同的url。。。。这样的问题的思路是什么?

这个题目是网友“拳拳”提出。致谢!

winston 发表于 2009-9-18 11:43:50

不少朋友已经提出了很好的思路和参考。
比如编程珠玑2.1中的数字问题、还有google数学之美系列的:布隆过滤器(Bloom Filter)(http://www.googlechinablog.com/2007/07/bloom-filter.html)

我写下自己的思路和方案,未必最好,只供研讨。

1、考虑函数的增长,就是计算量问题。最简单的办法,当然是从A文件中,逐个取出每个URL字符串,去B中逐个对比,相同的就记录到文件。但是在50亿规模条件下,效率太低了。平方级的计算量。
2、用某种映射,使得每条数据的比较范围,尽可能的小,以便提升速度。可以用计数。每条都按数字记录一个总和数字。然后排序,排序后的数据,里面有映射关系。
这样,只要比较总和数字一致的即可,大大缩减计算数量。但是这么大数据量,一起排序,也是需要考虑的。
3、因为这个问题中,字符串的映射关系,是有界的。有明确的上界和下界。就是说:
所有可能出现在URL中的字符组合,有加总的最小值和最大值。
比如:aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
      zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...
如果我们把此上下界看作一个可以分割的数字空间范围,就方便了。可以这样做:
把这个数字范围,分成多个等份,每个等份小于内存能处理的尺寸即可。
计算每个URL字符串的加总hash值,然后,判断这个hash值位于哪个范围内,把相关
信息存入此分块的文件。
所有的信息如此处理后。磁盘上应该有已经大致划分好的子文件集合了。
然后对子文件内容排序,因为是数字排序,可以用线性时间算法。排序后,根据映射关系,
进行字符串的比对,即可完成。
页: [1]
查看完整版本: URL字符串的相同内容检索问题