ICUとesaxxで極大部分文字列を求める

全ての部分文字列を考慮した文書分類」って論文の真似事をしてみようと、まずは極大部分文字列の抽出をやってみた。
極大部分文字列の作り方を調べていると、esaxxっていうライブラリが便利らしいとの情報を発見。(極大部分文字列 - アスペ日記)

早速やってみたわけだけど、サンプルでは文字型がcharなので、日本語を扱うことができない。僕は日本人だから日本語使うんだ!ってことで、C++JavaUnicodeライブラリ「ICU」で文字分割。ICUの名前は聞いたことあるけど、使うのは初めて。普通に


./configure
make
make all

ってしたら使えるようになりました。
ICU(C++)を使って Unicode 正規化 - やた@はてな日記」とか「ICUを使う | Netsphere Laboratories」を参考に、文字分割。その後esaxxに突っ込んでみた。

#include <iostream>
#include <vector>
#include <string>

#include <unicode/unistr.h>
#include <unicode/uchar.h>
#include <unicode/schriter.h>

#include "esa.hxx"

using namespace std;

int main() {
  vector<UChar32> T;
  while(!cin.eof()) {
    string s;
    getline(cin, s);

    UnicodeString str(s.c_str(), "UTF-8");
    StringCharacterIterator it(str);
    for(UChar32 uc = it.first32(); uc != it.DONE; uc = it.next32()) {
      if(uc>' ') T.push_back(uc);
    }
  }
 
  int n = T.size();

  vector<int>  SA(n);     // suffix array
  vector<int>  L (n);     // left boundaries of internal node
  vector<int>  R (n);     // right boundaries of internal node 
  vector<int>  D (n);     // depths of internal node
  
  int alphaSize = 0x110000;  // This can be very large
 int nodeNum = 0;
 if (esaxx(T.begin(), SA.begin(),
	   L.begin(), R.begin(),  D.begin(),
	   n, alphaSize, nodeNum) == -1){
   return -1;
 }

 vector<int> rank(n);
 int r = 0;
 for(int i=0;i<n;i++) {
   if(i==0 || T[(SA[i]+n-1)%n] != T[(SA[i-1]+n-1)%n]) r++;
   rank[i] = r;
   }

 for (int i = 0; i < nodeNum; ++i){
   // the frequency of substrings corresponding to the internal node
   //   and the depth of the internal node
   cout << R[i] - L[i] << "\t"  << D[i] << "\t"; 
   int beg = SA[L[i]];
   int len = D[i];
   for (int j = 0; j < len; ++j){
     UnicodeString us(T[beg + j]);
     char buf[8];
     us.extract(0, us.length(), buf, sizeof(buf), "UTF-8");
     cout << buf;
   }
   if(rank[ R[i] - 1 ] - rank[ L[i] ]>0) {
     cout << "*";
   }
   cout << endl;
   }
 return 0;
}

ICUとのリンクが必要なのでコンパイル時にオプション追加。


$ g++ `icu-config --cppflags --ldflags` program.cpp


$ ./a.out
うなぎうなうなうなぎ
^D
2 4 うなうな*
2 3 うなぎ*
4 2 うな*
2 5 ぎうなうな*
3 3 ぎうな*
2 2 なぎ
6 1 ぎ*
10 0 *

実行するとノード一覧が出力される。「*」が付いているのが極大部分文字列。「なぎ」は「うなぎ」の一部としてしか現れないから、極大部分文字列ではないと。なるほど。