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

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

我希望这会给我带来麻烦。我无法将它全部复制到内存中，因为那里没有足够的空间。

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

Answer 1

如果您使用的是支持它的平台，则可以使用mmap（）。 文件的分页也是可能的，但请记住保持缓冲区尽可能大以减少IO开销，并在两个页面的边界之间小心（假设字符串匹配，但由页面边界分割）

或者，我建议您构建某种索引，并使用索引来限制搜索。 KMP搜索效率不高。 这当然取决于文件的性质，创建方式等。

Answer 2

对于文件访问，我建议使用内存映射文件来避免数据复制。 在unix机器上它是微不足道的。 如果无法在一个块中分配文件映射，则可能必须将文件映射拆分为较小的块。 如果您有兴趣，我可以提供一些代码。

对于搜索，我建议使用Boyer More搜索算法 。

Answer 3

直接在文件中搜索会非常慢，使用缓冲会提供更好的性能。 但请注意，您的缓冲区必须大于您搜索的内容（ SearchLength ），当然，在结束之前，当您使用SearchLength字节时，必须刷新缓冲区。

Answer 4

最好的方法是用块读取它并搜索它。 您应该将块大小作为参数，以便您可以尝试提供最佳性能的内容。

但是，以某种方式尝试索引文件通常更有效，这样您就不必线性搜索整个文件。 例如，KMP是一种字符串搜索算法 – 你只是在寻找一个单词的出现吗？ 然后，您可以在文件中创建单词及其位置的哈希表（在磁盘上），并进行非常有效的搜索。