如何从大数据中找出两条相同的信息

Question

有50亿条商品名称信息，每条信息最长是50个字符，给定限制内存是4G，如何从这50亿条商品信息中查找出任意两条相同商品名称信息。给出思路以及算法思路。

Answer 1

算法2粗糙版：基于布隆过滤器，扫一遍，找出那些可能是重复的。看完这个数据结构你就懂了。

算法2精确版：使用布隆过滤器，扫一遍，找出那些可能是重复的。再扫一遍，计算它们的出现次数，超过1的就是精确的答案。

---

算法1：基本思路是对n个信息进行相对比较平均的分组（使用 hash(info) % m 分成m组），使得每组构成的哈希表可以放在内存中，且保证相同的两个信息进入同一组，然后再对每一组中的数据建立哈希表进行匹配即可。

4GB内存大约可以存下8000w+个50Bytes，考虑到hash表的空间利用率，假设以5000w为一组，则需要1000组（这个数字可以适当增加，并且使用质数的话通常效果更好）。

时间复杂度和空间复杂度都是O(n)。

p.s. 由于涉及到了外存，所以时间和空间复杂度其实就是扯淡。这个算法需要将所有数据先扫描一次（读取），分组（写入硬盘），再对每组进行查找（再读取），也就是要读2次写1次。

Answer 2

把商品名称分词，再对分词进行向量运算。然后就把这个问题转换成了向量比较问题，夹角越小则越被认为是同一个商品。