dictionary - 在大词典中查找某个单词的存在

Question

假设我有一个包含 2 亿个单词的平面文件大字典，我的函数需要检查字典中是否存在任何给定的单词，最快的方法是什么？您无法将字典存储在内存中，因为您只有 1GB 的内存。您可以将它存储在数据库中，但是如果没有任何优化，查询它仍然会非常慢。您无法索引完整的单词，因为您没有足够的资源。

编辑:除了下面提到的文件优化方法，还有没有数据库优化？我正在考虑创建部分索引，比如单词中每 2 个字母最多一个限制，我创建一个索引。这会加速数据库查询吗？

Answer 1

二分查找

假设字典有按字母顺序排列的单词，我会尝试修改 binary search .通过跳转到文件中的中点位置并查看那里的单词来划分和征服文件。如果猜测为高，将较低的分成两半并重试，直到没有文件位置可以尝试或找到单词。

(如 outis mentioned in a comment ，跳转到文件位置后，您需要来回扫描以找到跳转到的单词的边界。)

您可以通过根据单词的第一个字母立即猜测位置块来优化它。例如，如果单词以“c”开头，请围绕文件的 3/26 部分开始搜索。不过，实际上，我认为这种早期的猜测只会产生可以忽略不计的整体差异。

其他优化可能包括保留索引的一小部分。例如，保留以字母表中每个字母开头的第一个单词的索引，或保留以每个可能的两个字母组合开头的每个单词的索引。这将允许您立即缩小搜索范围。

O(log n)