21

我正在尝试围绕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 与字符 atPATTERN[i]相同，则匹配 TEXT 的子字符串TEXT[j]。

我不明白的是这个的位移实现。详细介绍该算法的官方论文基本上已经列出，但我似乎无法想象应该发生什么。 算法规范只是论文的前 2 页，但我会强调重要的部分：

这是该概念的位移版本：

在此处输入图像描述

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

在此处输入图像描述

这是算法的痕迹。

在此处输入图像描述

具体来说，我不明白 T 表的含义，以及OR使用当前状态在其中添加条目的原因。

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

4

2 回答 2

16

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

0 1 2 3 4
a b a b c

...而位通常从右到左编号。

但是将模式向后写在位上方可以清楚地表明：

  位：4 3 2 1 0

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

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

       巴巴_
T[c] = 0 1 1 1 1

       巴巴
T[d] = 1 1 1 1 1

位n的T[x]is0如果x出现在位置n中，或者1不出现。

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

现在进入匹配程序。状态的第n0位中的A表示我们在n 个字符之前开始匹配模式（其中 0 是当前字符）。最初，没有任何匹配项。

  [start]
1 1 1 1 1

当我们消耗试图匹配的字符时，状态向左移动（将零移到底部位，位 0）并与当前字符的表条目进行或运算。第一个字符是a; 左移和 OR-ingT[a]给出：

        a
1 1 1 1 0

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

状态的第 0 位现在0意味着我们开始匹配当前字符的模式；继续，我们得到：

      a b
1 1 1 0 1

...因为该0位已向左移动 - 认为它是说我们开始匹配模式 1 字符之前 - 并且在同一位置T[b]有 a ，告诉我们如果我们开始匹配，在当前位置0看到 a是好的b1 个字符前。

    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 个字符前开始，则很好。0in bit 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

最后，如果匹配在 4 个字符之前开始，那就太好了c 。a0已经达到最高位的事实意味着我们有一场比赛。

于 2012-07-04T00:25:24.783 回答
1

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

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

Let's have STR，它是使用给定字母表中的字符创建的字符串。

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

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

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

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

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

于 2012-07-04T00:17:40.100 回答