Bitap：我最喜欢的字符串匹配算法
文章摘要
作者 Joseph Liu（HN 用户名 jo3_l）写了一篇约 1800 字的教学性博文，介绍一个相对冷门的字符串匹配算法 bitap（也叫 shift-and 算法）。文章的核心亮点不在于算法本身有多快，而在于作者用一条清晰的推导链，从最朴素的暴力匹配一步步演化出 bitap，让人看完觉得”这不过是换了身衣服的暴力算法”。
问题与背景
经典问题：在文本 T 中找出模式 P 第一次出现的位置。业界的标准答案是 Boyer-Moore、Knuth-Morris-Pratt（KMP）和 Two-Way。bitap 的适用范围窄得多——只有当模式 P 的长度小于机器字长时才高效。但作者喜欢它，因为它既容易理解又容易实现，而且把位运算用得特别优雅。
第一步：朴素算法
最简单的暴力法就是从 T 的每个可能起点尝试逐字符匹配 P，一旦失配就换下一个起点。
第二步：改造成流式
作者接着加了一条人为约束来推动演化：假设 T 不是一次性给全的，而是以流的形式一个字符一个字符送进来（比如 T 非常长，不想全部载入内存）。朴素算法做不到，因为它需要从当前位置向前预读最多 len(P) 个字符。
改造思路是：不再从每个起点向前预读，而是在扫描 T 的过程中维护一组”进行中的匹配”。概念上每个进行中的匹配由”已匹配的 P 的前缀”和”尚未匹配的后缀”组成。读到新字符 c 时，推进那些正期待 c 的匹配，杀掉其余的；一旦某个活跃匹配走到 P 的末尾，就找到了答案。
第三步：用整数表示状态
进一步优化：每个进行中的匹配状态其实可以只用一个整数 j 表示——即 P 中下一个待匹配字符的下标（对应的未匹配后缀就是 P[j:]）。于是活跃集合变成了一个整数列表。
第四步：用位集合压缩
关键观察来了：活跃集合里的整数永远落在 0 到 len(P) 之间。如果 P 不长（比如 len(P) < 64），就可以把整个活跃集合打包进一个 64 位整数当位集合用。例如活跃集合是 {1, 2, 7} 时，位集合就是 0b1000_0110。
不过作者诚实地指出，光是这一步并没有实质改进——编码更紧凑了，但仍然是两层嵌套循环。真正的问题是：内层循环能不能消掉？
第五步：视角翻转，得到 bitap
答案是可以，靠的是一次小小的视角转换。前面的做法是”逐个检查每个匹配状态能否继续，能就前进一位”；替代做法是：先无条件把所有状态前进一位，再杀掉那些来自非法转移的状态。这两步的妙处在于，都能用一条作用于整个位集合的位运算完成。
- 前进一位 = 左移一位：
active << 1 - 杀掉非法转移 = 与一个预计算的掩码取交集
第二个洞见是：可以为模式中出现的每个字符预先算出一张位掩码表——看到字符 c 之后，哪些状态是合法可达的。构建方式是遍历 P，对每个位置 j 的字符 c，把 validMask[c] 的第 j+1 位置 1。
于是主循环就浓缩成了一行：新的活跃集合 = (active << 1) & validMask[c]，再检查第 len(P) 位是否被点亮即可判断匹配完成。这就是 shift-and（左移，然后按位与）名字的由来。
作者补充了两点实现细节：通常的教科书写法索引约定会错开一位，在实践中更合适，但精神相同；另外还有一个更高效的变体 shift-or，它把所有掩码取反并改用按位或，每个输入字符能少做一次位运算。
那么，然后呢？
文章末尾作者很坦率地给自己泼冷水：bitap 只在模式较短时才有意义。理论上可以用多字位集合推广到长模式，但收益递减。而且从渐进复杂度看，当模式长度有界为常数时，bitap 的运行时间和暴力算法完全一样（都是文本长度的线性）；在一次性的测试里，由于需要预计算掩码表，它甚至可能比暴力法更慢。
那为什么还喜欢它？作者的答案很个人化：因为它概念上优雅、能从朴素算法自然推导出来。他说自己也详细研究过 Boyer-Moore 和 KMP，但要从零重新推导它们得花上不少时间，而 bitap”对我来说就是换了身装扮的朴素算法”。文末脚注里他还自嘲：希望有朝一日能从零推导出 Two-Way，”我甚至都不理解它是怎么工作的”。另一条脚注澄清，本文讲的是精确匹配版本；bitap 这个名字也常指支持 Levenshtein 距离模糊匹配的变体，那个很酷但不是本文主题。
HN 评论精华
这条帖子分数不高（29 分，约 14 条评论），但讨论质量相当集中，基本是几位真正做过字符串搜索实现的人在交流。
作者亲自下场谈性能边界
jqpabc123 提出质疑：他能理解这个算法对中等长度（最多 64 字节）的模式有优势，但对于寄存器大小的短模式（4 或 8 字节），他怀疑它比不上一个紧凑的、按多字节块比较的暴力循环。
jo3_l（原文作者本人）直接承认对方是对的：对短模式来说 bitap 相对暴力法几乎没有优势，事实上暴力法在很多情况下反而更快——暴力法每轮和模式的比较本质上就是一次 memcmp，在现代硬件上会被向量化，跑得非常快。他补充说，据他所知所有主流编程语言在模式较短时都直接退回暴力算法，而不是用 bitap 这类更复杂的东西；正因为如此，他在原文里刻意谨慎，没有夸大性能收益。
jqpabc123 顺势问：那为什么不干脆用快速 memcmp 比对模式的前 4 到 8 个字符来定位候选，找到后再验证完整匹配？他说自己多年来就是这么做的，很简单，虽然未必最快但在实际场景中表现不赖。
MattPalmer1086 给出了为什么长模式需要更复杂算法的两条理由：第一是线性性——朴素方法在最坏情况数据上是二次的（想象在全是 0 的文本里搜 100 个 0）；第二是次线性——次线性搜索算法会跳过不可能匹配的文本，它们有个反直觉的性质：模式越长反而越快。jqpabc123 最后半开玩笑地回应：长模式算是异类，他日常做的搜索和解析大多是短模式，”也许我才是那个异类”。
一位算法作者的实践反馈
MattPalmer1086 还贡献了两条很有分量的评论。其一：他上个周末刚好在更新自己的字符串搜索算法，把模式长度小于 64 时使用的 KMP 换成了 bitap（shift-or 变体），结果更快了，并称这是个非常可爱的算法。他的算法 HashChain 是一个很快的次线性算法，但用 KMP（现在是 bitap）来验证匹配，因此最坏情况是线性的，而不像 Boyer-Moore-Horspool 那样是二次的。
其二是对文章的一处技术指正：作者说朴素算法是线性的，这对平均情况也许成立，但它的最坏情况复杂度是二次的；而 bitap 即便在最坏情况下也是线性的。他同时称赞这是一次很棒的从第一性原理推导 bitap 的讲解，此前没见过。
另一派：SIMD 字符串搜索
Rendello 说自己也有个最爱的字符串匹配算法——来自 Wojciech Muła 那篇 SIMD strfind 笔记里的”Generic SIMD”，并提到当年那条 HN 讨论里有 ripgrep 作者 burntsushi 的精彩发言。他推荐了 burntsushi 维护的三层工具链：底层 memchr、中层 Rust regex crate、高层 ripgrep，理由是文档齐全、模块化拆分清晰、覆盖从低到高的各个层次。他还点名 Wojciech Muła 和 simdjson 的 Daniel Lemire，并提到面向数据的设计（Data-Oriented Design）对思考 SIMD 和缓存友好的数据布局很有帮助。
MattPalmer1086 回应说自己一直对用 SIMD 加速搜索感兴趣，但至今没找到一个真正令人满意的方案——需要搞清楚它们各自擅长的领域，”没有哪一种搜索对所有数据类型和模式/搜索长度都是最优的”。
skrellm 则贴出了自己基于 Muła 工作实现的 SIMD 加速大小写不敏感搜索，做成 stb 风格的单头文件库，README 里的性能对比显示比 libc 快约 6 倍。限制是：虽然完整支持 UTF-8，但只适用于大小写形式 UTF-8 编码长度相同的码位——40576 对里有 27 对不满足。
意外的 Unicode 支线
skrellm 这条限制说明引出了一段 Unicode 吐槽。Rendello 说正是这同一个性质当年把他拖进了认真学习 Unicode 的兔子洞，还促使他开始做一个 Unicode 工具（”也许这个千年之内能发个初版”）。skrellm 抱怨 Unicode 在这件事上搞得一团糟：有时大小写之间是固定偏移（拉丁字母 ±32），有时大小写交错排列（拉丁扩展），有时因为当初忘了同时添加两种字形，大小写干脆落在完全不同的区块里——而码位距离对 UTF-8 编码长度差异的影响最大。他说自己针对”两种编码首字节相同”这个最常见情况（40549 对中的 40508 对）做了优化，但剩下 41 对必须走更慢的特殊路径，”要是当初 Unicode 那帮人功课做得好些，这条路径根本不需要”。
Rendello 补了一个他最喜欢的例子：连字 “ff” 大写后变成 “FF”，从一个字符变成两个字符，总字节数却从 3 字节降到 2 字节。他顺带提醒，这还没涉及 Casefold、NFKC_Casefold、简单与复杂大小写映射、CLDR 等更深的坑。