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

Question

我正在寻找一个KMP（或类似的）搜索到一个大文件（> 4GB）。

虽然我期待这个给我的问题，但我不能将它全部复制到内存中，因为那里没有足够的空间。

我的问题是，什么是最好的方式去做这个搜索？我应该简单地创建一个FILE *并直接在文件中进行搜索，我是否应该将块（比如4k）复制到内存中并搜索它们，或者完全搜索其他内容？

Answer 1

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

另外，我建议你建立某种索引，并使用索引来限制搜索。 KMP搜索不是特别有效。这当然取决于你的文件的性质，它如何被创建，等

Answer 2

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

Answer 3

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

但是，以某种方式尝试索引文件通常会更高效，因此您无需线性搜索整个文件。例如，KMP是一种字符串搜索算法 - 你只是在寻找一个词的发音？然后，您可以在文件中创建单词及其位置的哈希表（在磁盘上）并进行非常高效的搜索。

Answer 4

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