2

私はスティーブン・ハリムとフェリックス・ハリムによる本「競争力のあるプログラミング3」を読んでいます

Strings の章を読んでいます。接尾辞配列の構築アルゴリズムを理解しようとしています。基数ソートの部分がわかりません。（ただし、基数ソートとカウントソートの仕組みは理解しています）

ここに本からのコードがあります

#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];
}

貴重な時間をありがとうございました。

4

1 に答える 1

4

最初に、一意のランキングごとに startIndex を計算します。

注意: 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];
}

これは、 position で始まるi接尾辞が place の接尾辞のランキングによってソートされることを意味し(i+k)ます。

length の各接尾辞を、 placekの長さの接尾辞でソートします。これができるのは、前の反復ですべての接尾辞が length でソートされていたからです。ki+kk

その後、最初のインデックスから再度ソートします。サイズのランキングを保持していたのはどれですかk。ソートは安定しているため、すべてのサフィックスが長さでソートされるようになりk*2ました。

次のステップは、ランキング内の 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が同じなら。でのランキングはstartIndexsize も同じです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

countintSort ステップ K=1 の例:

// 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 を 1 増やして、次の発生で上書きされないようにします。

// 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)

これが私があなたに提供できるすべてです。まだ問題がある場合は、デバッガーを使用して実行するか、疑わしい部分の結果を出力してみてください。

于 2015-12-21T19:47:08.077 に答える