カサイのアルゴリズムとは？接尾辞配列からLCP配列を効率的に求める方法

カサイ（Kasai）のアルゴリズムは、接尾辞配列（サフィックスアレイ）から最長共通接頭辞（LCP：Longest Common Prefix）配列を求めるために用いられるアルゴリズムです。処理の流れとしては、まず対象の文字列から接尾辞配列を構築し、その後、その接尾辞配列を入力としてLCP配列を計算します。

そもそも接尾辞配列とは、文字列のすべての接尾辞を辞書順に並べ替えたときの開始位置（インデックス）の一覧です。また、LCP配列は隣接する接尾辞同士が共有する最長接頭辞の長さを記録したものであり、高速な文字列検索やデータ圧縮、バイオインフォマティクスなど幅広い分野で活用されています。

計算量については、接尾辞配列の構築には O(m log n) の時間がかかります。ここで m はパターンの長さ、n はテキストの長さを表します。一方、カサイのアルゴリズム自体は、主文字列に対する処理を線形時間 O(n) で完了できる点が大きな特徴です。

入力と出力

入力:
主文字列: "banana"
出力:
接尾辞配列 :
5 3 1 0 4 2
共通接頭辞配列 :
1 3 0 0 2 0

アルゴリズム

buildSuffixArray(text)

入力: 主文字列

出力: 主テキストから構築された接尾辞配列

手順開始
    n := テキストのサイズ

    i := 0 から n まで繰り返す
        suffArray[i].index := i
        suffArray[i].rank[0] := text[i]
        もし (i+1) < n ならば
            suffArray[i].rank[1] := text[i+1]
        そうでなければ
            suffArray[i].rank[1] := -1
    繰り返し終了

    接尾辞配列をソートする
    インデックスを格納するための index 配列を定義する

    k := 4 から (2*n)-1 まで、k を毎回 2 倍しながら繰り返す
        currRank := 0
        prevRank := suffArray[0].rank[0]
        suffArray[0].rank[0] := currRank
        index[suffArray[0].index] := 0

        テキストのすべての文字位置 i について
            もし suffArray[i].rank[0] = prevRank かつ
               suffArray[i].rank[1] = suffArray[i-1].rank[1] ならば
                prevRank := suffArray[i].rank[0]
                suffArray[i].rank[0] := currRank
            そうでなければ
                prevRank := suffArray[i].rank[0]
                suffArray[i].rank[0] := currRank + 1
                currRank := currRank + 1
                index[suffArray[i].index] := i
        繰り返し終了

        テキストのすべての文字位置 i について
            nextIndex := suffArray[i].index + k/2
            もし nextIndex < n ならば
                suffArray[i].rank[1] := suffArray[index[nextIndex]].rank[0]
            そうでなければ
                suffArray[i].rank[1] := -1
        繰り返し終了
        suffArray をソートする
    繰り返し終了

    テキストのすべての文字位置 i について
        suffVector に suffArray[i].index を挿入する
    繰り返し終了
手順終了

kasaiAlgorithm(text, suffVector)

入力: 主テキストと、接尾辞のリストである接尾辞ベクトル

出力: 最長共通接頭辞が見つかる位置

手順開始
    n := suffVector のサイズ
    サイズ n の longPrefix リストを定義し、全要素を 0 で初期化する
    サイズ n の suffInverse リストを定義し、全要素を 0 で初期化する

    suffVector のすべてのインデックス i について
        suffInverse[suffVector[i]] := i
    繰り返し終了

    k := 0
    i := 0 から n-1 まで繰り返す
        もし suffInverse[i] = n-1 ならば
            k := 0
            以降の処理をスキップして次の反復へ進む
        j := suffVector[suffInverse[i]+1]

        (i+k) < n かつ (j+k) < n かつ text[i+k] = text[j+k] の間
            k を 1 増やす
        繰り返し終了
        longPrefix[suffInverse[i]] := k
        もし k > 0 ならば
            k を 1 減らす
    繰り返し終了
    longPrefix を返す
手順終了

このアルゴリズムのポイントは、隣接する接尾辞同士の共通接頭辞の長さには強い関連性があるという性質を利用している点です。前の接尾辞で得られた一致長 k をそのまま次の比較に再利用できるため、全体を線形時間で処理することが可能になっています。

