Boyer–Moore 多数投票：它为何有效，它为何失效，以及它真正的适用范围

Source: Dev.to

介绍

Boyer–Moore 多数投票算法通常被呈现为一个巧妙的技巧：

在 O(1) 空间内找到多数元素。

这个说法在技术上是正确的，但在实际中具有误导性。本文记录了我所走的推理路径——从一种可辩护的精确计数方法到一种基于置信度的支配信号，而不是一个精确答案。探索最初是一个 LeetCode 题目，后来演变成系统设计问题。

多数元素基础

给定一个元素序列，多数元素出现的次数超过 ⌊n/2⌋ 次。

• 重要约束
  • 可能存在，也可能不存在多数元素。
  • 如果存在多数元素，则它是唯一的。

精确计数（HashMap）

• 时间: O(n)
• 空间: O(k)，其中 k 为不同元素的数量。

如果将计数存储在适当的结构（时间桶、可过滤字段桶）中，精确计数可以实现任意过滤（时间范围、标签、属性）。无需额外的验证步骤，但内存会随候选项基数的增长而增加——在具有大规模或未知域的流式系统中，这是一项无界的需求。

Boyer–Moore 多数投票算法

算法

1. 维护一个 candidate（候选者）和一个 counter（计数器）。
2. 对每个元素执行：
   • 如果 counter 为零，则将 candidate 设为当前元素。
   • 如果当前元素等于 candidate，则 counter 加一。
   • 否则，counter 减一。
3. 第一次遍历结束后，通过第二遍计数 来验证候选者的出现次数。

• 时间复杂度： O(n)
• 空间复杂度： O(1)

如果存在多数元素，Boyer–Moore 将把它作为最终候选者返回。但该算法 并不保证：

• 必然存在多数元素。
• 在未验证的情况下返回的候选者一定是多数元素。

验证（第二遍）

count = 0
for each element:
    if element == candidate:
        count += 1
if count > n/2:
    return candidate   // true majority
else:
    return None        // no majority

如果省略此验证步骤，算法可能会返回一个错误的多数元素，正确性无法得到保证。

为什么不直接使用 HashMap？

如果无论如何都需要第二次遍历和持久化数据，那么显而易见的反对意见是：

为什么不直接使用 HashMap？

这个反对意见是合理的。在选择算法之前，先描述问题域而不是工具会更有帮助。

Source: …

Boyer–Moore 发光的领域

考虑处理以下情况的系统：

• 连续的事件流。
• 高基数标识符。
• 可能无限的输入。
• 固定的内存预算。

典型例子：

• 监控与告警管道。
• 事件摄取层。
• 滥用或异常检测系统。
• 负载削减与背压机制。

在这些情境中，目标往往 不是 计算精确计数，而是回答诸如：

“有什么东西现在在系统中占主导吗？”

假设我们在固定窗口（例如每小时）内处理数百万事件，且事件类型是无限的。内存使用必须保持稳定。

HashMaps 在基数不爆炸时可以完美解决问题。Boyer–Moore 因为常数空间而显得有吸引力，但若在每个窗口都直接输出候选者，会导致噪声、误报以及告警疲劳。

将计数器解释为置信信号

关键洞见在于 counter 不是 频率；它是一个 支配边际——候选者抵消被消除的力度。即使没有精确计数，这一信息也是有意义的。

信号构建

• 随机数据 → 置信度接近 0。
• 主导数据 → 置信度上升。
• 候选者频繁翻转 → 置信度低。
• 候选者持久存在 → 置信度更高。
• 计数器振荡 → 噪声。
• 计数器增长 → 主导趋势出现。

决策依据 持久性和增长，而不是仅仅存在。

适用场景

• 流式告警系统。
• 背压检测。
• 异常或滥用信号。
• 内存受限的摄取路径。

不适用场景

• 报表。
• 历史分析。
• 合规或计费。

与 Misra–Gries 的关系

Boyer–Moore 可以视为 Misra–Gries 算法在 k = 2 时的特例。Misra–Gries 将该思想推广为：

• 跟踪多个候选者。
• 仍然限制内存使用。
• 用覆盖率换取精确度。

深入研究 Misra–Gries 是进一步探讨的自然下一步。

探索的起源

调查始于一个 LeetCode 题目：

Majority Element II

解决这个问题很容易；但理解算法的合理性却不容易。

要点

• Boyer–Moore 不是一种精确计数算法。
• 它是一种 有界内存的优势信号。
• 以这种方式使用是有依据的。
• 以其他任何方式使用都是误导性的。