总览

这是用于后缀数组构造的O（n log n）算法（或者，如果使用的不是::sort2遍存储桶排序，则为O（n log n）算法）。

它的工作方式是先对原始字符串的2克（*）排序，然后对4克，然后对8克S排序，依此类推，因此在第i次迭代中，我们对2个i克进行排序。有可明显不超过日志2（n）的这样的迭代，并且诀窍是，排序2
我 -grams中的第i个步骤是通过确保两个2每次比较容易我 -grams是为O完成（1）时间（而不是O（2 i）时间）。

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

词典重命名示例： 假设我们有一些双字母组的 排序
列表{'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都有两个步骤：

1. 按2个i- gram 排序，使用上一次迭代的词典名称，以使每个步骤分2个步骤（即O（1）时间）进行比较

2. 创建新的词典名称

我们重复此过程，直到所有2个i-
gram都不同为止。如果发生这种情况，我们就完成了。我们怎么知道是否都不同？好吧，字典名称是从0开始的整数递增序列。因此，如果在一次迭代中生成的最高字典名称与相同n-1，则每个2
i- 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;
}

这将在开始时比较（2
*间隙）-gram第i个后缀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意味着如果条件为true则返回1，如果条件为false则返回0。）

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

显然，这种简单的实现是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]必须以词汇表上小于开头的gap-gram的gap-
gram开头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

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

第一次迭代：

排序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

请注意，与的先前版本相比，1 5的位置是如何切换的sa。它以前是15，现在是51。这是因为在上一次迭代期间，bigram at
pos[1]和bigram at pos[5]以前是相同的（两者bc），但是现在bigram at pos[5]是12，而bigram
at 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（与往常一样）的二元组，每个二元组代表原始字符串的4个二元组的序列。

sa  40516273

您会注意到，现在前两个条目已切换位置：04已变为40。这是因为在二元pos[0]的02，而在一个pos[4]是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）2）次算法。但是，可以使用两次遍历的存储桶排序来执行排序，因为我们用于排序比较的键（即上一步的词典名称）形成了一个递增的整数序列。因此，可以将其改进为用于后缀排序的实际O（n
log n）时间算法。

备注

我相信这是Manber和Myers在1992年的论文中提出的用于后缀数组构造的原始算法（Google
Scholar上的链接；它应该是第一击，并且可能在其中带有PDF链接）。这（同时，但独立于Gonnet和Baeza-
Yates的论文）正是引入了后缀数组（当时也称为pat数组）作为数据结构而值得进一步研究的原因。

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

脚注

（*） 通过 2-克 我的意思是两个序列 连续
原始字符串的字符。例如，当S=abcde是字符串，然后ab，bc，cd，de是2-克S。同样，abcd和bcde是4克。通常，m-gram（对于正整数m）是一系列m连续字符。1-gram也称为unigram，2-gram称为bigrams，3-gram称为trigram。有些人会继续使用四卦，五芒星等。

请注意，S开头和位置的后缀i是的（ni）-gram S。同样，每个m-gram（对于任何m-gram）都是的后缀之一的前缀S。因此，对m-
gram进行排序（对于一个尽可能大的m）可以是对后缀进行排序的第一步。