c++ - 后缀数组算法

Question

经过大量的阅读之后，我弄清楚了后缀数组和LCP数组代表什么。

后缀数组:表示数组每个后缀的_lexicographic等级。

LCP数组:按字典顺序对两个连续后缀之间的最大长度前缀匹配进行匹配。

几天以来，我一直在努力理解后缀数组和LCP算法的工作原理。

这是代码，摘自Codeforces:

/*
Suffix array O(n lg^2 n)
LCP table O(n)
*/
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

#define REP(i, n) for (int i = 0; i < (int)(n); ++i)

namespace SuffixArray
{
    const int MAXN = 1 << 21;
    char * S;
    int N, gap;
    int sa[MAXN], pos[MAXN], tmp[MAXN], lcp[MAXN];

    bool sufCmp(int i, int j)
    {
        if (pos[i] != pos[j])
            return pos[i] < pos[j];
        i += gap;
        j += gap;
        return (i < N && j < N) ? pos[i] < pos[j] : i > j;
    }

    void buildSA()
    {
        N = strlen(S);
        REP(i, N) sa[i] = i, pos[i] = S[i];
        for (gap = 1;; gap *= 2)
        {
            sort(sa, sa + N, sufCmp);
            REP(i, N - 1) tmp[i + 1] = tmp[i] + sufCmp(sa[i], sa[i + 1]);
            REP(i, N) pos[sa[i]] = tmp[i];
            if (tmp[N - 1] == N - 1) break;
        }
    }

    void buildLCP()
    {
        for (int i = 0, k = 0; i < N; ++i) if (pos[i] != N - 1)
        {
            for (int j = sa[pos[i] + 1]; S[i + k] == S[j + k];)
            ++k;
            lcp[pos[i]] = k;
            if (k)--k;
        }
    }
} // end namespace SuffixArray

我不能，只是无法了解这种算法的工作原理。我尝试使用铅笔和纸写一个示例，并完成了所涉及的步骤，但由于两者之间的联系过于复杂，至少对于我来说，它们之间失去了联系。

高度赞赏有关示例的任何帮助。

Answer 1

总览

这是一种用于后缀数组构造的O(n log n)算法(或者，如果不是::sort而是使用2遍存储桶排序，则为O(n log n)算法)。

它首先对原始字符串S排序2克(*)，然后对4克，然后对8克等等进行排序，因此在第i次迭代中，我们对2i克进行了排序。显然，这样的迭代最多只能有log2(n)个，其诀窍是，通过确保在O(1)中完成两个2i-gram的每个比较，可以方便地在第i步中对2i-gram进行排序。时间(而不是O(2i)时间)。

它是如何做到的？好吧，在第一个迭代中对2克(又称双字母组)进行排序，然后执行所谓的词典重命名。这意味着它将创建一个新数组(长度为n)，该数组为每个bigram存储其在bigram排序中的排名。

词典重命名示例:假设我们有一个排序的列表，其中包含一些双字母组{'ab','ab','ca','cd','cd','ea'}。然后我们从左到右分配等级(即字典名称)，从等级0开始并在遇到新的双字母组变化时递增等级。因此，我们分配的等级如下:

ab : 0
ab : 0   [no change to previous]
ca : 1   [increment because different from previous]
cd : 2   [increment because different from previous]
cd : 2   [no change to previous]
ea : 3   [increment because different from previous]

这些等级被称为词典名称。

现在，在下一迭代中， ，我们对4克进行排序。这涉及不同4克之间的大量比较。我们如何比较两个4克？好吧，我们可以逐个字符地比较它们。每个比较最多可以进行4次操作。但是，相反，我们使用前面步骤中生成的排名表，通过查找其中包含的两个二元组的排名来进行比较。该等级代表先前2克排序中的字典顺序，因此，如果对于任何给定的4克，其前2克的等级高于其他4克的前2克，则它在字典上必须更大前两个字符中的某处。因此，如果对于两个4克，首2克的等级相同，则在前两个字符中它们必须相同。换句话说，在等级表中进行两次查找足以比较两个4克的所有4个字符。

排序后，我们再次为4克创建新的词典名称。

在第三次迭代中，我们需要按8克排序。同样，从上一步开始的字典顺序表中的两次查找足以比较两个给定8克的所有8个字符。

依此类推。每个迭代i都有两个步骤:

使用上一次迭代的词典名称以2i-gram进行排序，以使

能够分2个步骤(即O(1)时间)进行比较

创建新的词典名称

我们重复此过程，直到所有2i-gram都不同为止。如果发生这种情况，我们就完成了。我们怎么知道是否都不同？好吧，字典名称是从0开始的整数递增序列。因此，如果迭代中生成的最高字典名称与n-1相同，则每个2i-gram必须被赋予其自己的独特字典名称。

实作

现在，让我们看一下代码以确认所有这些。使用的变量如下:sa[]是我们正在构建的后缀数组。 pos[]是排名查找表(即，它包含词典名称)，具体地说，pos[k]包含上一步的k -th m-gram的词典名称。 tmp[]是用于帮助创建pos[]的辅助数组。

