1. Bitap Algorithm

论文第 2.3 节 Bitap Algorithm 介绍了 GenASM 所基于的核心近似字符串匹配算法——Bitap。下面根据论文内容，用中文解释该算法的原理与流程。

Bitap 算法的目标

Bitap 算法用于在给定参考文本（如参考基因组）和查询模式（如 read）之间，计算允许最多 $k$ 个错误的最小编辑距离。

Bitap 的核心思想是位并行：用二进制位向量表示模式与文本的部分匹配状态，通过简单的位运算（移位、与、或）同时处理多个位置，因此非常适合硬件加速。

算法从文本的最后一个字符开始，向前遍历每个文本字符（算法中 for i in (n-1):-1:0），每次处理一个字符。
对于当前文本字符 curChar：

取出该字符对应的模式位掩码 $curPM = PM[curChar]$ 。
计算精确匹配状态 $R[0]$ ：
$R[0] = (oldR[0] \ll 1) \ | \ curPM$
这里左移一位表示消耗一个模式字符，或上 $curPM$ 表示当前文本字符与模式字符的匹配情况。
对于每个编辑距离 $d = 1 \dots k$ ，计算四种中间位向量： 1.) $oldR$ 代表上一个文本位置（因为算法是从文本末尾向前遍历， $oldR$ 是文本位置 $i+1$ 的状态）。使用 $oldR$ 意味着消耗了一个文本字符。

2). $R$ 代表当前文本位置（文本位置 $i$ 的状态）。使用 $R$ 意味着没有消耗文本字符（文本指针停在原地）。

删除（Deletion, D）：当前模式字符缺失，只消耗文本字符，不消耗模式字符，错误数加 1。 $D = oldR[d-1]$

文本位置 $i+1$ 的 $d-1$ 个错误状态，到达 $d$ 状态，需由当前文本位置 $i+1$ 的 $d-1 \to d$ 转换而来
替换（Substitution, S）：当前模式字符与文本字符不匹配，同时消耗文本和模式字符，错误数加 1。 $S = (oldR[d-1] \ll 1)$

文本位置 $i+1$ 的 $d-1$ 个错误状态, 消耗模式字符，到达 $d$ 状态，需由当前文本位置 $i+1$ 的 $d-1 \to d$ 转换而来
插入（Insertion, I）：当前文本字符缺失，只消耗模式字符，不消耗文本字符，错误数加 1。 $I = (R[d-1] \ll 1)$

文本位置 $i$ 的 $d-1$ 个错误状态, 消耗模式字符，到达 $d$ 状态，需由当前文本位置 $i$ 的 $d-1 \to d$ 转换而来
匹配（Match, M）：当前模式字符与文本字符匹配，同时消耗文本和模式字符，错误数不变。 $M = (oldR[d] \ll 1) \ | \ curPM$

文本位置 $i+1$ 的 $d$ 个错误状态, 消耗模式字符, 因错误数不变，所以是第 $d$ 个错误状态

然后，将这四个中间位向量按位与（AND），得到当前编辑距离 $d$ 的状态位向量：

R[d] = D \ \& \ S \ \& \ I \ \& \ M

按位与的作用是保留所有可能的部分匹配位置（即所有位中为 0 的位置），表示在允许 $d$ 个错误时，从当前位置开始可能存在的匹配。

检测匹配：
- 检查每个 $R[d]$ 的最高有效位（MSB）。如果某一位为 0，则说明在文本位置 $i$ 处找到了一个匹配，其编辑距离为 $d$ 。
- 记录起始位置 $startLoc = i$ 和编辑距离 $editDist = d$ 。
- 算法继续遍历，直到所有文本位置都被检查完。

位向量的含义： $R[d]$ 中的每一位对应模式中的一个位置。某位为 0 表示从该位对应的模式位置开始，到当前文本位置为止，已经找到了一个允许 $d$ 个错误的匹配。
从后往前遍历：Bitap 通常从文本末尾向前扫描，这样左移操作对应模式字符的消耗，最终 MSB 为 0 表示整个模式匹配完成。
并行性：所有位运算都是按位操作，一条指令可以同时处理 $m$ 个位置，因此计算效率高。
复杂度：时间复杂度为 $O(n \cdot k)$ 次位运算，其中 $n$ 是文本长度， $k$ 是最大编辑距离。但原始 Bitap 受限于机器字长，模式长度不能超过一个字（如 64 位）。

论文指出原始 Bitap 存在五个主要限制，导致其难以直接用于基因组分析：

GenASM 正是针对这些限制，对 Bitap 进行了算法修改（支持多字、消除循环依赖、增加文本级并行）并设计了专用硬件加速器。