如题：
马上下班了，突然来了一个需求，
mongodb 存了 5 亿条 email，现有 100 万英文人名，想把包含人名的所有 email 找到，怎么办，
我想破脑子都没想明白应该怎么做，感觉这个除了遍历没有其他方法了，
如果遍历的话，是 O(mn)，也就是 100 百万 * 5 亿次匹配，这也太慢了，12 个小时也搞不完，求大佬帮忙想想办法。
同时匹配所有人名用 Aho Corasick 算法。
没有的话 100w 人名先 hash 一下，然后遍历 5 亿数据，对比只要 O(1)，也就是 5 亿次。
100w 人名也用不了太多存储
我觉得思路应该放在优化上，适当的剪枝或许能有大作用，比如在写匹配算法的时候，遇到 @就停止匹配，一下就减少了差不多一半的匹配次数。你多看看数据，应该是有一些数据是可以很轻易就去掉的，比如 qq 邮箱全数字这种就直接去掉，一下子也能剪去不少。
这种服务器如果来一打，抛开数据交换时间，算一次的时间估计能压缩在 3 个小时内。
但问题是：
1.你们需要足够的服务器资源，以及足够强劲的内网带宽。服务器不够，或者内网带宽只有百兆，那就 GG 了。
2.你们需要经验丰富的分布式 C++数据处理经验。不然跑一次 3 小时，发现有问题，改下程序重新跑一次，3 小时又过去了。
3.从 MongoDB 的数据导出，再到 C++的分布式数据导入，需要全程不能踩坑。
比如，MongoDB 导出时，导出工具有 bug，导致处理了半个小时突然卡死；
或者 MongoDB 是分布式架构且数据导出对于磁盘甚至网络是随机 IO 操作；
或者 C++导入数据时忘了用 cache 提速导致导入时瓶颈在机械硬盘的随机 IO 上；
甚至，MongoDB 导出时，发现早期数据录入阶段，因为写策略没使用安全策略且踩了 MongoDB 的性能 bug 导致丢数据；
就算前面都顺利，在最后把这 120GB 均分到不同服务器时，发现交换机的带宽居然不够。或者早期图便宜只用了超 5 类线，等等，这些都是坑。
我咋感觉，这需求，有点像是公司恶意辞退？
1. 先把名字规整化，全部小写，去除多余字符，每个名字一个字符串
2. 创建一个 BloomFilter，写入全部的名字规则
3. 遍历 MongoDB 的记录，判断是否在 BloomFilter 中，找出符合条件的
PS：如果公司故意恶心你，还不如直接走了算了。
把邮件名中按字母建立索引，然后用人名去对应的索引中查找（假设名字中没有数字和符号）。
比如：
[email protected] 同时进入：a t h o m 6 这几个的索引。
如果想加速，就每两两三三再建一层索引：
ha ah at to om 这样。
最后查询的话，拿 tom 去命中 t o m 或者 to om 中的数据。
然后再去检查，对比匹配的数量应该会少很多。
如果是精确匹配，将 100 万字符串放 hash 表比如 python 的字典，然后对五亿字符串遍历一次，每个字符串查看是否在 hash 表就行。时间复杂度 O （ N ）。还是很快的，内存占用也就 1G 左右吧。
但是要做模糊匹配就麻烦了，上面的 bloomfilter 之类的办法全都不能用。
假如有 2000 台机器，每台机器 20 核 20 并发，那么就是 12500s，也就几个小时而已。
上提出了多种解法：
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
只是 100 万英文名按照最简单的方法建立出来的 AC 自动机需要 2TB 内存，希望有足够大内存的服务器。
这个是不是和这个比较像 https://v2ex.com/t/125941 42 也有个类似的。
可能最热 2000 个名字已经能匹配出 80%，最热 10000 个名字 90%，剩下的 99 万个名字，慢慢来吧。
（后边 99 万个名字，活多产出少，可能有些人会选择直接不要了。）
只是，你老板怎么验证结果有效性呢？
首先注册一个 gsuite，把你这 5 亿 email 传进去。
其次，写代码实现确定单条 email 是否包含人名。
之后，将 5 亿条 email 挪到团队共享盘，不断注册 gmail 账户，开 colab，按上述单条 email 查询跑。
（当然实际情况可以是一次性取 1W 条 email 然后验证之类的，确保不要重了或者漏了就行）
印象里这种小脚本，一个账号可以开 5 个 colab 。我不确定单台电脑能开多少个这样的 gmail 而不被封号，需要你自己实测了。
总归，需要多快，只看你开了多少个 colab 就行
比如你取固定长为 3 或者 4 个字母的片段做倒排索引。email 和人名都这么干。然后你可以直接根据人名的片段集合，去对 email 的集合做 join 。这样 join 出来，每个人名可以只和几百万甚至几万个 email 匹配，自然就快了。