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

Question

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

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

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

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

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

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

有什么想法吗？在

谢谢！ 丹尼尔。在

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

Answer 1

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

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

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