11 dictionary
假设我在平面文件中给出了一个包含2亿字的大字典,我的函数需要检查字典中任何给定单词的存在,最快的方法是什么？您无法将字典存储在内存中,因为您只有1GB的内存.您可以将其存储在数据库中,但是在没有任何优化的情况下查询它仍然会非常慢.您无法索引完整的单词,因为您没有足够的资源.
编辑:除了下面提到的文件优化方法,有没有任何数据库优化？我正在考虑创建部分索引,比如在单词中每2个字母达到一个限制,我创建一个索引.这会加快db查询吗？
Rya*_*ary 21
假设字典按字母顺序排列,我会尝试修改二进制搜索.通过跳转到文件中的中点位置来分割和征服文件,并查看其中的单词.如果猜到高,将下半部分分成两半再试一次,直到没有文件位置可以尝试或找到单词.
(正如评论中提到的那样,在跳转到文件位置后,您需要向前和向后扫描以找到您跳转到的单词的边界.)
您可以通过根据单词的第一个字母直接猜测位置块来优化此功能.例如,如果单词以"c"开头,则围绕文件的3/26部分开始搜索.虽然,实际上,我认为这种早期猜测只能在总体上产生微不足道的差异.
其他优化可能包括保留索引的一小部分.例如,保留以字母表中每个字母开头的第一个单词的索引,或者保留每个单词的索引,每个单词以每个可能的两个字母组合开头.这样您就可以立即缩小搜索范围.
Joh*_*lla 14
这是Bloom过滤器的经典用例.Bloom过滤器是一种概率数据结构,它针对成员资格测试进行了优化("X是此集合的成员吗？"),并提供O(1)查找.作为交换,你引入一个任意小的假阳性概率 - 也就是说,过滤器会说一个特定的词存在,但实际上并不存在.你使用的内存越多,你就可以越小.然而,假阴性的概率为零:如果实际存在,过滤器将永远不会说某个单词不存在.
在您的特定情况下,使用80亿位(1 GB),您可以在每1,000,000,000次试验中获得比1更好的误报率.这是一个非常低的误报率.如果您查找了2亿个随机字符串,那么您从未遇到过一次误报的可能性大约是82%.
这不需要对字典进行排序,高度节省空间,并且不需要数据库或其他辅助存储结构.总的来说,它可能是您需求的不错选择.