求救！限时 12 小时！ mongodb 存了 5 亿条 email，现有 100 万英文人名，想把包含人名的所有 email 找到，怎么办

[0x0208v0]

如题：
马上下班了，突然来了一个需求，

mongodb 存了 5 亿条 email，现有 100 万英文人名，想把包含人名的所有 email 找到，怎么办，

我想破脑子都没想明白应该怎么做，感觉这个除了遍历没有其他方法了，

如果遍历的话，是 O(mn)，也就是 100 百万 * 5 亿次匹配，这也太慢了，12 个小时也搞不完，求大佬帮忙想想办法。

[iseki]

@heiheidewo 我傻了，计算时 0 写多了

[pcbl]

看到很多楼层完全就不审题就开干了，好奇工作中也是这样的吗

[raaaaaar]

别讲了，楼主已经被开除了

[iseki]

我感觉自己逐渐清醒了一点…100w 个人名…真的没有重复吗😅

[yuang]

收藏了，以备不时之需

[chihiro2014]

布隆过滤器了解下？

[swulling]

其实就是五亿个字符串和 100 万字符串做子串匹配。

如果是精确匹配，将 100 万字符串放 hash 表比如 python 的字典，然后对五亿字符串遍历一次，每个字符串查看是否在 hash 表就行。时间复杂度 O （ N ）。还是很快的，内存占用也就 1G 左右吧。

但是要做模糊匹配就麻烦了，上面的 bloomfilter 之类的办法全都不能用。

[swulling]

其实有大集群直接 grep 都行，测试了下，对一个邮件地址，通过 grep -F 从 100 万个子串中查找匹配，大约耗时 1s 。那么就是五亿秒总计算时间。

假如有 2000 台机器，每台机器 20 核 20 并发，那么就是 12500s，也就几个小时而已。

[pcbl]

@swulling 拥有 2000 台 20 核机器的老板一般不会提出这种需求出来

[Mangozhen]

@pcbl 思路清奇而有效。哈哈！

[xupefei]

讨论一天了，我来总结一下吧。首先，楼主的问题是是 substring matching：有输入（邮箱，集合 N ）和一个字典（集合 D ）。要求找到一个集合 R，使[D 中存在一项 d]是[R 中任意一项 r]的子字符串。

楼上提出了多种解法：

1. 人名排序二分查找：不适用 substring matching 问题。

2. Bloom filter 布隆过滤器：不适用 substring matching 问题。Bloom filter 只能解决字符串整体匹配的问题，除非你有完美的分词方法。

3. k-tuple / n-gram 定长索引：适用于此问题。这方法在数据库领域用的很多，关键词是 inverted list matching 和 filtering and verification 。这个办法一般用来加速 M*N 的 JOIN 问题。它的原理是一个必要不充分条件：“如果字符串 a 是 b 的子串，那么两者的 n-gram 集合 gram(a)和 gram(b)中必定有一个重复项，反之不成立”。这个条件不充分，所以用它来 filtering 后的结果存在假阳性（ false positive ），需要一个额外的 verification 步骤来对结果逐个确认真实性。
在 verification 这一步中，我们能拿到的是一个邮箱 n 和若干潜在匹配的字典项集合 D'，只能循环 n*|D'| 次来逐个验证。

4. 多层定长索引：false positive 比解法 3 少一点点，但是 filtering 这一步比解法 3 慢很多。总体还是慢了。

4. 特殊字符剪枝：恭喜你重新发明了一个简化版的解法 5😂

5. Aho Corasick，AC 自动机：解决此问题的正确答案。具体原理中文维基百科的例子不错，推荐看一看。它的特点是能在线性时间内同时尝试匹配所有字典项目。LZ 的问题写代码的话就是这样的：
R = 空集
T = buildTrie(D)
for n in N:
__if(T.lookup(n)):
____R = R + {n}
return R
注意，整个 for 循环都是可以同步跑的，多线程或分布式都没有问题，因为字典树 T 从来没变过。

[levelworm]

问题你怎么确定是人名？ tom 也可以不是人名啊。。。比如说 tome666，这算人名不算？

[levelworm]

没用过 mongodb，如果是正常的数据库 join 可以么。。。没试过这么大的数据。。。有些数据库 join 规则可以写的比较复杂

[shakoon]

12 小时已经过去了，楼主凉了没？

[yngzij]

楼主估计已经辞职了
:dog

[IMCA1024]

这有点为难，钱没给够
凭什么 12 小时内出结果

[yuanse]

楼主辞职了吗🌚

[ccppgo]

楼主人还好吗?

[murmur]

楼主估计正在办手续

[xuanbg]

老板估计已经放弃了。