bloom filter 简介

Bloom Filter 是一种有效的数据结构，可使用少量内存，在大量元素列表中进行快速查找。

问题

已有上亿条或者更多的 id，需要在其中查找另一组 id 是否存在。一般方法是使用 set 或者 dict 数据结构，将已知 id 全部读入内存中，然后遍历待查询 id。但是该方法读入全部数据到 set/dict 会占用大量内存，在内存资源有限的情况下无法正常运行。如果待查找的 id 过多，希望用多进程并行处理更是不可能实现。

此时使用 bloom filter 可有效解决该问题。

bloom filter工作原理

bloom filter 使用若干个 hash 函数将每个 id 映射到

bit 长度的二值（binary）数组中。需要查询时，将待查询的 id 也经过 hash 并依次检查每个 hash 函数的输出是否与二值数组的数值一致，从而判断该 id 是否已经存在。由于 bloom filter 不会存储 id，使用内存大大减少。1G 内存可以表示约 85 亿条 id 数据。

但是由于使用 hash 函数，本身会有碰撞的可能，因此 bloom filter 有一定的误判概率。判断为存在时，有可能实际不存在，即有假阳性；但是判断为不存在时，则确定不存在，即无假阴性。也就是说查询返回的是“可能存在”或者“一定不存在”。

可根据实际需求判断 bloom filter 是否适用。误判概率可设置。误判概率设置越小，会使二值数组的长度更长（即 m 越大），所需内存相应增加。

具体地，hash function 的个数 k 可默认设置为：

其中 m 是二值数组的长度，n 是添加的 id 个数。所需二值数组的长度理论上等于：

其中 \epsilon 为错误率，用户可以自行指定。

示例

现有 85877331 条 id 数据，另有更多数量的待查询数据，需要判断其是否存在于已有的数据中。

• 方法1：使用set读取内存

85877331 条数据添加到 set 中用时 57s，占用内存大小为 9.79G，在其中查找 500 个 id 耗时 0.0007s。

• 方法2：使用 bloom filter

from pybloomfilter import BloomFilter

# 需要指定包含元素的最大个数，错误率，和文件
bloom = BloomFilter(120000000, 0.000001, '/path/to/filter.bloom')
with open("/path/to/id_file.tsv") as f:
    for word in f:
        bloom.add(word.rstrip())    # word like NM_001346897.2

使用 pybloomfiltermmap3 包的函数，初次添加 85877331 条数据耗时 1185s，输出文件为 412M，由于使用内存映射，未获得其在内存中的准确大小。在其中查找 500 个元素耗时 0.01s。

在初次添加元素后，再次初始化则无需重复添加，如果 /path/to/filter.bloom 文件存在，则直接读取。并且 bloom filter 支持不断添加新元素。如果需要日常更新，则直接添加更新的部分后即可直接复用，无需从头开始。但要注意，不要超过初始化对象时设置的最大元素数目。

bloom filter 在生信中的应用

1. streammd: fast low-memory duplicate marking using a Bloom filter

该篇文章主要基于 bloom filter，实现了一个鉴定 NGS 重复序列的工具。其结果准确性与 Picard MarkDuplicates 基本一致，而耗时显著减少。相比于 SAMBLASTER，其内存消耗显著减少。

1. Hierarchical Interleaved Bloom Filter: Enabling ultrafast, approximate sequence queries

该文章介绍了一种数据结构 Hierarchical Interleaved Bloom Filter (HIBF)，可用于在庞大的数据库中搜索指定的序列。该数据结构主要解决以下问题：给定一组输入序列 (样本)，在允许一定错误的情况下，查找哪些样本包含查询序列，这也被称为近似成员查询 (Approximate Membership Queries, AMQ)。

参考

• [1] https://pybloomfiltermmap3.readthedocs.io/en/latest/
• [2] Leonard C R. streammd: fast low-memory duplicate marking using a Bloom filter[J]. bioRxiv, 2022.
• [3] Mehringer S, Seiler E, Droop F, et al. Hierarchical Interleaved Bloom Filter: Enabling ultrafast, approximate sequence queries[J]. bioRxiv, 2022.