排名列表的后缀

Question

x对数组/列表中的元素进行排序只是为了找出数组/列表中严格小于x的元素数量.

因此,对列表进行排名只是获取列表中所有元素的排名.

例如,rank [51, 38, 29, 51, 63, 38] = [3, 1, 0, 3, 5, 1]即有3个小于51的元素,等等.

可以在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].

---

编辑2

让我解释一下所有后缀是什么,这意味着在这里更清楚地排序/排序所有后缀.

假设我们有一个数组/列表[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]

顺便说一下,如果你不能想象如何在它们之间排序5个列表/数组,只需考虑按字典顺序排序字符串.

"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]

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(n log n)使用合并排序,堆排序或类似算法对比进行排序.所以问题仍然存在,我们如何快速比较两个后缀？

假设我们要比较后缀[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个这样的子串,但是如果需要,我们通过用负无穷大填充为每个位置分配一个.这里的诀窍是我们可以使用上面的分治理念和步骤1中分配的等级进行快速比较(这不是真正必要但后来会变得很重要).

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步骤.或者换句话说,我们需要log_2 n步骤来处理一系列大小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)作为z = n * x + y基数n中的数字.我们现在可以看到如何使用LSD基数排序来对这些对进行排序.在实践中,这意味着我们通过增加y使用计数排序来对对进行排序,然后再次使用计数排序来进行排序x.由于计数排序是稳定的,这给了我们对的字典顺序2 * O(n) = O(n).因此最终的复杂性O(n log n).

如果您有兴趣,可以在我的Github回购中找到O(n log² n)该方法的实现.该实现有27行代码.整洁,不是吗？