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

Question

我正在尋找一個KMP（或類似的）搜索到一個大文件（> 4GB）。

雖然我期待這個給我的問題，但我不能將它全部複製到內存中，因爲那裏沒有足夠的空間。

我的問題是，什麼是最好的方式去做這個搜索？我應該簡單地創建一個FILE *並直接在文件中進行搜索，我是否應該將塊（比如4k）複製到內存中並搜索它們，或者完全搜索其他內容？

Answer 1

如果您使用支持它的平臺，則可以使用mmap（）。 對文件進行分頁也是一種可能，但請記住儘可能保持緩衝區大小以減少IO開銷，並小心兩個頁面的邊界（假設一個字符串匹配，但被頁面邊界分割）

另外，我建議你建立某種索引，並使用索引來限制搜索。 KMP搜索不是特別有效。這當然取決於你的文件的性質，它如何被創建，等

Answer 2

直接在文件中搜索會非常緩慢，使用緩衝會提供更好的性能。但是請注意，當然緩衝區必須大於您搜索的緩衝區（SearchLength），並且在緩衝區結束前必須刷新緩衝區。

Answer 3

最好的方法是以塊的形式讀取並搜索它。您應該將塊大小作爲一個參數，以便您可以嘗試提供最佳性能的內容。

但是，以某種方式嘗試索引文件通常會更高效，因此您無需線性搜索整個文件。例如，KMP是一種字符串搜索算法 - 你只是在尋找一個詞的發音？然後，您可以在文件中創建單詞及其位置的哈希表（在磁盤上）並進行非常高效的搜索。

Answer 4

對於文件訪問，我會建議使用內存映射文件，以避免數據複製。這在unix機器上是微不足道的。如果文件映射不能在一個塊中分配，則可能必須將文件映射拆分爲更小的塊。如果您有興趣，我可以提供一些代碼。我想推薦使用Boyer More search algorithm。