字符串相似性:Bitap究竟是如何工作的？

Question

我试图围绕Bitap算法,但我无法理解算法步骤背后的原因.

我理解算法的基本前提,即(如果我错了,请纠正我):

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) 如果前一个子字符串PATTERN.substring(0, i-1)成功匹配且字符at与字符at PATTERN[i]相同,则匹配TEXT的子字符串TEXT[j].

我不明白的是这个位移实现.详细介绍这个算法的官方文章基本上已经解决了,但我似乎无法想象应该发生什么. 算法规范只是本文的前两页,但我将重点介绍重要部分:

以下是该概念的位移版本:

以下是样本搜索字符串的T [text]:

这是一个算法的痕迹.

具体来说,我不明白T表的含义,以及OR当前状态下输入的原因.

如果有人能帮我理解到底发生了什么,我将不胜感激

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]是0,如果x出现在位置ñ,或者1如果它不.

同样地,你可以认为这是说,如果在输入字符串当前字符是x,你可以看到一个0位置ň的T[x],那么你只能将可能与模式匹配的,如果比赛开始ñ前面的字符.

现在到匹配程序.甲0比特Ñ状态意味着我们的图案开始匹配Ñ字符前(其中0是当前字符).最初,没有任何匹配.

  [start]
1 1 1 1 1

当我们消耗试图匹配的字符时,状态向左移动(将零移位到底部位,位0)并且与当前字符的表条目进行OR运算.第一个角色是a; 向左移动和OR-ing 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相同的位置,告诉我们b如果我们开始匹配,在当前位置看到a 是好的1个字符前.

    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 如果匹配开始前2个字符或当前字符,那就好了.

d a b a b
1 0 1 0 1

b如果比赛在1或3个字符之前开始,那就很好.在0中位3意味着我们几乎与整个模式...

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

最后,c 是一件好事,如果在比赛前开始的4个字符.事实上,a 0一直到最高位意味着我们有匹配.

Answer 2

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

理解该算法的基本概念是用二进制表示匹配状态（在原始帖子中定义）。原帖中的文章正式解释了这一点；我将尝试用通俗的方式这样做：

让我们来看看STR，它是一个用给定字母表中的字符创建的字符串。

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

让我们假设 指RANDOM的是一个由来自相同字母表的随机字符STR创建的字符串。

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

STR[(index of letter in STR that the 0 in STR_BINARY corresponds to)]。空格算作匹配。1 表示在相同边界内RANDOM不匹配。STR

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