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

winston

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

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

winston

不少朋友已经提出了很好的思路和参考。
比如编程珠玑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值位于哪个范围内，把相关
信息存入此分块的文件。
所有的信息如此处理后。磁盘上应该有已经大致划分好的子文件集合了。
然后对子文件内容排序，因为是数字排序，可以用线性时间算法。排序后，根据映射关系，
进行字符串的比对，即可完成。