python - 检查大量字符串是否存在的有效方法

Question

我有一组超过 100 万个字符串，每个字符串最多 63 个字符。我有很多磁盘空间和很少的内存 (512 MB)。我需要单独查询是否存在，并且不存储额外的元数据。

我的实际解决方案是 BDB btree。有没有更好的选择？我知道 leveldb 和 Kyoto Cabinet，但还不够熟悉，无法找出优势。

Answer 1

如果误报是可以接受的，那么一种可能的解决方案是使用 bloom filter .布隆过滤器类似于哈希表，但它不是使用一个哈希值来索引一个桶表，而是使用多个哈希来索引一个位数组。设置对应于这些索引的位。然后，为了测试一个字符串是否在过滤器中，再次对该字符串进行哈希处理，如果设置了相应的索引，则该字符串“在”过滤器中。

它不存储有关字符串的任何信息，因此它使用的内存非常少——但如果两个字符串之间存在冲突，则无法解决冲突。这意味着可能存在误报(因为不在过滤器中的字符串可能散列到与过滤器中的字符串相同的索引)。但是，不能有假阴性；集合中真正存在的任何字符串都将在布隆过滤器中找到。

有一个few Python implementations .自己动手也不难；我记得曾经使用 bitarray 自己编写了一个快速而肮脏的布隆过滤器。这表现得很好。