另一个字符串中出现了多少次字符串

Question

我有一个大的静态二进制文件（10GB），它不会改变。在

我希望能够将小字符串（每个15个字节或更低的字节）作为输入，然后确定哪个字符串最不频繁。在

我知道，如果不搜索整个二进制文件，我就不能准确地确定这个值，所以我知道这将是一个近似值。在

建立一个树/哈希表是不可行的，因为它将需要大约256^15字节，这是很多。在

我有大约100GB的磁盘空间和8GB的RAM，它们将专门用于这项任务，但是如果不仔细检查文件，我似乎找不到任何方法来完成这项任务。在

我有足够的时间来准备大的二进制文件，然后我需要多次决定哪个字符串最不频繁。在

有什么想法吗？在

谢谢！ 丹尼尔。在

（顺便说一句：如果重要的话，我使用Python）

Answer 1

因为你有一个大的静态字符串不变，你可以区分一次性的工作预处理这个字符串，这是永远不必重复的工作，回答查询。在一台更强大的机器上做一次性的工作可能比较方便。在

如果你能找到一个数量级或更多内部存储的机器，你可以构建一个后缀数组——一个从偏移量开始按后缀排序顺序排列的偏移量数组。它可以存储在外部存储器中用于查询，并且可以将其与二进制搜索一起使用，以查找查询字符串出现的排序顺序中的第一个和最后一个位置。显然，两者之间的距离将给出出现的次数，并且二进制搜索将需要大约34个二进制切分来执行16gbyte假设16Gbytes是2^34字节，因此每个查询应该花费大约68个磁盘查找。在

希望你找到这么大的内存可能不太合理，但我刚花50英镑买了一个1TB的USB硬盘，所以我想你可以增加一次工作的外部存储空间。有一些算法可以在外部内存中构造后缀数组，但是由于查询字符串被限制在15个字节以内，所以不需要那么复杂的东西。只需写出在每个偏移量处找到的15字节字符串，后跟一个5字节的偏移量数字，然后用外部排序对这些20字节的记录进行排序，就可以创建200GB的数据。这将为字符串提供50GB的索引，这些索引按排序顺序放入外部存储器中，以便回答查询。在

Answer 2

如果您事先知道所有查询，或者准备对它们进行批处理，另一种方法是从它们构建一个http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm树。这使得查询的总大小呈线性。然后，您可以将10GB的数据流化，时间与该数据的大小和任何字符串找到匹配项的次数成正比。在

Answer 3

也许可以构建一个哈希表，其中包含尽可能多的n元组的计数？你可以修剪那些不再出现的树。我不会称之为“近似值”，但可以是“上界”，保证检测不出现的字符串。在

所以，假设您可以构建所有4元组。在

然后，要计算“ABCD ef”的出现次数，您需要的最小值是count（ABCD）、count（BCDE）、count（CDEF）。如果其中任何一个值为零，则保证不会出现该字符串。如果是一个，它最多会出现一次（但可能根本不会出现）。在