読者です 読者をやめる 読者になる 読者になる

naoya_t@hatenablog

いわゆるチラシノウラであります

高速かつ省メモリなGoogleの正規表現ライブラリ re2 についてのメモ

高速かつ省メモリなGoogle正規表現ライブラリ re2 についてのメモ。

RE2は、PCRE や PerlPython で使われているようなバックトラッキング正規表現エンジンの代替となる、高速で、安全で、スレッド・フレンドリーなC++ライブラリです。


バックトラッキング・エンジンは一般に機能や便利なシンタックスシュガーが満載ですが、小さな入力に対してさえも指数関数的に時間がかかる羽目に陥ることがあります。RE2はオートマトン理論を用い、正規表現検索が入力のサイズに対し線形の時間内に走ることを保証しています。
検索を固定量のメモリに制約できるように、RE2はメモリ制限を実装しています。
どのような入力もしくは正規表現を処理しなくてはならないとしても、小さな固定のC++スタック量のみ使用するようRE2は設計されています。そのため、RE2はスレッドスタックを任意に拡げられないマルチスレッド環境で便利です。


大きな入力に対し、RE2はよくバックトラッキング型エンジンより高速になります。オートマトン理論を用いることで、他のエンジンが成し得ない最適化を行います。


他のオートマトンベースのエンジンとは異なり、RE2はPerlやPCREの一般的な機能やシンタックスシュガーのほぼ全てを実装しています。 最左優先一致や、Perl と同様のマッチングを行ったり、部分一致情報を返すこともできます。
特筆すべき例外の一つは、RE2が後方参照と汎用ゼロ幅アサーションのサポートを行わないことです。これらは効率的に実装することができないためです。詳しくは 文法のページ をご覧ください。


RE2 にはもっと単純な文法を望む人たちのために、POSIXの egrep 演算のみを受け入れ最左最長全体一致を実装している POSIX モードもあります。


RE2を利用したプログラムを書き始めるなら、C++ API description をご覧ください。実装に関する詳細については 野生の正規表現マッチング(Regular Expression Matching in the Wild) をご覧ください。

re2 - 高効率で原理に基づいた正規表現ライブラリ

以下、re2/re2.h より

re2

re2 正規表現ライブラリへの C++ インターフェイスです。
RE2 はPerlスタイルの正規表現を(\d, \w, \s, ... のような拡張も)サポートします。

正規表現文法:

このモジュールは re2 ライブラリを使用しているため、re2 の正規表現文法をサポートしています。これは Perl のものに似ていますが、いくつかのより込み入った部分は捨てられています。具体的には、後方参照と汎用アサーション、あと\Zが使えません。

RE2 がサポートする文法と、PCREやPERL正規表現との比較については http://code.google.com/p/re2/wiki/Syntax をご参照ください。Perl正規表現にあまり詳しくない人のために、よく使われる拡張の例をここに挙げておきます。

"hello (\\w+) world" -- \w は「ワード」文字にマッチ
"version (\\d+)" -- \d は数字にマッチ
"hello\\s+world" -- \s はホワイトスペース文字にマッチ
"\\b(\\w+)\\b" -- \b は単語境界で空でない文字列にマッチ
"(?i)hello" -- (?i) は大文字小文字の区別をしなくする
"/\\*(.*?)\\*/" -- .*? は . を可能な最小の回数だけマッチ

マッチング・インターフェイス

完全一致("FullMatch")演算は、与えられたテキストが与えられたパターンに正確にマッチしているかをチェックします。

例:マッチ成功
CHECK(RE2::FullMatch("hello", "h.*o"));
例:マッチ失敗(完全一致が求められている)
CHECK(!RE2::FullMatch("hello", "e"));

UTF-8 とマッチングインターフェイス

デフォルトで、パターンと入力テキストはUTF-8として解釈されます。
RE2::Latin1 オプションを使うと Latin-1 として解釈されます。

例:
CHECK(RE2::FullMatch(utf8_string, RE2(utf8_pattern)));
CHECK(RE2::FullMatch(latin1_string, RE2(latin1_pattern, RE2::Latin1)));

部分文字列抽出ありマッチング

マッチした部分を抽出するためのポインタ引数を追加することができます。