我将在代码行之间给出进一步的解释:

void buildSA()
{
    N = strlen(S);

    /* This is a loop that initializes sa[] and pos[].
       For sa[] we assume the order the suffixes have
       in the given string. For pos[] we set the lexicographic
       rank of each 1-gram using the characters themselves.
       That makes sense, right? */
    REP(i, N) sa[i] = i, pos[i] = S[i];

    /* Gap is the length of the m-gram in each step, divided by 2.
       We start with 2-grams, so gap is 1 initially. It then increases
       to 2, 4, 8 and so on. */
    for (gap = 1;; gap *= 2)
    {
        /* We sort by (gap*2)-grams: */
        sort(sa, sa + N, sufCmp);

        /* We compute the lexicographic rank of each m-gram
           that we have sorted above. Notice how the rank is computed
           by comparing each n-gram at position i with its
           neighbor at i+1. If they are identical, the comparison
           yields 0, so the rank does not increase. Otherwise the
           comparison yields 1, so the rank increases by 1. */
        REP(i, N - 1) tmp[i + 1] = tmp[i] + sufCmp(sa[i], sa[i + 1]);

        /* tmp contains the rank by position. Now we map this
           into pos, so that in the next step we can look it
           up per m-gram, rather than by position. */
        REP(i, N) pos[sa[i]] = tmp[i];

        /* If the largest lexicographic name generated is
           n-1, we are finished, because this means all
           m-grams must have been different. */
        if (tmp[N - 1] == N - 1) break;
    }
}

关于比较功能

函数sufCmp用于按字典顺序比较两个(2 * gap)-gram。因此，在第一个迭代中，它比较双字母组，在第二个迭代中，它比较4克，然后是8克，依此类推。这是由gap控制的，它是一个全局变量。
sufCmp的一个简单的实现是这样的:

bool sufCmp(int i, int j)
{
  int pos_i = sa[i];
  int pos_j = sa[j];

  int end_i = pos_i + 2*gap;
  int end_j = pos_j + 2*gap;
  if (end_i > N)
    end_i = N;
  if (end_j > N)
    end_j = N;

  while (i < end_i && j < end_j)
  {
    if (S[pos_i] != S[pos_j])
      return S[pos_i] < S[pos_j];
    pos_i += 1;
    pos_j += 1;
  }
  return (pos_i < N && pos_j < N) ? S[pos_i] < S[pos_j] : pos_i > pos_j;
}

这将比较第i个后缀pos_i:=sa[i]开头的(2 * gap)-gram与在第j个后缀pos_j:=sa[j]开头找到的gram。它会逐个字符地比较它们，即比较S[pos_i]和S[pos_j]，然后S[pos_i+1]和S[pos_j+1]等等。只要字符相同，它就会继续。一旦它们不同，如​​果第i个后缀的字符小于第j个后缀的字符，则返回1，否则返回0。 (请注意，返回return a<b的函数中的int表示如果条件为true，则返回1，如果条件为false，则返回0。)

返回语句中复杂的外观条件处理(2 * gap)-gram之一位于字符串末尾的情况。在这种情况下，即使所有(2 * gap)字符都被比较，pos_i或pos_j都将到达N，即使到该点为止的所有字符都相同。如果第i个后缀在末尾，则返回1；如果第j个后缀在末尾，则返回0。这是正确的，因为如果所有字符都相同，则较短的字符在字典上较小。如果pos_i已到达结尾，则第i个后缀必须比第j个后缀短。

显然，这种简单的实现是O(gap)，即它的复杂度在(2 * gap)-grams的长度上是线性的。但是，您的代码中使用的函数使用字典名称将其简化为O(1)(具体而言，最多进行两次比较):

bool sufCmp(int i, int j)
{
  if (pos[i] != pos[j])
    return pos[i] < pos[j];
  i += gap;
  j += gap;
  return (i < N && j < N) ? pos[i] < pos[j] : i > j;
}

如您所见，我们没有查找单个字符S[i]和S[j]，而是检查了第i和第j后缀的词典顺序。在以前的迭代中为间隙图计算了辞书等级。因此，如果是pos[i] < pos[j]，则第i个后缀sa[i]必须以一个间隔词开始，该词在字典上小于sa[j]开头的差距词。换句话说，仅通过查找pos[i]和pos[j]并进行比较，我们就比较了两个后缀的第一个空格字符。

如果等级相同，我们继续比较pos[i+gap]和pos[j+gap]。这与比较(2 * gap)-gram的下一个间隙字符(即下半部分)相同。如果等级再次相同，则两个(2 * gap)-gram相同，因此返回0。否则，如果第i个后缀小于第j个后缀，则返回1。

例

以下示例说明了该算法的运行方式，并特别说明了词典名称在排序算法中的作用。

