c++ - 在一个大的二进制文件中搜索，在缓冲区中加载 block

Question

我想知道按 block 搜索大文件并将它们加载到内存缓冲区的算法。

所以我有一个很大的文件，将把它读取到小缓冲区并扫描它以查找“针”字:

while ( read = fread(buff, buff_size, 1, file) )
   if strstr(buff, needle) print "found!";

但是如果“干草”中的“针”会被方 block 边界割断怎么办？将无法找到。

我看到的一个解决方案是每次都读取下一个 block fseek'ing(减少“针”字符串长度的偏移量)

 offset += read - strlen(needle);
 if (offset > 0) fseek(file, offset ,SEEK_SET);

我说得对吗？

Answer 1

你是对的，你需要处理搜索模式跨越两个 block 的情况。

你也说得对，寻求可以是一种解决方案。

但是还有其他不使用搜索的解决方案。

解决方案 1

一个解决方案可能是复制缓冲区的最后一部分，即 strlen(needle) 到一个能够容纳 2 倍 strlen(needle) 的小缓冲区。

然后在读取下一个 block 时，将新缓冲区的第一部分(同样是 strlen(needle))复制到小缓冲区，以便它与前一个缓冲区末尾的部分相连接缓冲区。

最后，您可以在小缓冲区中搜索 niddle。

方案二

一个解决方案可能是从文件中读取到 buffer + strlen(needle)，即避免覆盖缓冲区的第一个 strlen(needle) 字符。从文件中读取的字符数必须相应减少(即 buff_size - strlen(needle))

完成缓冲区后，将最后的 strlen(needle) 字符复制到缓冲区的开头，然后从文件中读取更多数据到 buffer + strlen(needle)

对于缓冲区中的第一次搜索，您必须跳过第一个 strlen(needle) 字符(或确保它们不匹配您的模式，例如通过初始化)。后续搜索应搜索整个缓冲区。