2. Bitap Example

下面用一个具体的小例子，完整演示 Bitap 算法的遍历过程。为了便于手算，取很短的序列和错误阈值。

---

例子设定

• 字母表：$\{A, C, G, T\}$
• 查询模式：$P = \text{"AC"}$，长度 $m = 2$
• 参考文本：$T = \text{"AGC"}$，长度 $n = 3$
• 最大编辑距离：$k = 1$

位向量长度等于模式长度 $m = 2$。我们用两位二进制表示，左边为最高有效位（MSB，位 1），右边为最低有效位（LSB，位 0）。
约定：位值为 0 表示匹配。

模式字符与位的对应关系：

• 模式第 0 个字符 'A' 对应 位 0（LSB）
• 模式第 1 个字符 'C' 对应 位 1（MSB）

因此，预处理得到的模式位掩码（Pattern Bitmask, PM）为：

字符	位 1 (MSB)	位 0 (LSB)	二进制
A	1	0	10
C	0	1	01
G	1	1	11
T	1	1	11

初始状态位向量（允许 $d$ 个错误）：

• $R[0] = 11$
• $R[1] = 11$

Bitap 算法从文本末尾向前遍历，因此处理顺序为：位置 2 ('C') → 位置 1 ('G') → 位置 0 ('A')。

---

迭代 1：文本位置 $i = 2$，字符 'C'

保存上一轮状态： $oldR[0] = 11$，$oldR[1] = 11$

当前字符 'C' 的位掩码：$curPM = PM['C'] = 01$

计算 $R[0]$（精确匹配）

$$R[0] = (oldR[0] \ll 1) \ | \ curPM$$

• $oldR[0] \ll 1$：11 左移一位，丢弃最高位，低位补 0 → 10
• $10 \ | \ 01 = 11$

所以 $R[0] = 11$。

计算 $R[1]$（允许 1 个错误）

需要四个中间位向量：

• 删除：$D = oldR[0] = 11$
• 替换：$S = (oldR[0] \ll 1) = 10$
• 插入：$I = (R[0] \ll 1) = (11 \ll 1) = 10$
• 匹配：$M = (oldR[1] \ll 1) \ | \ curPM = (11 \ll 1) \ | \ 01 = 10 \ | \ 01 = 11$

然后按位与：

$$R[1] = D \ \& \ S \ \& \ I \ \& \ M = 11 \ \& \ 10 \ \& \ 10 \ \& \ 11 = 10$$

检查 MSB

• $R[0] = 11$，MSB = 1，不是 0
• $R[1] = 10$，MSB = 1，不是 0

没有找到匹配。

---

迭代 2：文本位置 $i = 1$，字符 'G'

保存上一轮状态： $oldR[0] = 11$，$oldR[1] = 10$

当前字符 'G' 的位掩码：$curPM = PM['G'] = 11$

计算 $R[0]$

$$R[0] = (oldR[0] \ll 1) \ | \ curPM = (11 \ll 1) \ | \ 11 = 10 \ | \ 11 = 11$$

计算 $R[1]$

• $D = oldR[0] = 11$
• $S = (oldR[0] \ll 1) = 10$
• $I = (R[0] \ll 1) = (11 \ll 1) = 10$
• $M = (oldR[1] \ll 1) \ | \ curPM = (10 \ll 1) \ | \ 11 = 00 \ | \ 11 = 11$

$$R[1] = 11 \ \& \ 10 \ \& \ 10 \ \& \ 11 = 10$$

检查 MSB

• $R[0] = 11$，MSB = 1
• $R[1] = 10$，MSB = 1

仍然没有匹配。

---

迭代 3：文本位置 $i = 0$，字符 'A'

保存上一轮状态： $oldR[0] = 11$，$oldR[1] = 10$

当前字符 'A' 的位掩码：$curPM = PM['A'] = 10$

计算 $R[0]$

$$R[0] = (oldR[0] \ll 1) \ | \ curPM = (11 \ll 1) \ | \ 10 = 10 \ | \ 10 = 10$$

计算 $R[1]$

• $D = oldR[0] = 11$
• $S = (oldR[0] \ll 1) = 10$
• $I = (R[0] \ll 1) = (10 \ll 1) = 00$
• $M = (oldR[1] \ll 1) \ | \ curPM = (10 \ll 1) \ | \ 10 = 00 \ | \ 10 = 10$

$$R[1] = D \ \& \ S \ \& \ I \ \& \ M = 11 \ \& \ 10 \ \& \ 00 \ \& \ 10 = 00$$

检查 MSB

• $R[0] = 10$，MSB = 1，不是 0
• $R[1] = 00$，MSB = 0 ✅

找到匹配！
此时 $i = 0$，$d = 1$。
表示从文本位置 0 开始，存在一个编辑距离为 1 的匹配。

---

结果解释

文本从位置 0 开始的子串是 "AGC"，模式是 "AC"。
它们之间的编辑距离为 1（删除中间的 'G' 即可得到 "AC"）。
因此 Bitap 算法输出：

• 匹配起始位置：$startLoc = 0$
• 编辑距离：$editDist = 1$

---

总结

这个例子展示了 Bitap 的核心机制：

1. 位向量编码：用 0/1 表示模式字符的匹配状态。
2. 逐字符向前遍历：从文本末尾到开头。
3. 位运算更新：通过左移、或、与操作同时计算所有可能的部分匹配。
4. MSB 检测：当某个 $R[d]$ 的最高位变为 0 时，说明整个模式匹配完成，且编辑距离为 $d$。

原始 Bitap 受限于机器字长（位向量长度不能超过一个字），且迭代间存在数据依赖，无法直接并行。GenASM 正是通过多字扩展、循环展开和专用硬件设计，克服了这些限制，从而高效支持长读长和回溯操作。