お久しぶりです,木村です.

最近どうもやることが多くてエントリーを書けずにいました...これからはまたちょっとずつ書いていこうと思います.というかメモですね.

正規表現ライブラリRe2

つい先日Googleにより,正規表現ライブラリがリリースされたのは有名な話ですね.

Re2とは

米Googleは3月11日、正規表現ライブラリ「RE2」を発表した。動作が高速で「スレッドフレンドリー」な点が特徴。従来のバックトラック型正規表現ライブラリの代替として開発を進めていく。

http://sourceforge.jp/magazine/10/03/15/0331223より引用

だそうです.

僕もしばしば言語処理のプログラムを書くときは正規表現を使うので,これは良さそう!ってことでRe2を物色してみました.

Re2を使ってみた

使い方はPerlの正規表現っぽく使えて簡単です,後方参照とかもできます.

詳しくはヘッダーファイルを読んでいただくとして,ヘッダーファイルからパクってきた簡単な後方参照のサンプルを載せておきます.Re2がインストールされている環境で行ってください.

以下のサンプルコードをRe2test.cppという名前で保存します.


このコードを以下のようにコンパイルします

g++ -Wall -I/usr/local/include Re2test.cpp -lre2 -lpthread

超簡単ですね.他にも色々機能がありますのでぜひヘッダーファイルをご参照ください.

Re2のスピード

そこで,ベンチマークをとってみようかなあと思ったのですが,以下のエントリでid:tkuroさんがすでにベンチをとっておられました.結論「RE2はええ」だそうです.

Re2のメモリチェック

使い方もわかったので,そろそろvalgrindをかけたくなるというのが男の性.
そこで,先ほどのサンプルプログラムにvalgrindをかけて実行してみました.

valgrind ./a.out

ををを・・・?
めちゃくちゃメッセージがでてきましたね.

メッセージの要約

==13496== Conditional jump or move depends on uninitialised value(s)
==13496== at 0x8069B9A: re2::Prog::Optimize() (sparse_array.h:296)
==13496== by 0x8058635: re2::Compiler::Compile(re2::Regexp*, bool, long long) (compile.cc:920)
==13496== by 0x8058D26: re2::Regexp::CompileToProg(long long) (compile.cc:941)
==13496== by 0x804E6B2: re2::RE2::Init(re2::StringPiece const&, re2::RE2::Options const&) (re2.cc:170)
==13496== by 0x804F035: re2::RE2::RE2(char const*) (re2.cc:87)
==13496== by 0x8049AE1: main (in /home/kimura/Work/Re2/a.out)
==13496==
==13496== Use of uninitialised value of size 4
==13496== at 0x8069D9B: re2::Prog::Optimize() (sparse_array.h:296)
==13496== by 0x8058635: re2::Compiler::Compile(re2::Regexp*, bool, long long) (compile.cc:920)
==13496== by 0x8058D26: re2::Regexp::CompileToProg(long long) (compile.cc:941)
==13496== by 0x804E6B2: re2::RE2::Init(re2::StringPiece const&, re2::RE2::Options const&) (re2.cc:170)
==13496== by 0x804F035: re2::RE2::RE2(char const*) (re2.cc:87)
==13496== by 0x8049AE1: main (in /home/kimura/Work/Re2/a.out)

==13496== ERROR SUMMARY: 866 errors from 41 contexts (suppressed: 16 from 1)
==13496== malloc/free: in use at exit: 0 bytes in 0 blocks.
==13496== malloc/free: 265 allocs, 265 frees, 40,326 bytes allocated.
==13496== For counts of detected errors, rerun with: -v
==13496== Use --track-origins=yes to see where uninitialised values come from
==13496== All heap blocks were freed -- no leaks are possible.

以下の32bit環境?64bit環境でチェックしましたが,両方ともエラーが出ました.
* fedora core 11 32bit
* fedora core 11 64bit
* g++ (GCC) 4.4.1 20090725 (Red Hat 4.4.1-2)

エラーメッセージを追ってみるとどうやら,複数の個所でイニシャライズされていない領域を使用しているように見えました.深追いするとちょっと時間がかかりそうなので今回は深追いはやめました.どうやらエラーの中のひとつはdfa.ccの中にあるAddToQueue()という,おそらくジョブをキューに追加する関数の中で起こっているようですが,明確なことは言えないので調査が済んだらまたエントリーを書きたいと思います.

Re2にパッケージングされているテストを実行しても同じようにエラーが出たので,おそらくどこかに不具合があるのだと思いますが...もし僕のケアレスミスでしたらごめんなさい.

もうちょとRe2のソースをよく読んでみたいと思いますー.


プログラム保存用

#include 
#include 

using namespace re2;

int main(void) {

  int i = 0;
  std::string s = "";
  
  if(RE2::FullMatch("hello", "h.*o")) std::cout << "PASS" << std::endl;
  if(RE2::FullMatch("ruby:1234", "(\\w+):(\\d+)", &s, &i)) std::cout << "PASS" << std::endl;
  if(!RE2::FullMatch("ruby", "(.*)", &i)) std::cout << "PASS" << std::endl;
  if(!RE2::FullMatch("ruby:1234", "\\w+:\\d+", &s)) std::cout << "PASS" << std::endl;
  if(RE2::FullMatch("ruby:1234", "(\\w+):(\\d+)", &s)) std::cout << "PASS" << std::endl;
  
  return 0;
}

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です