米Google、高速・低メモリ消費の正規表現ライブラリ「RE2」を公開

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

　Googleによると、同社はCode SearchやSawzallといったインフラやアプリケーションで正規表現を利用しているが、バックトラックアルゴリズムを利用した従来の正規表現実装では入力データに対し処理時間が指数的に増加することが問題となっていた。また、固定サイズのスタックを持つC++のマルチスレッドプログラムの場合、従来の正規表現実装ではスタックを使い切ってスタックオーバーフローを発生させることがあったという。これらを解決するために独自の正規表現エンジンを開発したとのこと。

　RE2はどのような入力や正規表現に対しても一定の小さいメモリ量で動作するように開発されているのが特徴。オートマトン理論の下、処理時間は入力に対して線形に増加するよう保証されている。メモリ制限も実装されており、使用するメモリ容量を一定に保つことが可能とのこと。特に大容量のデータを処理する場合、従来の正規表現エンジンと比べて高速に動作する場合が多いという。

　従来の正規表現実装と同様、RE2ではPerlやPCRE（Perl Compatible Regular Expressions）の正規表現のほとんどに対応。ただし、後方参照や独占的量指定子など一部対応していない表現もある。また、POSIXのegrepが対応する表現のみ利用できるモードも用意されている。

　ライセンスはNew BSD Licenseで、Google Codeのページでコードやドキュメンテーションを入手できる。

Google
http://www.google.com/

Google Codeのプロジェクトページ
http://code.google.com/p/re2/

RE2が対応する正規表現一覧
http://code.google.com/p/re2/wiki/Syntax