在文件中搜索字符串的最快方法

Question

我需要爲項目執行「查找功能」。我必須以儘可能最快的方式搜索所有相同的字符串（當然只有一個由操作員編寫）以及它們在一個大文件中的數量。 我想過一個與散列表連接的樹，但我不知道它是否正確。

1. 我怎樣才能用字符串（我通常使用數字）？

2. 什麼應該是最好的數據結構使用（複雜性）？

Answer 1

假設最壞的情況下：

• 巨大（1個Tebibyte）文件
• 高度變化和高度重複的內容。讓我們用它的〜100,000個單詞（這裏）取/usr/share/dict/words，連接，直到我們有一個Tebibyte，它給出了約110萬個。重複和混合起來。
• 非重複性（或接近非重複性）短（例如1-20字節，平均10）輸入。

算法的選擇取決於

• 數量的輸入（輸入/秒）
• 可用內存

如果只有極少數（數字有意保持含糊）的（Boyer-Moor（-Horspool），Rabin-Karp，Apostolico-Giancarlo，Knuth-Morris-Pratt）的輸入和/或沒有太多的可用內存。如果你有很多輸入和一些可用的內存，你可以首先索引這個文件（O（n），顯然），然後在O（1）中用散列表或者O（log n）用二分查找樹（有幾個優化可能，但讓我們保持簡單）。

不需要太多內存。不管你做什麼，哈希表或樹，你都需要保持這個位置，因爲你有四個以上的Gibibytes，你需要一個64位的計數器。八個字節乘以1.1 mio的表大小：僅8 Mebibytes。加上單詞本身的空間（少於一個Mebibyte與我的/usr/share/dict/words）或散列表索引（少一點，因爲你不需要大的整數與他們這樣一個短的單詞表）。

對於保存和管理大文件中單個詞的索引，您有一些開銷。二叉搜索樹是快速且快速構建的，儘管它具有相當大的內存開銷。如果您不需要搜索索引：只需將它們放入一個簡單的數組中即可。

tl; dr：索引文件，這是對文字和他們的地方的可憎的。如果你需要搜索這些索引，如果你一次需要它們，但是使用（二進制）搜索樹，可以將這些地方（可能需要64位整數！）放在一個簡單的數組中。我在這裏假設你知道如何構建一個完美的哈希。