这里是一个问题的描述。 假设您有一组字符串(多达100亿个字符串,每个字符串长度高达10k个字符,可以从中构造出1000个独特符号的字符串)。 我该如何查找长度为2到N(例如10)的模式?此外,我只想看到在所有字符串中至少出现1%的那些模式(某些阈值)。
我希望找到一种算法来帮助我解决这个问题。 数字不是精确的,但与项目中的数量级相同。
谢谢
我希望找到一种算法来帮助我解决这个问题。 数字不是精确的,但与项目中的数量级相同。
谢谢
在后缀树(链接)中索引所有字符串。这可能需要O(字符数),您只需要在开始之前执行一次。
后缀树允许您快速(O(模式长度))检查是否出现任何已索引的字符串中的模式,以及出现的次数。
您可以通过结构再次进行遍历,并计算每个子树中叶子节点的数量(再次是O(N)),这告诉您可以从根到该节点找到子字符串的频率,因此您可以基于它们的常见程度删除它们或执行其他操作。
现在,长度为10k的100亿个字符串,具有2字节字符(以适应1000个唯一符号)非常大(如果我的数学正确,则为18TB),不适合RAM。因此,您需要等待一段时间或获取更多计算机并设置分布式解决方案。您可以将上述解决方案应用于字符串批次,以便它们适合您可用的内存,但是在结构中查找需要乘以您正在执行的批次数。
如果所有的东西都是批处理的,那么最有效的方法就是尽可能地将批次变大,然后在为一批构建后缀树时,运行所有查询并保存结果,然后删除树以释放内存,以便下一批输入字符串。