例:”ruby" をsに、1234をiに抽出
int i;
string s;
CHECK(RE2::FullMatch("ruby:1234", "(\\w+):(\\d+)", &s, &i));
例:文字列はint変数に格納できないため失敗する
CHECK(!RE2::FullMatch("ruby", "(.*)", &i));
例:十分な部分パターンが無いので失敗する
CHECK(!RE2::FullMatch("ruby:1234", "\\w+:\\d+", &s));
例:余った部分パターンは抽出されない
CHECK(RE2::FullMatch("ruby:1234", "(\\w+):(\\d+)", &s));
例:NULLの中には抽出されない
CHECK(RE2::FullMatch("ruby:1234", "(\\w+):(\\d+)", NULL, &i));
例:整数がオーバーフローして失敗
CHECK(!RE2::FullMatch("ruby:1234567891234", "\\w+:(\\d+)", &i));

注(rsc): 部分文字列を問うことで、成功するマッチがかなり遅くなります。これは将来もう少し高速になるかもしれませんが、現時点ではPCREより遅いです。一方、失敗するマッチは部分文字列の抽出を行わないマッチと同様*とても*速く走ります(PCREより速いです)、

部分的マッチ (PartialMatch)

パターンをテキストの任意の部分文字列とマッチさせたい場合には PartialMatch 演算が使えます。

例:文字列の単純な検索
CHECK(RE2::PartialMatch("hello", "ell"));
例:文字列中に最初に現れる数字を見つける
int number;
CHECK(RE2::PartialMatch("x*100 + 20", "(\\d+)", &number));
CHECK_EQ(number, 100);

コンパイル済み正規表現

RE2は別々のコンパイル段階を必要とせず、任意の文字列を正規表現として利用しやすくします。
速度が重要ならば、プリコンパイルした RE2 オブジェクトをパターンから作成し、それを複数回使用してください。そうすれば、一般にはテキストを sscanf より高速にパースすることが可能です。

例:より高速なマッチングのために、パターンをプリコンパイルする
RE2 pattern("h.*o");
while (ReadLine(&str)) {
  if (RE2::FullMatch(str, pattern)) ...;
}

テキストをインクリメンタルにスキャンする

Consume 演算は、正規表現を文字列の先頭からマッチさせ、マッチした分だけ先に進めてを繰り返したい場合に便利です。
この演算には、実文字列の部分的な範囲を表現する StringPiece 型を使う必要があります。

例:文字列から、"変数 = 値" 形式の行を読む
string contents = ...;          // 何らかの入力文字列
StringPiece input(contents);    // StringPiece で包む

string var;
int value;
while (RE2::Consume(&input, "(\\w+) = (\\d+)\n", &var, &value)) {
  ...;
}

Consume の呼び出し成功の度に varvalue がセットされ、マッチしたテキストの直後を指すように input を進めます。
正規表現が空文字列にマッチする場合、入力の進みは0バイトになることに注意してください。
使われる正規表現が空文字列にマッチしうる場合、ループの本体はそうしたケースをチェックし、
文字列を先に進めるかループを脱出するかするべきです。

FindAndConsume 演算は Consume に似ていますが、こちらは文字列の先頭からのマッチでなくても構いません。例えば、

RE2::FindAndConsume(&input, "(\\w+)", &word)

を繰り返し呼ぶことで、文字列から全ての単語を抽出することができます。

可変個の引数を使う

上述の演算では、コードを書いている時に引数の個数が分かっている必要があります。
これはいつも可能あるいは容易であるとは限りません(例えば、正規表現が実行時に算出される場合とか)。
実行中にマッチ引数の個数が決定されるような場合には、これらの演算の "N" バージョンを使うことができます。

例:
const RE2::Arg* args[10];
int n;
// ... args を RE2::Arg 型の値へのポインタで埋める ...
// ... n にはRE2::Argオブジェクトの個数をセット ...
bool match = RE2::FullMatchN(input, pattern, args, n);

最後の文は以下と等価です

bool match = RE2::FullMatch(input, pattern,
                            *args[0], *args[1], ..., *args[n - 1]);

16進/8進/C言語方式記数法(C-Radix)をパースする

ポインタに数値を渡した場合にはデフォルトで、対応するテキストは10進数値として解釈されます。
代わりに Hex(), Octal() あるいは CRadix() 演算子のどれかを呼び出し、ポインタをラップすることで、テキストを他の基数で解釈することができます。
CRadix 演算子C言語形式の "0"(8進数)や "0x"(16進数)接頭辞を解釈しますが、デフォルトは10進数です。

例:
int a, b, c, d;
CHECK(RE2::FullMatch("100 40 0100 0x40", "(.*) (.*) (.*) (.*)",
      RE2::Octal(&a), RE2::Hex(&b), RE2::CRadix(&c), RE2::CRadix(&d));

では a,b,c,d それぞれに64が入ります。