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

Question

我有一组 100+ 百万个字符串，每个最多 63 个字符。我有很多磁盘空间和很少的内存（512 MB）。我需要单独查询存在，并且不存储其他元数据。

我事实上的解决方案是 BDB btree。有没有更好的选择？我知道 leveldb 和京都内阁，但不够熟悉以确定优势。

Answer 1

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

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

有一些 Python 实现。自己动手也不难；我记得曾经使用bitarrays 自己编写了一个快速而肮脏的布隆过滤器，效果很好。

Answer 2

你说你有很多磁盘，对吧？一种选择是将字符串作为文件名存储在嵌套的子目录中。您可以直接使用字符串：

• 将“drew sears”存储在d/r/e/w/ sears

或者通过对字符串进行哈希处理并遵循类似的过程：

• MD5('drew sears') = 'f010fe6e20d12ed895c10b93b2f81c6e'
• 创建一个名为f0/10/fe/6e/20d12ed895c10b93b2f81c6e.

将其视为操作系统优化的、基于哈希表的索引 NoSQL 数据库。

附带好处：

• 您可以稍后改变主意并将数据存储在文件中。
• 您可以使用 rsync 将数据库复制到另一个系统。