c - Boyer-Moore良好后缀的启发式方法

Question

我了解不良字符启发法的工作原理。当找到不匹配的字母x时，只需移动模式，以使模式中最右边的x与字符串中的x对齐。而且很容易在代码中实现。

我想我也了解后缀启发式的工作原理。当找到合适的后缀s时，请在模式中的不同位置找到相同的后缀，然后将其移动，以使模式中的s与字符串中的s对齐。但是我不明白如何在代码中做到这一点。我们如何查找模式中另一个位置是否存在相同的后缀？我们如何知道它的位置？代码：

void bmPreprocess1()
{
    int i=m, j=m+1;
    f[i]=j;
    while (i>0)
    {
        while (j<=m && p[i-1]!=p[j-1])
        {
            if (s[j]==0) s[j]=j-i;
            j=f[j];
        }
        i--; j--;
        f[i]=j;
    }
}

从 http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/bmen.htm中获取对我来说没有意义...有人可以为此任务编写尽可能简单的伪代码吗？或以某种方式解释？

Answer 1

首先，我将使用p[i]表示模式中的字符，m模式长度，$模式中的最后一个字符，即$ = p[m-1]。

良好的后缀启发式案例1有两种情况。

情况1

考虑以下示例，

    leading TEXT cXXXbXXXcXXXcXXX rest of the TEXT
         cXXXbXXXcXXXcXXX
                     ^ 
                     | mismatch here

因此，模式 XXX中的子字符串 cXXXbXXXcXXXcXXX是很好的后缀。不匹配发生在字符 c。那么在不匹配之后，我们应该将4移到右边还是8？

如果我们按如下所示将4移位，则将再次发生相同的错误（ b导致错误 c），

    leading TEXT cXXXbXXXcXXXcXXX rest of the TEXT
             cXXXbXXXcXXXcXXX
                     ^ 
                     | mismatch occurs here again

因此，在这种情况下，我们实际上可以向右移动8个字符。

情况二

让我们来看另一个例子

    leading TEXT cXXXcXXXbXXXcXXX rest of the TEXT
            cXXXXcXXXbXXXcXXX
                         ^ 
                         | mismatch happens here

我们可以在这里移动4或8或更多吗？显然，如果我们移位8或更多，我们将错过将模式与文本匹配的机会。因此，在这种情况下，我们只能向右移动4个字符。

那么这两种情况有什么区别？

区别在于，在第一种情况下，不匹配的字符 c加上后缀 XXX为 cXXX，与下一个（从右数起）匹配的 XXX加上前一个字符相同那。在第二种情况下， cXXX与下一个匹配项（从右数起）加上该匹配项之前的字符不同。

因此，对于任何给定的GOF SUFFIX（让我们将其称为 XXX），我们需要弄清楚这两种情况下的变化，（1）在GOOD SUFFIX和GOOD SUFFIX之前的字符（我们将其称为 c），模式中的字符也匹配好后缀+下一个字符的下一个（从右数）匹配，（2）字符加GOF SUFFIX不匹配

例如，对于情况（1），如果具有模式 0XXXcXXXcXXXcXXXcXXXcXXX，并且在 c的第一次测试失败后，则可以向右移动20个字符，并使 0XXX与测试的文本对齐。

这就是数字20的计算方式，

              1         2
    012345678901234567890123
    0XXXcXXXcXXXcXXXcXXXcXXX
    ^                   ^

发生不匹配的位置是20，移位后的子字符串 0XXX的位置将从20到23。 0XXX从位置0开始，所以20-0 = 20。

对于情况（2），如本例中的 0XXXaXXXbXXXcXXX，如果 c的第一次测试失败，则只能向右移动4个字符，并使 bXXX与测试的文本对齐。

这就是数字 4的计算方式，

    0123456789012345
    0XXXaXXXbXXXcXXX

发生不匹配的位置是12，下一个要代替的子字符串是 bXXX，它从位置8、12-8 = 4开始。如果我们设置 j = 12和 i = 8，则移位是 ，在代码中为 j - i。

边境

