c - 在大文件中进行搜索的最佳方法是什么？

Question

我希望将 KMP(或类似)搜索应用于大文件(> 4GB)。

不过我预计这会给我带来问题。我无法将其全部复制到内存中，因为那里没有足够的空间。

我的问题是，进行此搜索的最佳方法是什么？我应该简单地创建一个 FILE* 并直接在文件中进行搜索，我应该将 block (比如 4k)复制到内存并搜索那些，还是完全其他的东西？

Answer 1

如果你使用的是支持它的平台，你可以使用mmap()。文件的分页也是可能的，但记住保持缓冲区尽可能大以减少 IO 开销，并注意两个页面的边界(假设一个字符串匹配，但被页面边界分割)

或者，我建议您建立某种索引，并使用该索引来限制搜索。 KMP 搜索不是特别有效。这当然取决于文件的性质、文件的创建方式等。