Wu-Manber改进版Bitap模糊搜索算法多错误计算咨询

参数定义澄清 #

不同文献的符号命名容易混淆，统一对应你给出的场景：

• $R_t$：t代表允许的最大错误数（即NFA的状态，$R_0$对应0错误，$R_1$对应最多1错误，$R_2$对应最多2错误）
• $j$：文本的遍历索引（逐个处理文本中的每个字符）
• $B[c]$：字符c对应的模式匹配位掩码，每一位对应模式的一个位置，1表示该字符匹配模式对应位置的字符

注意：你提供的位掩码中B["s"]和B["e"]均为0010，这是笔误。模式"rise"长度为4，正确的位掩码应为：

B["r"] = 1000  # 对应模式第1位
B["i"] = 0100  # 对应模式第2位
B["s"] = 0010  # 对应模式第3位
B["e"] = 0001  # 对应模式第4位
B[*] = 0000    # 其他字符

核心更新公式 #

对于允许t个错误的状态$R_t$（$t≥1$），每一步更新由两部分组成：

1. 无新增错误：从上一轮的$R_t$匹配当前字符

   ((R_t << 1) | 1) & B[c_j]
   

2. 新增一个错误：从上一轮的$R_{t-1}$通过插入、删除、替换操作产生一个错误，三种操作的位运算合并为：

   R_{t-1} << 1 | R_{t-1} | R_{t-1} >> 1
   

完整更新公式：

R'_t = [((R_t << 1) | 1) & B[c_j]] | [R_{t-1} << 1 | R_{t-1} | R_{t-1} >> 1]

所有$R_t$初始值为0000（二进制）。

1错误场景（$R_1$）计算步骤 #

文本为"surprise"（字符顺序：s, u, r, p, r, i, s, e），初始状态$R_0=0000$，$R_1=0000$。

前7个字符处理后，$R_0$和$R_1$均为0000，重点看最后一个字符e（$j=7$）的计算：

1. 先更新$R_0$：

   R'_0 = ((0000 << 1) | 1) & B["e"] = 0001 & 0001 = 0001
   

2. 再更新$R_1$：
   • 无新增错误部分：((0000 << 1) | 1) & 0001 = 0001 & 0001 = 0001
   • 新增错误部分：0001 << 1 | 0001 | 0001 >> 1 = 0010 | 0001 | 0000 = 0011
   • 合并结果：0001 | 0011 = 0011

最终$R_1=0011$，最低位为1，说明存在最多1错误的匹配（此处因0错误已匹配，1错误必然匹配）。

2错误场景（$R_2$）计算步骤 #

初始状态$R_0=0000$，$R_1=0000$，$R_2=0000$。

$R_2$的更新规则为：

R'_2 = [((R_2 << 1) | 1) & B[c_j]] | [R_1 << 1 | R_1 | R_1 >> 1]

同样看最后一个字符e（$j=7$）的计算：

1. 此时上一轮$R_1=0000$（$j=6$时的状态），$R_2=0000$
2. 无新增错误部分：((0000 << 1) | 1) & 0001 = 0001 & 0001 = 0001
3. 新增错误部分：0000 << 1 | 0000 | 0000 >> 1 = 0000
4. 合并结果：0001 | 0000 = 0001

最终$R_2=0001$，最低位为1，说明存在最多2错误的匹配。

内容的提问来源于stack exchange，提问作者WAATS