字符串相似度：Bitap算法是如何工作的？

Question

我正在努力理解比特位匹配算法，但是我很难理解算法步骤背后的原因。

我理解算法的基本原理，即（如果我错了，请纠正我）：

Two strings:     PATTERN (the desired string)
                 TEXT (the String to be perused for the presence of PATTERN)

Two indices:     i (currently processing index in PATTERN), 1 <= i < PATTERN.SIZE
                 j (arbitrary index in TEXT)

Match state S(x): S(PATTERN(i)) = S(PATTERN(i-1)) && PATTERN[i] == TEXT[j], S(0) = 1

在英文中，“PATTERN.substring(0,i)”匹配TEXT的子字符串，如果先前的子字符串“PATTERN.substring(0, i-1)”已经成功匹配，并且PATTERN[i]处的字符与TEXT[j]处的字符相同。

我不理解的是这个算法的位移实现。官方论文详细介绍了这个算法的基本原理，但我似乎无法想象出应该发生什么。 算法规范只有论文的前两页，但我会强调重要的部分：

这是概念的位移版本：

这是一个示例搜索字符串的 T[text]：

这是算法的追踪记录。

具体来说，我不理解T表的意义，以及将其中一个条目与当前状态进行“或”操作的原因。

如果有人能帮助我理解正在发生的事情，我将不胜感激。

- Kevin

Answer 1

T 有点令人困惑，因为通常你会从左到右给模式中的位置编号：

0 1 2 3 4
a b a b c

相比之下，位数通常是从右到左编号。

但将模式反向写在位上方会让它更清晰：

  bit: 4 3 2 1 0

       c b a b a
T[a] = 1 1 0 1 0

       c b a b a
T[b] = 1 0 1 0 1
 c b a b a
T[c] = 0 1 1 1 1
c b a b a
T[d] = 1 1 1 1 1

T[x] 的第n位为0表示x出现在位置n，否则为1。

等价地，你可以认为如果输入字符串的当前字符是x，并且您看到T[x]中的第n位是0，那么只有在匹配开始n个字符之前才可能匹配模式。

---

现在，来看匹配过程。状态中第n位为0表示我们开始匹配模式n个字符前（其中0是当前字符）。最初，没有任何匹配。

  [start]
1 1 1 1 1

当我们消耗字符进行匹配时，状态向左移动（将零移入底部位，位0），并与当前字符的表格条目进行OR运算。第一个字符是a；左移并OR运算T[a]得到：

        a
1 1 1 1 0

保留移位的0比特，因为当前字符a可以开始匹配模式。对于任何其他字符，该比特都将被设置为1。

状态中比特0现在为0的事实意味着我们从当前字符开始匹配模式；继续进行，我们得到：

      a b
1 1 1 0 1

因为0位已向左移动-可以将其视为我们从1个字符前开始匹配该模式-并且T [b]在相同位置上有一个0，告诉我们如果我们从1个字符前开始匹配，则在当前位置看到b是好的。

    a b d
1 1 1 1 1

d无法匹配任何位置; 所有位都会被设置回1.

  a b d a
1 1 1 1 0

和以前一样。

a b d a b
1 1 1 0 1

与之前一样。

b d a b a
1 1 0 1 0

a 表示在当前字符或者前两个字符中出现都是正确的。

d a b a b
1 0 1 0 1

b表示如果匹配始于1或3个字符之前，则匹配很好。在第3位的0表示我们几乎匹配了整个模式...

a b a b a
1 1 0 1 0

...但下一个字符是a，如果匹配开始4个字符之前就不好了。然而，较短的匹配可能仍然是好的。

b a b a b
1 0 1 0 1

仍然看起来不错。

a b a b c
0 1 1 1 1

最后，如果匹配在4个字符之前开始，则c是好的。 事实上，一个0已经到达了最高位，这意味着我们有一个匹配。

- Matthew Slattery

---

抱歉打扰了这么老的问题，但是您如何扩展此算法以便处理带有误差的搜索？ - David S

@DavidS diff_match_patch 包含了一个具有错误容忍度的比特位实现。 - midrare

Answer 2

很抱歉不允许其他人回答，但我相信我现在已经弄清楚了。

理解该算法的关键概念是将匹配状态（在原帖中定义）用二进制表示。原帖中的文章对此进行了正式解释；我将尝试以通俗易懂的方式进行解释：

假设有一个由给定字母表中的字符创建的字符串STR。

让我们用一组二进制数字STR_BINARY来表示STR。该算法要求这种表示方式是反向的（因此，第一个字母对应于最后一个数字，第二个字母对应于倒数第二个数字，依此类推）。

假设RANDOM是指具有与创建STR的相同字母表的随机字符的字符串。

在STR_BINARY中，给定索引处的0表示RANDOM从STR[0]到匹配STR。

STR[(STR_BINARY中0对应的字母在STR中的索引)]。空格也算匹配。1表示RANDOM在相同范围内与STR不匹配。

一旦理解了这一点，算法就变得更容易学习了。

- Kevin