对列表后缀进行排名

Question

在一个数组/列表中，排名一个元素x就是找出在这个数组/列表中比x小的元素总数。

因此，对一个列表进行排名就是获得列表中所有元素的排名。

例如，排名[51, 38, 29, 51, 63, 38] = [3, 1, 0, 3, 5, 1]，即51有3个比它小的元素，等等。

对列表进行排名可以在O(NlogN)的时间内完成。基本上，我们可以对列表进行排序，同时记下每个元素的原始索引，然后看看每个元素之前有多少个元素。

问题在于如何以O(NlogN)的时间对列表的后缀进行排名？

排列一个列表的后缀意味着：

对于列表[3；1；2]，排名[[3；1；2]；[1；2]；[2]]

请注意，元素可能不是唯一的。

我们不需要为所有后缀打印出所有元素。你可以想象我们只需要打印出一个列表/数组，其中每个元素都是一个后缀的排名。

例如，rank suffix_of_[3;1;2] = rank [[3;1;2]; [1;2]; [2]] = [2;0;1]，你只需要打印出[2;0;1]。

让我更清楚地解释一下什么是“所有后缀”以及什么意思是“对所有后缀进行排序/排名”。

假设我们有一个数组/列表[e1;e2;e3;e4;e5]。

那么[e1;e2;e3;e4;e5]的所有后缀是：

[e1;e2;e3;e4;e5]
[e2;e3;e4;e5]
[e3;e4;e5]
[e4;e5]
[e5]

例如，[4;2;3;1;0]的所有后缀是

[4;2;3;1;0]
[2;3;1;0]
[3;1;0]
[1;0]
[0]

对以上5个后缀进行排序意味着按字典顺序排序。对所有这些后缀进行排序，您将得到

[0]
[1;0]
[2;3;1;0]
[3;1;0]
[4;2;3;1;0]

顺便提一下，如果你无法想象五个列表/数组如何在它们之间排序，可以考虑按词典顺序排序字符串。

"0" < "10" < "2310" < "310" < "42310"

---

似乎对所有后缀进行排序实际上是对原始数组的所有元素进行排序。

但是，请注意所有元素可能不是唯一的，例如

对于 [4;2;2;1;0]，所有后缀为：

[4;2;2;1;0]
[2;2;1;0]
[2;1;0]
[1;0]
[0]

然后按以下顺序排列：

[0]
[1;0]
[2;1;0]
[2;2;1;0]
[4;2;2;1;0]

- Jackson Tale

---

如果您已经将列表排序，那么其后缀也排序好了吧？ - Dima Chubarov

@ZiyaoWei 是的，我确定这是可能的。http://itu.dk/courses/SGDS/F2012/fastsufsort.pdf。只是我不能完全理解它。 - Jackson Tale

此外，您发布的链接是解决完全不同的问题，即对数组所有后缀进行词典排序。这与您发布的问题不同。 - templatetypedef

对于排序一个数组和获取每个元素的排名来说，它们不就是同一件事吗？ - Jackson Tale

啊，我明白你的意思了。你所描述的问题正是你链接的那个问题。 - templatetypedef

Answer 1

作为MBo正确指出的，你的问题是构建输入列表的后缀数组。实现这个的快速而复杂的算法实际上是线性时间，但由于您只针对O(n log n)，我将尝试提出一个更简单的版本，该版本更容易实现。

基本思想和初始O(n log² n)实现

让我们以序列[4, 2, 2, 1]为例。它的后缀是

0: 4 2 2 1
1: 2 2 1
2: 2 1
3: 1

我将原序列的后缀编号为其起始索引。最终我们希望以字典顺序快速排序这组后缀。我们知道可以使用归并排序、堆排序或类似算法，在O(nlogn)次比较中以常数空间表示每个后缀，进行排序。因此问题仍然是，如何快速比较两个后缀？

假设我们要比较后缀[2, 2, 1]和[2, 1]。我们可以用负无穷值填充它们，从而改变比较的结果：[2, 2, 1, -∞]和[2, 1, -∞, -∞]。

现在关键的想法是以下的分治观察：不必逐个字符比较序列直到找到不同的位置，而是将两个列表分成两半，并按字典顺序比较。

     [a, b, c, d]     < [e, f, g, h] 
 <=> ([a, b], [c, d]) < ([e, f], [g, h])
 <=> [a, b] < [e, f] or ([a, b,] = [e, f] and [c, d] < [g, h])

基本上，我们将比较序列的问题分解为比较较小序列的两个问题。这导致以下算法： 步骤1：对长度为1的子字符串（连续子序列）进行排序。在我们的示例中，长度为1的子字符串是[4]，[2]，[2]，[1]。每个子字符串可以用原始列表中的起始位置表示。我们通过简单的比较排序对它们进行排序，得到[1]，[2]，[2]，[4]。我们通过将每个位置分配给它在已排序的列表中的排名来存储结果：

position   substring   rank
0          [4]         2
1          [2]         1
2          [2]         1
3          [1]         0

重要的是我们给相等的子字符串分配相同的等级！

步骤2：现在我们想要对长度为2的子字符串进行排序。实际上只有3个这样的子字符串，但如果需要，我们可以通过填充负无穷来为每个位置分配一个子字符串。这里的技巧是我们可以利用上面提到的分治思想和第一步中分配的等级来进行快速比较（虽然现在并不是必须的，但以后会变得很重要）。

position  substring    halves        ranks from step 1   final rank
0         [4,  2]      ([4], [2])    (2,  1)             3               
1         [2,  2]      ([2], [2])    (1,  1)             2
2         [2,  1]      ([2], [2])    (1,  0)             1
3         [1, -∞]      ([1], [-∞])   (0, -∞)             0

