后缀数组构造 O(N LogN) - 竞争性编程 3 Steven Halim
Suffix Array Construction O(N LogN) - Competitive Programming 3 Steven Halim
我正在阅读 Steven Halim 和 Felix Halim 合着的《Competitive Programming 3》一书
我正在阅读有关 Strings.I 的章节，试图了解后缀数组构造算法。我不明白基数排序部分。 （虽然，我明白基数排序和计数排序是如何工作的）
这是书中的代码
#define MAX_N 100010 // second approach: O(n log n)
char T[MAX_N]; // the input string, up to 100K characters
int n; // the length of input string
int RA[MAX_N], tempRA[MAX_N]; // rank array and temporary rank array
int SA[MAX_N], tempSA[MAX_N]; // suffix array and temporary suffix array
int c[MAX_N]; // for counting/radix sort
void countingSort(int k) { // O(n)
int i, sum, maxi = max(300, n); // up to 255 ASCII chars or length of n
memset(c, 0, sizeof c); // clear frequency table
for (i = 0; i < n; i++){ // count the frequency of each integer rank
c[i + k < n ? RA[i + k] : 0]++;
}
for (i = sum = 0; i < maxi; i++) {
int t = c[i]; c[i] = sum; sum += t;
}
for (i = 0; i < n; i++){ // shuffle the suffix array if necessary
tempSA[c[SA[i]+k < n ? RA[SA[i]+k] : 0]++] = SA[i];
}
for (i = 0; i < n; i++){ // update the suffix array SA
SA[i] = tempSA[i];
}
}
void constructSA() { // this version can go up to 100000 characters
int i, k, r;
for (i = 0; i < n; i++) RA[i] = T[i]; // initial rankings
for (i = 0; i < n; i++) SA[i] = i; //initial SA: {0, 1, 2, ..., n-1}
for (k = 1; k < n; k <<= 1) { // repeat sorting process log n times
countingSort(k); //actually radix sort:sort based on the second item
countingSort(0); // then (stable) sort based on the first item
tempRA[SA[0]] = r = 0; // re-ranking; start from rank r = 0
// compare adjacent suffixes
for (i = 1; i < n; i++){
// if same pair => same rank r; otherwise,increase r
tempRA[SA[i]] = (RA[SA[i]] == RA[SA[i-1]] && RA[SA[i]+k] == RA[SA[i-1]+k]) ? r : ++r;
}
for (i = 0; i < n; i++){// update the rank array RA
RA[i] = tempRA[i];
}
if (RA[SA[n-1]] == n-1) break; // nice optimization trick
}
}
有人可以解释一下 countingSort() 函数的这些行中发生了什么吗？
for (i = sum = 0; i < maxi; i++) {
int t = c[i]; c[i] = sum; sum += t;
}
for (i = 0; i < n; i++){ // shuffle the suffix array if necessary
tempSA[c[SA[i]+k < n ? RA[SA[i]+k] : 0]++] = SA[i];
}
for (i = 0; i < n; i++){ // update the suffix array SA
SA[i] = tempSA[i];
}
非常感谢您抽出宝贵时间。
首先计算每个唯一排名的 startIndex。
REMARK: c[]这里代表的是一个排名，而不是一个单独的角色。
// compute cumulates of rankings
for (i = sum = 0; i < maxi; i++) {
int t = c[i]; c[i] = sum; sum += t;
}
使用刚刚计算的 startIndices 对 Suffix 数组重新排序。基于SA[i]+k后缀的排名。
// shuffle the suffix array if necessary
for (i = 0; i < n; i++){
tempSA[c[SA[i]+k < n ? RA[SA[i]+k] : 0]++] = SA[i];
}
从临时数组中复制更新后的值
// copy the updated values back to SA
for (i = 0; i < n; i++){
SA[i] = tempSA[i];
}
这意味着从位置 i 开始的后缀按位置 (i+k).
的后缀排名排序
我们根据 i+k 处长度 k 的后缀对每个长度 k 的后缀进行排序。我们可以这样做，因为在之前的迭代中，所有后缀都按长度 k.
排序
之后我们再次从第一个索引开始排序。它保持着尺寸 k 的排名。自 sorting is stable 以来，所有后缀现在都按长度 k*2.
排序
如果排名中的两个连续后缀数组不再相等，我们的下一步是更新排名。
for (i = 1; i < n; i++){
// if same pair => same rank r; otherwise,increase r
tempRA[SA[i]] = (RA[SA[i]] == RA[SA[i-1]] && RA[SA[i]+k] == RA[SA[i-1]+k]) ? r : ++r;
}
如果尺码 k 在他们 startIndex 的排名相同并且在他们 startIndex+k 的排名相同。那么 startIndex 的排名与尺寸 k*2 相同。
这还应该解释以下内容：
if (RA[SA[n-1]] == n-1) break; // nice optimization trick
这意味着此时当前尺码的排名都是唯一的。所以所有后缀也是唯一的，不需要进一步排序。
步进示例：
a b c x a b c d
--------------------------------INIT-
0 1 2 3 4 5 6 7 // SA
97 98 99 120 97 98 99 100 // RA
---------------------------------K=1-
0 2 5 7 1 3 4 6 // SA
0 1 2 4 0 1 2 3 // RA
---------------------------------K=2-
1 3 5 7 0 2 4 6 // SA
1 3 5 7 0 2 4 6 // RA
步骤 K=1 的 countintSort 示例：
// count frequencies
c['a']=2;
c['b']=2;
c['c']=2;
c['d']=1;
c['x']=1;
// switch them to startindices
c['a']=0;
c['b']=2;
c['c']=4;
c['d']=6; // e.g. in total there are 6 suffixes smaller than starting with d (2 x a, 2 x b, 2 x c)
c['x']=7;
// determine the new SA position
tempSA[c[rank(SA[i]+k)]++] = SA[i];
// decomposing first iteration
tempSA[c[rank(SA[0]+k)]++] = SA[0]; // i = 0
tempSA[c[rank(SA[0]+1)]++] = SA[0]; // k = 1
tempSA[c[rank(1)]++] = 0; // SA[0] = 0
tempSA[c['b']++] = 0; // rank(1) = 'B'
tempSA[2] = 0; // c['b']=2 => 2++ = 3
换句话说：将当前第一个后缀数组放在后面开始k位的suffixArray的startIndex处。并将 startIndex 增加一个，以便下一次出现不会覆盖。
// all other iterations resulting in:
tempSA[0] = 7 // d (sorted by EMPTY)
tempSA[1] = 3 // x (sorted by a)
tempSA[2] = 0 // a (sorted by b)
tempSA[3] = 4 // a (sorted by b)
tempSA[4] = 1 // b (sorted by c)
tempSA[5] = 5 // b (sorted by c)
tempSA[6] = 6 // c (sorted by d)
tempSA[7] = 2 // c (sorted by d)
// last step is simply copying those values to SA (I suppose you know why this is)
这就是我能给你的全部，如果你仍然有问题，请尝试使用调试器检查它或打印出你有疑问的子结果。
我正在阅读 Steven Halim 和 Felix Halim 合着的《Competitive Programming 3》一书
我正在阅读有关 Strings.I 的章节，试图了解后缀数组构造算法。我不明白基数排序部分。 （虽然，我明白基数排序和计数排序是如何工作的）
这是书中的代码
#define MAX_N 100010 // second approach: O(n log n)
char T[MAX_N]; // the input string, up to 100K characters
int n; // the length of input string
int RA[MAX_N], tempRA[MAX_N]; // rank array and temporary rank array
int SA[MAX_N], tempSA[MAX_N]; // suffix array and temporary suffix array
int c[MAX_N]; // for counting/radix sort
void countingSort(int k) { // O(n)
int i, sum, maxi = max(300, n); // up to 255 ASCII chars or length of n
memset(c, 0, sizeof c); // clear frequency table
for (i = 0; i < n; i++){ // count the frequency of each integer rank
c[i + k < n ? RA[i + k] : 0]++;
}
for (i = sum = 0; i < maxi; i++) {
int t = c[i]; c[i] = sum; sum += t;
}
for (i = 0; i < n; i++){ // shuffle the suffix array if necessary
tempSA[c[SA[i]+k < n ? RA[SA[i]+k] : 0]++] = SA[i];
}
for (i = 0; i < n; i++){ // update the suffix array SA
SA[i] = tempSA[i];
}
}
void constructSA() { // this version can go up to 100000 characters
int i, k, r;
for (i = 0; i < n; i++) RA[i] = T[i]; // initial rankings
for (i = 0; i < n; i++) SA[i] = i; //initial SA: {0, 1, 2, ..., n-1}
for (k = 1; k < n; k <<= 1) { // repeat sorting process log n times
countingSort(k); //actually radix sort:sort based on the second item
countingSort(0); // then (stable) sort based on the first item
tempRA[SA[0]] = r = 0; // re-ranking; start from rank r = 0
// compare adjacent suffixes
for (i = 1; i < n; i++){
// if same pair => same rank r; otherwise,increase r
tempRA[SA[i]] = (RA[SA[i]] == RA[SA[i-1]] && RA[SA[i]+k] == RA[SA[i-1]+k]) ? r : ++r;
}
for (i = 0; i < n; i++){// update the rank array RA
RA[i] = tempRA[i];
}
if (RA[SA[n-1]] == n-1) break; // nice optimization trick
}
}
有人可以解释一下 countingSort() 函数的这些行中发生了什么吗？
for (i = sum = 0; i < maxi; i++) {
int t = c[i]; c[i] = sum; sum += t;
}
for (i = 0; i < n; i++){ // shuffle the suffix array if necessary
tempSA[c[SA[i]+k < n ? RA[SA[i]+k] : 0]++] = SA[i];
}
for (i = 0; i < n; i++){ // update the suffix array SA
SA[i] = tempSA[i];
}
非常感谢您抽出宝贵时间。
首先计算每个唯一排名的 startIndex。
REMARK: c[]这里代表的是一个排名，而不是一个单独的角色。
// compute cumulates of rankings
for (i = sum = 0; i < maxi; i++) {
int t = c[i]; c[i] = sum; sum += t;
}
使用刚刚计算的 startIndices 对 Suffix 数组重新排序。基于SA[i]+k后缀的排名。
// shuffle the suffix array if necessary
for (i = 0; i < n; i++){
tempSA[c[SA[i]+k < n ? RA[SA[i]+k] : 0]++] = SA[i];
}
从临时数组中复制更新后的值
// copy the updated values back to SA
for (i = 0; i < n; i++){
SA[i] = tempSA[i];
}
这意味着从位置 i 开始的后缀按位置 (i+k).
我们根据 i+k 处长度 k 的后缀对每个长度 k 的后缀进行排序。我们可以这样做，因为在之前的迭代中，所有后缀都按长度 k.
之后我们再次从第一个索引开始排序。它保持着尺寸 k 的排名。自 sorting is stable 以来，所有后缀现在都按长度 k*2.
如果排名中的两个连续后缀数组不再相等，我们的下一步是更新排名。
for (i = 1; i < n; i++){
// if same pair => same rank r; otherwise,increase r
tempRA[SA[i]] = (RA[SA[i]] == RA[SA[i-1]] && RA[SA[i]+k] == RA[SA[i-1]+k]) ? r : ++r;
}
如果尺码 k 在他们 startIndex 的排名相同并且在他们 startIndex+k 的排名相同。那么 startIndex 的排名与尺寸 k*2 相同。
这还应该解释以下内容：
if (RA[SA[n-1]] == n-1) break; // nice optimization trick
这意味着此时当前尺码的排名都是唯一的。所以所有后缀也是唯一的，不需要进一步排序。
步进示例：
a b c x a b c d
--------------------------------INIT-
0 1 2 3 4 5 6 7 // SA
97 98 99 120 97 98 99 100 // RA
---------------------------------K=1-
0 2 5 7 1 3 4 6 // SA
0 1 2 4 0 1 2 3 // RA
---------------------------------K=2-
1 3 5 7 0 2 4 6 // SA
1 3 5 7 0 2 4 6 // RA
步骤 K=1 的 countintSort 示例：
// count frequencies
c['a']=2;
c['b']=2;
c['c']=2;
c['d']=1;
c['x']=1;
// switch them to startindices
c['a']=0;
c['b']=2;
c['c']=4;
c['d']=6; // e.g. in total there are 6 suffixes smaller than starting with d (2 x a, 2 x b, 2 x c)
c['x']=7;
// determine the new SA position
tempSA[c[rank(SA[i]+k)]++] = SA[i];
// decomposing first iteration
tempSA[c[rank(SA[0]+k)]++] = SA[0]; // i = 0
tempSA[c[rank(SA[0]+1)]++] = SA[0]; // k = 1
tempSA[c[rank(1)]++] = 0; // SA[0] = 0
tempSA[c['b']++] = 0; // rank(1) = 'B'
tempSA[2] = 0; // c['b']=2 => 2++ = 3
换句话说：将当前第一个后缀数组放在后面开始k位的suffixArray的startIndex处。并将 startIndex 增加一个，以便下一次出现不会覆盖。
// all other iterations resulting in:
tempSA[0] = 7 // d (sorted by EMPTY)
tempSA[1] = 3 // x (sorted by a)
tempSA[2] = 0 // a (sorted by b)
tempSA[3] = 4 // a (sorted by b)
tempSA[4] = 1 // b (sorted by c)
tempSA[5] = 5 // b (sorted by c)
tempSA[6] = 6 // c (sorted by d)
tempSA[7] = 2 // c (sorted by d)
// last step is simply copying those values to SA (I suppose you know why this is)
这就是我能给你的全部，如果你仍然有问题，请尝试使用调试器检查它或打印出你有疑问的子结果。