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

ColarCoon
  • 22

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

回复
阅读 4.9k
2 个回答

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

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

---

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

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

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

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

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

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
你知道吗?

宣传栏