Skip to main content

2.2.1 GBV bitvector

要理解“把一整行压缩成一个位向量”，最好用一个具体的小例子。我们来看 Myers's bitvector 的核心思想：它不直接存储每个单元格的编辑距离分数，而是存储相邻单元格之间的差异，而这些差异可以用一位二进制表示。

1. 先看普通动态规划怎么存一行​

假设参考序列长度为 88，我们计算编辑距离矩阵的某一行。传统 DP 会存储 88 个整数，例如：

row=[3,3,4,4,4,5,5,6]\text{row} = [3, 3, 4, 4, 4, 5, 5, 6]

每个整数通常占 44 字节，一行就需要 3232 字节。而且更新这一行时，要逐个单元格计算。

2. Myers 的关键观察：增量可以用一位表示​

Myers 算法发现，在计算编辑距离时，相邻单元格的分数差只会是 00 或 +1+1（在它的差分表示中，可以只用一位表示“是否有增量”）。也就是说，我们不需要存绝对分数，只需要存每个位置相对于前一个位置是否“增加了 11”。

例如，上面那行分数：

[3,3,4,4,4,5,5,6][3, 3, 4, 4, 4, 5, 5, 6]

相邻差值（从第二个开始）：

3→3:0,3→4:+1,4→4:0,4→4:0,4→5:+1,5→5:0,5→6:+13 \to 3: 0,\quad 3 \to 4: +1,\quad 4 \to 4: 0,\quad 4 \to 4: 0,\quad 4 \to 5: +1,\quad 5 \to 5: 0,\quad 5 \to 6: +1

用 11 表示“增加了 11”，00 表示“没有增加”，就得到一个位序列：

0, 1, 0, 0, 1, 0, 10,\ 1,\ 0,\ 0,\ 1,\ 0,\ 1

这 77 位可以打包成一个字节（前面补一位）：

bitvector=0b0100101\text{bitvector} = 0b0100101

原本需要 88 个整数的信息，现在只用了一个字节就表达了整行的“形状”。

3. 为什么这样能并行​

有了这个位向量，整行的更新就可以用位运算一次完成，而不是逐个格子循环。例如：

  • 判断哪些位置匹配：可以用一个匹配位向量，和当前位向量做与、或、异或。
  • 模拟“插入/删除”操作：可以用移位和加法。
  • 一次处理 6464 位，也就是同时处理 6464 个单元格。

这就是 SIMD 并行：一条指令操作整个位向量，等于同时算了很多个格子。

4. 一个更贴近 Myers 的例子​

假设查询字符是 A，参考序列是 AGCT。我们想计算编辑距离矩阵中与查询 A 对应的一行。

先标记参考序列中哪些位置是 A：

  • 位置 1：A → 匹配，位 =1=1
  • 位置 2：G → 不匹配，位 =0=0
  • 位置 3：C → 不匹配，位 =0=0
  • 位置 4：T → 不匹配，位 =0=0

匹配位向量就是 1000。

Myers 算法会维护两个位向量，分别表示垂直差异和水平差异。然后通过一系列位运算，例如：

X = match | (Pv & ~Mv)
D = ((Pv + X) ^ Pv) | match
...

就能一次算出整行的编辑距离状态。这里我们不展开所有位运算，但关键是：整行信息被编码在几个 6464 位整数里，而不是一个整数数组。

5. 一句话总结​

把一整行压缩成一个位向量，就是：不再存储每个单元格的绝对分数，而是只存储相邻单元格的“增量”或“差异”，每个差异只用 11 位表示。 这样，6464 个单元格的状态就能塞进一个 6464 位整数里，然后用位运算一次更新整行，实现 SIMD 级别的并行。Myers's bitvector 正是靠这个技巧，在牺牲仿射间隙评分的情况下，换来了极高的计算效率。