布隆过滤器和前缀树实现违禁词过滤的性能对比

1 过滤1000个违禁词消耗内存对比

前言

此处假设违禁词都是由小写字母组成的单词 实际上违禁词的字肯定不止26个小写字母, 我目前想到的是用Set存储每个指针 但不管如何, 实际情况中布隆过滤器节省的内存肯定远不止下面计算所得

前缀树（Trie）的内存消耗

前缀树的每个节点通常包含以下内容：

  • 一个固定大小的数组（假设只有小写字母，每个节点有26个指针）
  • 一个布尔值或其他标记来指示该节点是否是一个完整单词

假设每个指针占用8个字节（64位系统）和每个布尔值占用1个字节：

  1. 每个节点的内存消耗：
    • 数组：26 * 8 字节 = 208 字节
    • 布尔值：1 字节
    • 总计：209 字节
  2. 节点数估算： 对于一个前缀树，每个词条大约创建的节点数取决于树内对应的公共前缀的长度。这里取最好情况即1000个词条只需要创建1000+n(单词长度)个节点(即所有单词只有最后一个字母不一样) 。
  3. 总内存消耗：
    • 1000+n 个节点 * 209 字节 ≈ 209,000 字节 ≈ 209 KB

布隆过滤器的内存消耗

布隆过滤器的内存消耗主要取决于位数组的大小和哈希函数的数量。假设使用合适的哈希函数数量和位数组大小，以达到合理的误报率。

  1. 位数组大小估算：
    • 为了达到1%的误报率，对于1000个元素，位数组的大小约为9585位（根据布隆过滤器的最佳参数公式）。
    • 9585位 ≈ 1198字节（1字节=8位）
  2. 哈希函数的数量：
    • 为了达到1%的误报率，大约需要7个哈希函数。
    • 每个哈希函数的计算开销是固定的，不影响内存消耗。
  3. 总内存消耗：
    • 位数组：1198 字节 ≈ 1.2 KB

内存消耗比较

  • 前缀树（Trie）：约209 KB
  • 布隆过滤器：约1.2 KB

节省内存计算

  • 节省的内存：209 KB - 1.2 KB = 207.8 KB

因此，布隆过滤器在处理每一千个屏蔽词时，相对于前缀树大约能节省207.8 KB的内存。(假设违禁词由26个小写字母组成且每个违禁词只有最后一个字母不同)

2 时间复杂度对比

前缀树（Trie）

  • 插入： 每个单词的插入时间复杂度为 O(L)，其中 L 是单词的长度。
  • 查询： 每个单词的查询时间复杂度也为 O(L)，其中 L 是单词的长度。

布隆过滤器

  • 插入： 每个单词的插入时间复杂度为 O(k)，其中 k 是哈希函数的数量。
  • 查询： 每个单词的查询时间复杂度也是 O(k)，其中 k 是哈希函数的数量。

时间复杂度对比

  • 对于前缀树（Trie），时间复杂度主要依赖于单词的长度 L。
  • 对于布隆过滤器，时间复杂度主要依赖于哈希函数的数量 k。

假设平均单词长度为 L，哈希函数数量为 k，通常 k 是一个较小的常数（例如，7个哈希函数），而单词长度 L 通常会比 k 大。因此，布隆过滤器在时间复杂度上通常会比前缀树更快，特别是在查询操作上。

具体比较

  1. 插入操作：

    • 前缀树：O(L)
    • 布隆过滤器：O(k)

    如果 L>k，布隆过滤器的插入操作更快, 反之前缀树更快

  2. 查询操作：

    • 前缀树：O(L)
    • 布隆过滤器：O(k)

    如果 L>k，布隆过滤器的查询操作更快, 反之前缀树更快

总结

一般来说布隆过滤器的哈希函数数量不会太多, 而中文环境下的前缀树违禁词长度也不会太长, 所以这两的时间复杂度应该相差不大; 而英文违禁词的单词长度普遍不短, 大部分情况下应该是布隆过滤器更快点

3 可靠性对比

前缀树

前缀树提供了精确的匹配功能。插入和查询操作都是确定的，不会有误报或漏报。

布隆过滤器

误报

布隆过滤器存在误报可能 即可能判断某个不在违禁词里的单词是违禁词; 但保证不会漏报, 即如果布隆过滤器判断某个单词不是违禁词 那么它一定不是违禁词

误报概率

误报概率可以通过以下公式计算:
image-20240716231217177

例如对于1000个元素，如果要保证误报率低于1%, 一般需要约9586位的位数组大小和7个哈希函数。实际应用中，可以根据具体需求和误报率要求调整这些参数。

4 其他方面

前缀树

暂时没想到什么缺点

布隆过滤器

  1. 无法删除元素：标准的布隆过滤器不支持删除操作，因为位数组中的位无法简单地重置而不影响其他元素的存在状态。虽然可以使用计数布隆过滤器（Counting Bloom Filter）来支持删除操作，但这会增加内存消耗和复杂性。

  2. 对哈希函数的依赖：布隆过滤器的性能和误报率高度依赖于选择的哈希函数。如果哈希函数不够好（例如产生碰撞较多），会导致误报率增加。

  3. 固定大小：布隆过滤器的位数组大小在创建时是固定的。如果要添加的元素数量远超过预期，会导致误报率大幅上升。动态调整位数组大小并不容易，需要重新构建布隆过滤器。

  4. 缺乏结构信息：布隆过滤器不存储元素的具体信息，只是对元素的存在进行概率性判断。因此，无法进行元素的具体操作或查询元素的详细信息。

5 总结

  • 前缀树（Trie）：在需要精确匹配的情况下，前缀树提供了高可靠性，但内存消耗较大，适合处理较少的数据量或对内存消耗不敏感的应用场景。
  • 布隆过滤器：在可以容忍误报的情况下，布隆过滤器提供了高内存效率和快速的插入、查询操作，适合处理大量数据且对内存使用敏感的应用场景。

选择前缀树还是布隆过滤器，取决于具体应用对内存、性能和可靠性的需求。