string - 如何在字符串集中找到未知的重复模式？

Question

这是一个问题的描述。假设你有一组字符串(最多 100 亿个字符串，每个字符串长度最多 10k 个字符，可以从 1000 个唯一符号构造字符串)。我怎样才能找到长度从 2 到长度 N 的模式(为简单起见，假设为 10)。此外，我希望只看到至少出现在所有字符串的 1%(某个阈值)中的那些模式。

我想找到一个算法来帮助我解决这个问题。这些数字并不准确，但与我们在项目中的数量级相同。

谢谢

Answer 1

在后缀树 ( link ) 中索引所有字符串。这可以是 O(字符数)并且您只需要在开始之前执行一次。

后缀树允许您快速(O(模式长度))判断模式是否出现在您索引的任何字符串中，以及出现了多少次。

您可以再遍历该结构并计算每个子树中叶子的数量(再次为 O(N))，这会告诉您多久可以找到从根到该节点的子字符串，因此您可以删除它们或者根据它们的常见程度做任何你想做的事情。

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

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