我需要为一个项目执行“查找功能”。我必须以尽可能最快的方式搜索所有相同的字符串(当然只有运算符(operator)编写的一个)以及它们在一个巨大文件中的数量。 我想到了一棵树与一个哈希表连接，但我不知道它是否正确。
如何使用字符串(我通常使用数字)来完成此操作？
最好使用的数据结构(复杂性)应该是什么？
最佳答案
假设最坏的情况:
- 巨大(1 Tebibyte)文件
- 内容高度多样化且高度重复。让我们将
/usr/share/dict/words及其大约 100,000 个单词(此处)连接起来，直到我们得到 1 Tebibyte，它提供大约 1.1 mio。重复并混合起来。 - 非重复(或接近非重复)的短输入(例如 1-20 字节，平均 10 个字节)。
算法的选择取决于
- 输入数量(输入/秒)
- 可用内存
如果您只有少量(数字故意保持模糊)输入和/或没有太多可用内存，您可以线性搜索它(Boyer-Moor(-Horspool)、Rabin-Karp、Apostolico-Giancarlo、Knuth-莫里斯-普拉特)。
如果你有很多输入和一些可用内存，你可以先索引文件(显然是 O(n))，然后使用哈希表在 O(1) 中搜索，或者使用二叉搜索树在 O(log n) 中搜索(有几种可能的优化，但让我们保持简单)。
不需要太多内存。无论您做什么，无论是哈希表还是树，您都需要将位置保留在某个地方，并且因为您有超过 4 Gibibytes，所以您需要一个 64 位计数器。 8 个字节乘以表大小 1.1 mio:仅 8 Mebibytes。加上单词本身的空间(我的 /usr/share/dict/words 小于 1 Mebibyte)或哈希表的索引(稍微少一点，因为您不需要使用大整数来存储它们)一个简短的单词表)。
您需要一些开销来保存和管理大文件中各个单词的索引。二叉搜索树的构建速度很快，尽管它有相当多的内存开销。如果您不需要搜索索引:只需将它们放入一个简单的数组中即可。
tl;dr:索引文件，即对单词及其位置进行哈希表。如果您一次需要所有位置(可能需要 64 位整数!)，请将它们放在一个简单的数组中，但如果您需要搜索这些索引，请使用(二元)搜索树。我在这里假设您知道如何构建完美的哈希。
关于c - 在文件中搜索字符串的最快方法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40695665/