Dre*_*ars 6 python berkeley-db kyotocabinet leveldb
我有一组1亿多个字符串,每个字符串长达63个字符.我有很多磁盘空间和很少的内存(512 MB).我需要单独查询存在,并且不存储其他元数据.
我事实上的解决方案是BDB btree.有没有更好的选择？我知道leveldb和Kyoto Cabinet,但不熟悉以确定优势.
如果误报是可接受的,那么一种可能的解决方案是使用布隆过滤器.Bloom过滤器类似于散列表,但它不使用一个散列值来索引桶表,而是使用多个散列来索引位数组.设置对应于那些索引的位.然后,为了测试字符串是否在过滤器中,字符串再次进行哈希处理,如果设置了相应的索引,则字符串在"过滤器"中.
它不存储有关字符串的任何信息,因此它使用非常少的内存 - 但如果两个字符串之间发生冲突,则无法进行冲突解决.这意味着可能存在误报(因为不在过滤器中的字符串可能会散布到与过滤器中的字符串相同的索引).但是,没有假阴性; 任何真正在集合中的字符串都将在bloom过滤器中找到.
有一些 Python 实现.滚动自己也不难; 我记得曾经使用bitarray过表现非常好的s 编写一个快速而肮脏的布隆过滤器.
| 归档时间： |
|
| 查看次数： |
800 次 |
| 最近记录： |