SkRegExp version 3.0 は開発中

SkRegExp version 3.0 が未だに公開されないのは最適化の深みにはまっているからです。

以前「SkRegExp はまだ終わらない!」という記事の中で書いたのは次の5つ。

  1. 大文字小文字を区別しない比較を Unicode 標準に対応。
  2. Perl 5.14 互換の正規表現への対応
  3. UnicodeProp.pas の切り離し。
  4. 最適化の見直し
  5. UFT-16 からの解放

5は次のバージョンへ持ち越しです。

1~3は既に実装済で、テストも終わっています。

今、はまっているのは4の最適化です。

具体的には Aho-corasick 法の実装です。

Perl|PHP|Pyton のような検索には Aho-corasick が最適です。

実は3年前にも一度実装を試みました。

が、性能が上がらなくて諦めています。

今回再度挑戦した理由は、前回のは「実装が悪かっただけでは?」とふと思ったからです。

前回は文字の保持に TStringHash を使ったのですが、これを自前のに変えたら速度が出ました。

やはり実装が悪かったんです。

で、Aho-corasick 法をどこまで適応するかで悩んでいます。

たとえば正規表現 Perl|PHP|Pyton|PerlPHP を PerlPHP にマッチさせたとき、Perl にマッチするのが 従来型NFAエンジンの正しい挙動です。

しかし、Aho-corasick 法でマッチさせると PerlPHP にマッチするのが正しいです。

これはまずい。

つまり、整合性を図るなら、最適化だけでなく、正規表現エンジンにも Aho-corasick 法を組み込まないとならないわけです。

となると、結構な大手術です。

どのくらい掛かるか想像できません。

もしかしてその間にモチベーションが落ちてしまうかも?

ここで決断できずにいました。

でも、今決めました。

Aho-corasick 法は最適化だけで使う、と。

というわけで、SkRegExp version 3.0 は今月中に公開する予定です。

お楽しみに。

あ、楽しみにしている人がいれば、ですが。

コメントを残す

メールアドレスが公開されることはありません。