幾何級数マッチ対策へ

幾何級数マッチとはマッチするパターンが膨大でマッチにものすごく時間がかかる処理のこと。NFAエンジンでは避けて通れない。

SkRegExpも例外ではない。以下のプログラムを実行すればすぐに体験できる。

フォームにTMemoとButton1をを貼り付けてButton1.OnClickに以下のソースを貼り付ける。

var
  I: Integer;
  r: TSkRegExp;
  S, E: REString;
  TI, GI: Cardinal;
begin
  r := TSkRegExp.Create;
  try
    E := 'a*a';
    S := 'a';
    r.Expression := E;
    Memo1.Lines.BeginUpdate;
    for I := 1 to 25 do
    begin
      TI := GetTickCount;
      r.Expression := E;
      if r.Exec(S) then
      begin
        GI := GetTickCount - TI;
        Memo1.Lines.Add(Format('%d,%d', [Length(S), GI]));
      end;
      S := S + 'a';
      E := E + '*a';
    end; 
    Memo1.Lines.EndUpdate;
  finally
    r.Free;
  end;
end;

forループがこの程度なら何とか終わるが、25以上にすると制御が帰ってこない。

これはバグではない。マッチするパターンが膨大になって処理が終わらないだけだ。

ちなみに、PCREだとスタックを食いつぶしてしまうようで途中で落ちてしまう。

PCREのやり方も一つの考え方だと思う。無限にマッチに時間がかかるのではあればエラーで終わりにするというのも方法だ。

しかし、SkRegExpの場合、ループを再帰で処理していないので残念ながら落ちない。

これに対処しているのはNFAエンジンでは鬼車くらいだから無視しようか・・・。

でも、面白そうなチャレンジではある。どうしようなあ・・・。

幾何級数マッチ対策へ」への1件のフィードバック

  1. 小宮秀一

    自分でコメント。
    正直、こんな正規表現を書く方が悪いと思うけど、SkRegExpを使う人が正規表現エンジンの仕組みを知っているとは言えないんですよね。

    返信

コメントを残す

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