一年没有写博客了，写一个我今年在工作中遇到的问题吧。

首先有一个字符串集合A（母串集），A中大概有1.6x10¹⁰个字符串。这些字符串大部分都比较短，长度小于100。最长的字符串有2¹⁶个字符。

还有一个比较小的字符串集合B（子串集）。B里的每个字符串都是A里某个字符串的前缀，共有2.4x10⁷个前缀。B中的每个字符串都与一个非负整数相关联。

现在对于A中的每个字符串a_i，求一个整数。这个整数等于B中所有a_i的前缀所对应的整数的最大值。

（之前已经听我白话过这个问题的同学们：是的，问题规模又扩大了。）

背景：A是数据的key集合，B是用户的删除数据请求，删除被匹配的key和它对应的数据。因此，最后A中被匹配到的字符串不会特别多，大约是B的大小的若干倍。可以认为远小于100倍。

看到这个问题的规模，我们就知道只能跑在一台机器上的算法是不行的。必须设计一个能并行地跑在许多台机器上的算法。

这个问题的规模如果小一点，就相当容易解决。例如，如果B中的字符串少一点，少到2.4x10⁴个。我们就可以把B做成一个Trie直接扔到内存里。准备若干台机器，每台机器都复制一份。给每台机器分配A的一段，各自扫描就好了。这样的复杂度是length(sigma A + sigma B)的。可能会比较占内存，但是现在内存都是白菜价了， who cares。

如果B再大一点点，大到2.4x10⁶，问题也不是那么难。我们可以：

1. 把B分成一百份，每次用上述方法处理一份，处理一百次；
2. 或者，找一份可以放在硬盘上的Trie实现（假设能找得到）。Trie的每次查询只用到整个Trie的很小一部分。实现时只需要把查询时能访问到的部分装载到内存里，访问不到的swap到硬盘上就可以了。如果性能不足，还可以把4个byte压缩成一个long，既减少硬盘读写又减少空间浪费。
3. 再或者两种方案结合，把B分成10份，每次用硬盘Trie处理一份。即使用最烂的（我的）实现，Trie文件的大小也不过几十G，可以接受。

但是拆分B的方案不能把B拆成太多份。因为每拆一份B都要把A复制一份，也就意味着多一份的数据读写。不幸的是我司的storage层对许多个并行读者的支持并不好，过多读者会导致大家都读得更慢。B如果再大，拆分的方法就不好用了。

大家有什么想法？我的答案在下面，不要偷看哦。

---

答案分割线

---

解决方案其实很简单，相信大家也都想到了：hash。

对集合B里的每一个子串，hash它长度为2的整数次幂的最长前缀。如果一个串的长度为19，就hash前16个字符；如果长度是32，就hash所有字符。这样我们得到了2.4x10⁷个long，大约占192M内存（我是不是算错了….对这个数字没什么信心）。

把这些hash值扔到一个数组b_hash_set里，排序之。

对于集合A里的每个母串，hash它的每个长度为2的整数次幂的前缀。对于每个字符串a_i，我们会得到log(length(a_i))个数字。称这些hash值的集合为a_hash_set。 如果a_hash_set和b_hash_set中的某一对数字a_hash和b_hash相等，他们分别对应的母串和子串才有可能前缀匹配。就不证明了，结论非常明显。

这时再暴力匹配有可能的字符串对，运行时间就完全可以接受了。

一个小优化：在生成a_hash_set的一个值的时候，可以直接在b_hash_set里二分查找这个值。如果不存在，就不用把它放到a_hash_set里了。这样可以显著减小a_hash_set（以及和它关联的数据）的体积。在实践中，优化后a_hash_set的体积缩小了三百倍。

如何找到所有相等的a_hash和b_hash对？把它们扔到一起sort就可以了。a_hash_set的体积可能会特别大，但是我们也有分布式排序算法嘛。

后话

上次在群里跟大家讨论的时候，范神@ronaflx提到，他们判断整个字符串相等的时候都会先算hash，然后暴力匹配。我当时还觉得，暴力就暴力吧，hash能有什么作用？仔细一想，使用hash，子串和母串都只需要扫描一遍；而且hash本身的体积比字符串小很多，比较容易传递。在这里顺便感谢范神给我普及字符串匹配基础知识。

但是hash只能判断相等（严格来说，只能确定不等），不能判断前缀。一个常见的workaround是把母串的所有前缀都hash了，再和子串的hash比。这样的方案在母串都不长的情况下很适用。但是在这个问题上，这样做会在时间复杂度上乘一个一百左右的常数。要减小常数，只处理2的整数次幂也是常见workaround：牺牲部分精度（子串的一部分被忽略了），但是可以把常数从100减少到6。

最后，欢迎大家提出更好的方法来打脸！

吐槽

Java的TreeSet存2.4x10⁷个数，居然要占用10多G内存！你丫是暴力数组实现的Trie吧！

下次给自己的service设计功能的时候，一定要先想想到底能不能高效实现。堂堂大Google，若干M个请求都处理不好，混不混了！

感慨

本文就是我今年工作最大的成绩了。进入Google一年，蹉跎一年，一事无成，Todo List 基本没有刷，能力进步为零。

逆水行舟，不进则退。与君共勉！