我有一个不变的大型静态二进制文件（10GB）。
我希望能够将小字符串（每个 15 字节或更低）作为输入，然后确定哪个字符串频率最低。
我知道如果不实际搜索整个二进制文件，我将无法准确确定这一点，所以我知道这将是一个近似值。
构建树/哈希表是不可行的，因为它需要大约 256^15 个字节，这非常多。
我有大约 100GB 的磁盘空间和 8GB 的 RAM 将专用于这项任务，但我似乎找不到任何方法来完成这项任务而无需实际检查文件。
我有尽可能多的时间来准备大二进制文件，然后我需要多次确定哪个是最不频繁的字符串。
有任何想法吗？
谢谢！丹尼尔。
（顺便说一句：如果重要的话，我正在使用 Python）
也许构建一个哈希表，其中包含尽可能多的 n 元组的计数，因为您可以负担得起存储？您可以修剪不再出现的树木。我不会将其称为“近似值”，但可以称为“上限”，以确保检测到未出现的字符串。
因此，假设您可以构建所有 4 元组。
然后要计算“ABCDEF”的出现次数，您将拥有 count(ABCD)、count(BCDE)、count(CDEF) 的最小值。如果其中任何一个为零，则保证不会出现该字符串。如果是一个，它最多会出现一次（但可能根本不会出现）。
因为您有一个不会更改的大型静态字符串，您可以将预处理此字符串的一次性工作与回答查询的工作区分开来。在更强大的机器上完成一次性工作可能会很方便。
如果你能找到一台具有一个数量级或更多内部存储的机器，你可以构建一个后缀数组——一个偏移量数组，按照从偏移量开始的后缀的排序顺序排列到流中。这可以存储在外部存储中以进行查询，您可以将其与二进制搜索一起使用，以按排序顺序查找查询字符串出现的第一个和最后一个位置。显然，两者之间的距离将为您提供出现次数，假设 16GB 为 2^34 字节，二进制搜索将需要大约 34 次二进制切碎来执行 16GB，因此每个查询应该花费大约 68 次磁盘寻道。
期望您找到这么多的内部存储空间可能不合理，但我刚刚以大约 50 英镑的价格购买了一个 1TB USB 硬盘，所以我认为您可以增加一次工作的外部存储空间。外部存储器中有用于后缀数组构造的算法，但由于您的查询字符串限制为 15 个字节，因此您不需要任何复杂的东西。只需写出在每个偏移处找到的 15 字节字符串，后跟 5 字节偏移编号，即可创建 200GB 数据，然后使用外部排序对这些 20 字节记录进行排序。这将为您提供 50GB 的按排序顺序排列的字符串索引，以便您放入外部存储以回答查询。
如果您事先知道所有查询，或者准备将它们批量处理，另一种方法是从它们构建http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm树。这需要与查询的总大小成线性关系的时间。然后，您可以按时间将 10GB 数据流过它们，这与该数据大小的总和以及任何字符串找到匹配项的次数成正比。
由于您正在寻找频率最低的，并且愿意接受近似解决方案。您可以使用一系列Bloom 过滤器而不是哈希表。如果您使用足够大的查询，则无需担心查询大小，因为您可能可以将误报率保持在较低水平。
这个想法是遍历所有可能的查询大小并从中制作子字符串。例如，如果查询将介于 3 和 100 之间，那么它将花费 (N * ((i) 从 i = 3 到 i = 100 的总和))。然后将子集一一添加到其中一个布隆过滤器中，以使过滤器中不存在查询，如果需要，创建一个具有相同哈希函数的新布隆过滤器。您可以通过遍历每个过滤器并检查其中是否存在查询来获得计数。然后，每个查询都简单地通过每个过滤器并检查它是否存在，如果存在，它将计数加 1。
您需要尝试平衡误报率和过滤器的数量。如果其中一个过滤器的误报率太高，它就没有用，同样，如果您有数万亿个布隆过滤器（如果每个子字符串一个过滤器，则很有可能）。有几种方法可以处理这些问题。
您可能最终不得不实现可扩展的布隆过滤器以保持事情的可管理性，这听起来与我的建议相似，所以应该可以正常工作。