我们要排序的字符串是abcxabcd。为此需要三个迭代来生成后缀数组。在每次迭代中，我将显示S(字符串)，sa(后缀数组的当前状态)以及tmp和pos，它们代表词典名称。

首先，我们初始化:

S   abcxabcd
sa  01234567
pos abcxabcd

请注意，最初代表字母组合的字典顺序的词典名称如何与字符本身(即字母组合)完全相同。

第一次迭代:

使用bigrams作为排序标准，对sa进行排序:

sa  04156273

前两个后缀为0和4，因为它们是bigram'ab'的位置。然后是1和5(bigram'bc'的位置)，然后是6(bigram'cd')，然后是2(bigram'cx')。然后是7(不完整的双字母组'd')，然后是3(bigram'xa')。显然，位置仅基于字符二元组而与顺序相对应。

生成词典名称:

tmp 00112345

如上所述，字典名称被分配为递增的整数。前两个后缀(均以bigram'ab'开头)为0，接下来的两个后缀(均以bigram'bc'开头)均为1，然后为2、3、4、5(每个都是不同的bigram)。

最后，我们根据sa中的位置将其映射为pos:

sa  04156273
tmp 00112345
pos 01350124

(生成pos的方法是这样的:从左到右浏览sa，并使用该条目在pos中定义索引。使用tmp中的相应条目来定义该索引的值。因此pos[0]:=0，pos[4]:=0，pos[1]:=1，pos[5]:=1 ，pos[6]:=2等。索引来自sa，值来自tmp。)

第二次迭代:

我们再次对sa进行排序，然后再次查看pos中的二元组(每个二元组代表原始字符串的两个二元组的序列)。

sa  04516273

请注意，与先前版本的sa相比，1 5的位置是如何切换的。它以前是15，现在是51。这是因为在上一次迭代期间，pos[1]的bigram和pos[5]的bigram过去是相同的(两者都是bc)，但是现在pos[5]的bigram是12，而bigram则是pos[1]是13。因此，位置5在位置1之前。这是由于以下事实:词典名称现在每个都代表原始字符串的双字母:pos[5]代表bc，而pos[6]代表“cd”。因此，它们一起表示bcd，而pos[1]表示bc，而pos[2]表示cx，因此它们一起表示bcx，在字典上确实比bcd大。

同样，我们通过从左到右筛选当前版本的sa并比较pos中相应的双字母组来生成词典名称:

tmp 00123456

前两个条目仍然相同(均为0)，因为pos中的相应二元组都是01。其余部分是严格增加的整数序列，因为pos中的所有其他双字母组都是唯一的。

我们像以前一样执行到新pos的映射(从sa获取索引，从tmp获取值):

sa  04516273
tmp 00123456
pos 02460135

第三次迭代:

我们再次对sa进行排序，并使用pos的二元组(一如既往)，现在每个04代表原始字符串的4个二元组的序列。

sa  40516273

您会注意到，现在前两个条目已切换位置:40已变为pos[0]。这是因为02的bigram是pos[4]，而01的bigram是abcx，后者在字典上明显更小。深层原因是这两个分别代表abcd和7。

生成词典名称会产生:

tmp 01234567

它们都是不同的，即最高的是n-1，即sort。如此，我们完成了，因为排序现在基于所有不同的m-gram。即使我们继续，排序顺序也不会改变。

改善建议

用于在每次迭代中对2i-gram进行排序的算法似乎是内置的std::sort(或S=abcde)。这意味着它是一种比较排序，在最坏的情况下，每次迭代都需要O(n log n)时间。由于在最坏的情况下存在log n次迭代，因此这使其成为O(n(log n)2)时间算法。但是，可以使用两次遍历的存储桶排序来执行排序，因为我们用于排序比较的键(即上一步的词典名称)形成了一个递增的整数序列。因此，可以将其改进为用于后缀排序的实际O(n log n)时间算法。

备注

我相信这是Manber和Myers在1992年的论文中提出的用于后缀数组构造的原始算法(link on Google Scholar；它应该是第一个命中，并且那里可能有PDF的链接)。这(同时，但独立于Gonnet和Baeza-Yates的论文)才引入了后缀数组(在当时也称为pat数组)作为一种值得进一步研究的数据结构。

用于后缀数组构造的现代算法为O(n)，因此上述方法不再是可用的最佳算法(至少从理论上讲，不是最坏情况下的复杂性)。

脚注

(*) 2克表示原始字符串的两个连续字符序列。例如，当ab是字符串时，那么bc，cd，de和S是abcd的2克。同样，bcde和m是4克。通常，m-gram(对于正整数m)是S连续字符的序列。 1-gram也称为unigram，2-gram称为bigrams，3-gram称为trigram。有些人会继续使用四卦，五芒星等。

请注意，开始并定位i的S后缀是S的(n-i)-gram。同样，每个m-gram(对于任何m-gram)都是ojit_code后缀之一的前缀。因此，对m-gram进行排序(对于一个尽可能大的m)可以是对后缀进行排序的第一步。