如何在一组字符串中找到未知的重复模式？

Question

这里是一个问题的描述。 假设您有一组字符串（多达100亿个字符串，每个字符串长度高达10k个字符，可以从中构造出1000个独特符号的字符串）。 我该如何查找长度为2到N（例如10）的模式？此外，我只想看到在所有字符串中至少出现1％的那些模式（某些阈值）。

我希望找到一种算法来帮助我解决这个问题。 数字不是精确的，但与项目中的数量级相同。

谢谢

- Oleksii Duzhyi

Answer 1

在后缀树（链接）中索引所有字符串。这可能需要O（字符数），您只需要在开始之前执行一次。

后缀树允许您快速（O（模式长度））检查是否出现任何已索引的字符串中的模式，以及出现的次数。

您可以通过结构再次进行遍历，并计算每个子树中叶子节点的数量（再次是O（N）），这告诉您可以从根到该节点找到子字符串的频率，因此您可以基于它们的常见程度删除它们或执行其他操作。

现在，长度为10k的100亿个字符串，具有2字节字符（以适应1000个唯一符号）非常大（如果我的数学正确，则为18TB），不适合RAM。因此，您需要等待一段时间或获取更多计算机并设置分布式解决方案。您可以将上述解决方案应用于字符串批次，以便它们适合您可用的内存，但是在结构中查找需要乘以您正在执行的批次数。

如果所有的东西都是批处理的，那么最有效的方法就是尽可能地将批次变大，然后在为一批构建后缀树时，运行所有查询并保存结果，然后删除树以释放内存，以便下一批输入字符串。

- Sorin

---

如果您只计算节点下方的叶子数量，那么您将计算出模式的总出现次数（包括在同一字符串中多次出现的情况），而不是OP所要求的（即模式出现的字符串总数）。但是您的方法很快，而且据我所知，计算后者需要在每个节点处存储具有下方叶子的字符串集合，并在DFS期间计算并集，这会使时间和空间复杂度增加，因此也许这已经足够好了。 - j_random_hacker

我认为我没有理解批处理的概念。假设我已经将输入分成了合理大小的批次，我的计算机/集群可以一次处理它们 - 那么在最后合并所有这些批次以获得正确答案，是不是错误的呢？ - Oleksii Duzhyi

你是对的，你需要在最后合并结果才能得到正确的答案。我认为这一部分是显而易见的。 - Sorin