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

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位整数！）放在一个简单的数组中。我在这里假设你知道如何构建一个完美的哈希。