要考虑所有的后缀，我们首先需要了解什么是所谓的 s[j] = j - i;。
边框是一个子字符串，它既是字符串的 border前缀又是 proper后缀。例如，对于字符串 proper， XXXcXXX是边框， X是边框， XX也是如此。但是 XXX不是。我们需要确定模式后缀的最宽边界的起点，并且此信息保存在数组 XXXc中。

如何确定 f[i]？

假设我们知道 f[i]，并且对于所有其他 f[i] = j具有 f[k]的字母，这意味着从位置 i < k < m开始于位置 i的后缀的最宽边框。我们想基于 j查找 f[i-1]。

例如，对于模式 f[i]，在位置 aabbccaacc处，后缀为 i=4，其最宽边框为 ccaacc（ cc），因此为 p[8]p[9]。现在我们想根据对 j = f[i=4] = 8， f[i-1] = f[3]，...的信息来了解 f[4]，对于 f[5]，后缀现在为 f[3]。在 bccaacc位置，它是 j-1=7！= a，它是 p[4-1]。因此 b不是边界。

我们知道宽度<= 1的 bcc边界必须以 bccaacc开头，后缀的边界必须从positin b开始，在本例中为 j = 8。 cc在 cc位置上的 c边框最宽。因此，我们继续比较 j = f[8]与 9。他们又不平等了。现在后缀为 p[4-1]，并且在位置 p[j-1]处只有零长度的边框。所以现在是 p[9] = c，它是 10。因此，我们继续进行比较，将 j = f[9]与 10进行比较，它们不相等，那就是字符串的结尾。那么 p[4-1]仅具有零长度的边框，使其等于10。

从更一般的意义上描述过程

因此， p[j-1]的含义是这样的，

    Position:    012345     i-1  i     j - 1   j       m
    pattern:     abcdef ... @    x ... ?       x ...   $ 

如果位置 f[3]处的字符 f[i] = j与位置 @处的字符 i - 1相同，我们知道
?或 j - 1。边框后缀 f[i - 1] = j - 1;从位置 --i; --j; f[i] = j;开始。

但是，如果位置 @x ... $上的字符 j-1与位置 @上的字符 i - 1不同，
我们必须继续在右侧搜索。我们知道两个事实：（1）现在我们知道边界宽度必须小于从位置 ?开始的宽度，即小于 j - 1。其次，边框必须以 j开头并以字符 x...$结束，否则可以为空。

基于这两个事实，我们继续在子字符串 @...（从位置j到m）中搜索以 $开头的边框。然后，下一个边框应位于等于 x ... $的 x，即 j。然后，我们将字符 f[j];与 j = f[j];之前的字符（在 @处）进行比较。如果它们相等，则找到边界，否则，继续进行处理，直到j> m。以下代码显示了此过程，

    while (j<=m && p[i-1]!=p[j-1])
    {
        j=f[j];
    }

    i--; j--;
    f[i]=j;

现在查看条件 x p [j-1] j-1 p [i] p[i -1] != p [j] , this is what we talked about in situation (2), p [i -1]！= matches，因此我们从 , but转换为 p[j-1]，即 i。

现在剩下的唯一没有解释的是测试 j，当较短的后缀具有相同的边框时，将发生该测试。例如，您有一个模式

    012345678
    addbddcdd

计算 s[j] = j - i;和 if (s[j] == 0)时，将设置 f[i - 1]。但是，当您为 i = 4计算 s[7]时，如果没有测试 f[i-1]，则将再次设置 i = 1。这意味着，如果在位置 s[7]不匹配，则将 if (s[j] == 0)向右移动（将 6与所占据的位置 3对齐）而不是 bdd（直到 cdd移至位置 6占据）。

代码注释

    void bmPreprocess1()
    {
        // initial condition, set f[m] = m+1;
        int i=m, j=m+1;

        f[i]=j;

        // calculate f[i], s[j] from i = m to 0.
        while (i>0)
        {
            // at this line, we know f[i], f[i+1], ... f[m].
            while (j<=m && p[i-1]!=p[j-1]) // calculate the value of f[i-1] and save it to j-1
            {
                if (s[j]==0) s[j]=j-i; // if s[j] is not occupied, set it.
                j=f[j]; // get the start position of the border of suffix p[j] ... p[m-1]
            }
            // assign j-1 to f[i-1]
            i--; j--;
            f[i]=j;
        }
    }