ICUとesaxxで極大部分文字列を求める
「全ての部分文字列を考慮した文書分類」って論文の真似事をしてみようと、まずは極大部分文字列の抽出をやってみた。
極大部分文字列の作り方を調べていると、esaxxっていうライブラリが便利らしいとの情報を発見。(極大部分文字列 - アスペ日記)
早速やってみたわけだけど、サンプルでは文字型がcharなので、日本語を扱うことができない。僕は日本人だから日本語使うんだ!ってことで、C++とJavaのUnicodeライブラリ「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 *
実行するとノード一覧が出力される。「*」が付いているのが極大部分文字列。「なぎ」は「うなぎ」の一部としてしか現れないから、極大部分文字列ではないと。なるほど。