步骤3：你猜对了，现在我们要排序长度为4的子字符串（！）。这些恰好是列表的后缀！这一次我们可以使用分而治之的技巧和步骤2的结果：

position  substring         halves              ranks from step 2   final rank
0         [4,  2,  2,  1]   ([4, 2], [2,  1])   (3,  1)             3
1         [2,  2,  1, -∞]   ([2, 2], [1, -∞])   (2,  0)             2
2         [2,  1, -∞, -∞]   ([2, 1], [-∞,-∞])   (1, -∞)             1
3         [1, -∞, -∞, -∞]   ([1,-∞], [-∞,-∞])   (0, -∞)             0

我们完成了！如果初始序列的大小为2^k，我们需要k步。或者反过来说，处理大小为n的序列需要log_2 n步。如果其长度不是2的幂，则只需用负无穷填充。

对于实际的实现，我们只需要记住算法每一步的序列“最终排名”。

C++中的实现可能如下（使用-std=c++11编译）：

#include <algorithm>
#include <iostream>
using namespace std;

int seq[] = {8, 3, 2, 4, 2, 2, 1};
const int n = 7;
const int log2n = 3;       // log2n = ceil(log_2(n))
int Rank[log2n + 1][n];    // Rank[i] will save the final Ranks of step i
tuple<int, int, int> L[n]; // L is a list of tuples. in step i,
                           // this will hold pairs of Ranks from step i - 1
                           // along with the substring index
const int neginf = -1;     // should be smaller than all the numbers in seq
int main() {
  for (int i = 0; i < n; ++i)
    Rank[1][i] = seq[i]; // step 1 is actually simple if you think about it
  for (int step = 2; step <= log2n; ++step) {
    int length = 1 << (step - 1); // length is 2^(step - 1)
    for (int i = 0; i < n; ++i)
      L[i] = make_tuple(
                Rank[step - 1][i],
                (i + length / 2 < n) ? Rank[step - 1][i + length / 2] : neginf,
                i); // we need to know where the tuple came from later
    sort(L, L + n); // lexicographical sort
    for (int i = 0; i < n; ++i) {
      // we save the rank of the index, but we need to be careful to
      // assign equal ranks to equal pairs
      Rank[step][get<2>(L[i])] = (i > 0 && get<0>(L[i]) == get<0>(L[i - 1])
                                        && get<1>(L[i]) == get<1>(L[i - 1]))
                                    ? Rank[step][get<2>(L[i - 1])] 
                                    : i;
    }
  }
  // the suffix array is in L after the last step
  for (int i = 0; i < n; ++i) {
    int start = get<2>(L[i]);
    cout << start << ":";
    for (int j = start; j < n; ++j)
      cout << " " << seq[j];
    cout << endl;
  }
}

输出：

6: 1
5: 2 1
4: 2 2 1
2: 2 4 2 2 1
1: 3 2 4 2 2 1
3: 4 2 2 1
0: 8 3 2 4 2 2 1

复杂度为O(log n * (n + sort))，在此实现中为O(n log² n)，因为我们使用的是比较排序，其复杂度为O(n log n)。

一个简单的O(n log n)算法

如果我们每步都能以O(n)的时间完成排序，那么我们就可以得到O(n log n)的上界。因此，基本上我们需要对一系列配对的(x, y)进行排序，其中0 <= x, y < n。我们知道可以使用计数排序在给定范围内以O(n)的时间对整数序列进行排序。我们可以将我们的配对(x, y)解释为以n为基数的数字z = n * x + y。现在我们可以看到如何使用LSD基数排序来对这些配对进行排序。 实际上，这意味着我们通过使用计数排序按递增顺序对y进行排序，然后再次使用计数排序按递增顺序对x进行排序。由于计数排序是稳定的，所以这给出了我们的配对的字典序顺序，复杂度为2 * O(n) = O(n)。因此，最终的复杂度为O(n log n)。

如果你有兴趣，可以在我的Github仓库中找到一种O(n log² n)的实现方法。这个实现只有27行代码。很整洁，不是吗？

- Niklas B.

---

不错，这正是我追寻的。我们可以将两个列表分成两半并按字典顺序比较这些部分，而不是逐个字符地比较序列，直到找到两个不同的位置。实际上，我可以在《函数算法设计珠玑》一书中找到这个问题的答案，但我就是无法理解它。现在通过你的回答，我明白了，并且那本书中的算法只是另一种描述方式。如果您有时间，能否请您描述一下O(n)算法？无论如何，我都会将您的答案标记为正确。 - Jackson Tale

@JacksonTale：嗯，我的意思是对列表进行排序是问题的下限，所以除非列表数字（字符串术语中的“字母表”）有特殊限制，否则整数排序是下限 :) 假设字母表大小恒定，我可以尝试解释桑德斯等人的构造算法，这是我认为最简单的。稍后我会尝试写点东西。 - Niklas B.

我们能否使用一轮计数排序来对(x,y)进行排序，即对z = n * x + y进行排序，而不是使用两轮计数排序（LSD基数排序）？ - Jackson Tale

@JacksonTale 是的，但我们会得到“n ^ 2”运行时间，因为z可以达到n *（n-1）的大小。 - Niklas B.

@Jacksontale，我们可以在不构建后缀树的情况下在线性时间内获得SA。这将是时间和空间的巨大浪费。 - Niklas B.

Answer 2

这正是后缀数组构建问题，维基页面包含线性复杂度算法的链接（可能取决于字母表）。

- MBo