我有一个不会更改的大型静态二进制文件（10GB）。字符串出现在另一个字符串中的次数
我希望能够输入小字符串（每个15字节或更低），然后确定哪个字符串是最不频繁的。
我明白，如果没有真正搜索整个二进制文件，我无法完全确定这一点，所以我知道这将是一个近似值。
构建一个树/哈希表是不可行的，因为它需要大约256^15字节，这是ALOT。
我有大约100GB的磁盘空间和8GB RAM将专门用于此任务，但我似乎无法找到任何方式来实现此任务，而不会实际上通过该文件。
我有尽可能多的时间，因为我想准备大二进制文件，然后我需要决定哪些是最不频繁的字符串很多次。
任何想法？
谢谢！ 丹尼尔。
（顺便说一句：如果它很重要，我使用Python）
也许建立与计数哈希表尽可能多的n元组，你可以买得起的存储呢？您可以修剪不再出现的树木。我不会称之为“逼近”，但可能是“上限”，并保证检测不出现的字符串。
因此，假设您可以构建所有4元组。
然后为“ABCDEF”的出现次数计算最小计数（ABCD），计数（BCDE），计数（CDEF）。如果其中任何一个为零，则保证字符串不出现。如果它是一个，它最多只会出现一次（但也许根本不会）。
因为你有一个不变的大静态字符串，你可以区分一次性工作预处理这个字符串，这个字符串永远不需要从回答查询的工作中重复。在更强大的机器上做一次性工作可能会很方便。
如果你可以找到一个数量级或更多的内部存储器的机器，你可以建立一个后缀数组 - 一个以偏移量开始的后缀排序顺序的偏移数组。这可以存储在外部存储器中用于查询，并且可以在二分搜索中使用该查找来查找排序顺序中的第一个和最后一个位置，其中出现查询字符串。显然，两者之间的距离会给出出现次数，而二进制搜索将需要大约34个二进制文件才能完成16G字节，假设16G字节是2^34字节，因此每个查询应该花费大约68个磁盘搜索。
指望你找到那么多的内部存储空间可能是不合理的，但我刚买了一个1TB的USB硬盘大概50磅，所以我认为你可以增加一次外部存储工作。在外部存储器中有后缀数组构造的算法，但是因为你的查询字符串被限制为15个字节，所以你不需要任何复杂的东西。通过写出在每个偏移量处找到的15字节字符串，然后是5字节偏移量数字，然后通过外部排序对这些20字节记录进行排序，创建200GB数据。这将为您提供50GB的索引到排序顺序的字符串中，以便您将其放入外部存储以回答查询。
如果您事先知道所有查询，或者准备对它们进行批处理，另一种方法是从它们构建http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm树。这在查询的总大小中花费时间线性。然后，您可以在时间上流过10GB数据，并按时间成比例地与数据大小和任何字符串找到匹配的次数之和成比例。
既然您正在寻找哪个频率最低，并且愿意接受近似的解决方案。您可以使用一系列Bloom filters而不是散列表。如果你使用足够大的数据，你不需要担心查询的大小，因为你可能保持低误报率。
这个想法是通过所有可能的查询大小并使子字符串不在其中。例如，如果查询将在3到100之间，那么它将花费（N *（从i = 3到i = 100的（i）的总和））。然后逐个将子集添加到布隆过滤器之一，以便查询不存在于过滤器中，如果需要，创建具有相同哈希函数的新布隆过滤器。您可以通过遍历每个过滤器并检查查询是否存在于其中。每个查询然后简单地通过每个过滤器并检查它是否在那里，如果是，则它向计数加1。
您需要尝试平衡误报率以及过滤器的数量。如果其中一个滤波器的误报率过高，那么它就没有用了，同样，如果您拥有数万亿个布隆滤波器（如果您对每个子滤波器进行一次滤波，则很有可能）。有几种方法可以处理这些问题。
你可能最终不得不实施scalable bloom filters让事情变得可管理的，这听起来类似于我建议无论如何，所以应该很好地工作。
你确定你真的想要近似吗？取决于这是什么类型的文件，不完整的抽样可能是相当具有误导性的。 – Thilo 2013-04-21 06:41:16
也许可以构建一个包含尽可能多的前缀的散列表，因为您可以负担得起存储空间？您可以修剪不再出现的树木。我不会称之为“逼近”，但可能是“上限”，并保证检测不出现的字符串。 – Thilo 2013-04-21 06:45:26
我将不得不每次运行算法大约20,000次，以决定大约15个字符串（以选择理想的字符串）。 （大10gb文件将始终保持不变）。 关于哈希表和前缀 - 我想过。我将回答这个问题作为对下面提出的答案的评论 – Avenger 2013-04-21 07:00:37