C++による実装例

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

struct suffix {
   int index;
   int rank[2];    // ランクペアを格納する
};

bool compare(suffix s1, suffix s2) {    // sort関数用に接尾辞を比較する
   if(s1.rank[0] == s2.rank[0]) {
      if(s1.rank[1] < s2.rank[1])
         return true;
      else
         return false;
   }else {
      if(s1.rank[0] < s2.rank[0])
         return true;
      else
         return false;
   }
}

vector<int> buildSuffixArray(string mainString) {
   int n = mainString.size();
   suffix suffixArray[n];

   for (int i = 0; i < n; i++) {
      suffixArray[i].index = i;
      suffixArray[i].rank[0] = mainString[i] - 'a';     // 古いランクを保存
      suffixArray[i].rank[1] = ((i+1)<n)?(mainString[i+1]-'a'):-1; // 辞書順での次のランク
   }

   sort(suffixArray, suffixArray+n, compare);    // 先頭2文字まででソート
   int index[n];  // suffixArray 内のインデックス

   for (int k = 4; k < 2*n; k = k*2) {    // k を2のべき乗として増やす
      int currRank = 0;
      int prevRank = suffixArray[0].rank[0];
      suffixArray[0].rank[0] = currRank;
      index[suffixArray[0].index] = 0;

      for (int i = 1; i < n; i++) {    // すべての接尾辞にランクを割り当てる
         if (suffixArray[i].rank[0] == prevRank && suffixArray[i].rank[1] == suffixArray[i-1].rank[1]) {
            prevRank = suffixArray[i].rank[0];
            suffixArray[i].rank[0] = currRank;
         } else{    // ランクを増やして割り当てる
            prevRank = suffixArray[i].rank[0];
            suffixArray[i].rank[0] = ++currRank;
         }
         index[suffixArray[i].index] = i;
      }

      for (int i = 0; i < n; i++) {    // 各接尾辞に次のランクを割り当てる
         int nextIndex = suffixArray[i].index + k/2;
         suffixArray[i].rank[1] = (nextIndex < n)? suffixArray[index[nextIndex]].rank[0]: -1;
      }
      sort(suffixArray, suffixArray+n, compare); // 先頭 k 文字まででソート
   }

   vector<int>suffixVector;
   for (int i = 0; i < n; i++)
      suffixVector.push_back(suffixArray[i].index);    // 全接尾辞のインデックスをベクトルに格納
      return  suffixVector;
}

vector<int> kasaiAlgorithm(string mainString, vector<int> suffixVector) {
   int n = suffixVector.size();
   vector<int> longPrefix(n, 0);    // サイズ n・0で初期化
   vector<int> suffixInverse(n, 0);

   for (int i=0; i < n; i++)
      suffixInverse[suffixVector[i]] = i;    // 逆接尾辞リストの値を埋める
   int k = 0;
   for (int i=0; i<n; i++) {    // 主文字列のすべての接尾辞について
      if (suffixInverse[i] == n-1) {    // 位置 (n-1) の接尾辞の場合
         k = 0;
         continue;
      }

      int j = suffixVector[suffixInverse[i]+1];    // 接尾辞リストの次の文字列
      while (i+k<n && j+k<n && mainString[i+k]==mainString[j+k]) // k番目から比較開始
         k++;
      longPrefix[suffixInverse[i]] = k;    // 現在の接尾辞の接頭辞長
      if (k>0)
         k--;    // 先頭の1文字を除く
   }
   return longPrefix;
}

void showArray(vector<int> vec) {
   vector<int>::iterator it;

   for (it = vec.begin(); it < vec.end() ; it++)
      cout << *it << " ";
   cout << endl;
}

int main() {
   string mainString = "banana";
   vector<int>suffixArray = buildSuffixArray(mainString);
   int n = suffixArray.size();

   cout<< "Suffix Array : "<<endl;
   showArray(suffixArray);

   vector<int>commonPrefix = kasaiAlgorithm(mainString, suffixArray);

   cout<< "\nCommon Prefix Array : "<<endl;
   showArray(commonPrefix);
}

実行結果

Suffix Array :
5 3 1 0 4 2
Common Prefix Array :
1 3 0 0 2 0