后缀数组算法

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遍存储桶排序).

它的工作原理是首先对原始字符串的2克^(*),然后是4克,然后是8克等进行S排序,因此在第i次迭代中,我们对2个^i- gram进行排序.有可明显不超过登录₂(n)的这样的迭代,并且诀窍是,排序2 ^我在第i步-grams是通过确保两个2每次比较容易^我 -grams为O完成(1)时间(而不是O(2 ⁱ)时间).

它是如何做到的？好吧,在第一次迭代中,它对2-gram(又名bigrams)进行排序,然后执行所谓的字典重命名.这意味着它创建了一个新的数组(长度n),为每个二元组存储它在bigram排序中的排名.

字典重命名示例:假设我们有一些bigrams 的排序列表{'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次操作.但相反,我们使用前面步骤中生成的排名表,通过查找其中包含的两个bigrams的行列来比较它们.该等级代表前一个2克分类的词典排名,因此如果对于任何给定的4克,其第一个2克的排名高于另一个4克的前2克,那么它必须在字典上更大在前两个字符的某个地方.因此,如果对于两个4克,前2克的等级是相同的,则它们在前两个字符中必须相同.换句话说,等级表中的两个查找足以比较两个4克的所有4个字符.

排序后,我们再次创建新的词典名称,这次是4克.

在第三次迭代中,我们需要按8克排序.同样,在前一步骤的词典排名表中的两次查找足以比较两个给定8克的所有8个字符.

等等.每次迭代i都有两个步骤:

1. 使用上一次迭代中的字典名称对2个^i- gram进行排序,以便在2个步骤(即O(1)时间)内进行比较

2. 创建新的词典名称

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

履行

现在让我们看看代码来确认所有这些.使用的变量如下:sa[]是我们正在构建的后缀数组.pos[]是rank lookup-table(即它包含字典名称),具体来说,它包含上一步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*间隙) - 图表.所以在第一次迭代中它比较了双字母,在第二次迭代中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个后缀开头的(2*gap)-gram pos_i:=sa[i]与第j个后缀开头的结果pos_j:=sa[j].并且它将逐个字符地比较它们,即S[pos_i]与之比较S[pos_j],然后S[pos_i+1]与之比较S[pos_j+1]等.只要字符相同,它就会继续.一旦它们不同,如​​果第i个后缀中的字符小于第j个后缀中的字符,则返回1,否则返回0.(注意,return a<b在函数返回中,int如果条件为真,则返回1;如果为假,则返回0.)

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

显然,这种天真的实现是O(间隙),即其复杂度在(2*间隙) - 格的长度上是线性的.但是,代码中使用的函数使用词典名称将其降低到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个后缀的字典军衔.在前一次迭代中,对于gap-gram计算了词典排名.所以,如果pos[i] < pos[j],那么第i个后缀sa[i]必须以一个空格键开始,这个空格键在字典上小于开头处的gap-gram sa[j].换句话说,只需通过查找pos[i]并pos[j]和他们比较,我们比较了第一个缺口的两个后缀的字符.

如果等级相同,我们将继续通过比较pos[i+gap]同pos[j+gap].这与比较(2*间隙) - 格的下一个间隙字符(即下半部分)相同.如果排名再次是同一个,那么两个(2*gap)-grams是不同的,所以我们返回0.否则,如果第i个后缀小于第j个后缀,则返回1,否则返回0.

例

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

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

首先,我们初始化:

S   abcxabcd
sa  01234567
pos abcxabcd

请注意词典名称(最初代表unigrams的词典排名)与字符(即unigrams)本身完全相同.

第一次迭代:

排序sa,使用bigrams作为排序标准:

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(每个都是一个不同的二元组).

最后,我们根据位置进行映射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再次排序,我们再次查看来自的bigrams pos(每个都表示原始字符串的两个 bigrams的序列).

sa  04516273

注意与之前版本相比,1 5的位置是如何切换的sa.它曾经是15,现在它是51.这是因为在上一次迭代中,二元组pos[1]和二元组在过去的迭代中pos[5]曾经是相同的(两者bc),但是现在的二元组pos[5]是12,而二元组pos[1]是13.所以位置5来之前的位置1.这是因为词典名称现在每个都代表原始字符串的bigrams:pos[5]代表bc并pos[6]代表'cd'.因此,它们共同代表bcd,pos[1]代表bc和pos[2]代表cx,它们代表在一起bcx,这确实是词典上的大于bcd.

同样,我们通过sa从左到右筛选当前版本并比较以下对应的双子座来生成词典名称pos:

tmp 00123456

前两个条目仍然相同(均为0),因为相应的双字母组合pos都是01.其余的是一个严格增加的整数序列,因为所有其他的bigrams pos都是唯一的.

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

sa  04516273
tmp 00123456
pos 02460135

第三次迭代:

我们sa再次排序,采用pos(一如既往)的bigrams ,现在每个都代表原始字符串的4个bigrams的序列.

sa  40516273

你会注意到现在前两个条目已经转换了位置:04已成为40.这是因为在二元pos[0]的02,而一个在pos[4]IS 01,后者显然是字典序小.深层原因是这两个分别代表abcx和abcd.

生成字典名称会产生:

tmp 01234567

它们都是不同的,即最高的是7,即n-1.所以,我们已经完成了,因为排序现在基于m-gram,它们都是不同的.即使我们继续,排序顺序也不会改变.

改进建议

用于在每次迭代中对2个^i- gram 进行排序的算法似乎是内置sort(或std::sort).这意味着它是一种比较排序,在每次迭代中,在最坏的情况下需要O(n log n)时间.由于在最坏的情况下存在log n次迭代,因此这使得它成为O(n(log n)²)时间算法.然而,排序可以通过使用两次桶排序来执行,因为我们用于排序比较的键(即前一步骤的词典名称)形成递增的整数序列.因此,这可以改进为用于后缀排序的实际O(n log n)时间算法.

备注

我相信这是后缀阵列构造的原始算法,在1992年的文章中由Manber和Myers提出(链接在Google学术搜索 ;它应该是第一个,它可能有一个链接到那里的PDF).这(同时,但与Gonnet和Baeza-Yates的论文无关)是引入后缀数组(当时也称为pat数组)作为有待进一步研究的数据结构.

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

脚注

^(*)通过 2-克我的意思是两个序列连续原始字符串的字符.例如,当S=abcde是字符串,然后ab,bc,cd,de是2-克S.类似地,abcd和bcde是4克.通常,m-gram(对于正整数m)是m连续字符序列.1克也称为unigrams,2克称为bigrams,3克称为三卦.有些人继续使用四卦,五角星等.

注意,S开始和位置的后缀i是(ni)-gram S.此外,每个m-gram(对于任何m)都是其中一个后缀的前缀S.因此,对m-gram进行排序(对于尽可能大的m)可以是排序后缀的第一步.