SkRegExp version 1.1.7 公開

SkRegExp version 1.1.7 を公開しました。仕様を固めたのでβ版の表記をはずしました。

今回の目玉は、version 1.2 以降で採用するつもりだった幾何級数的マッチ対策です。

やってみたら意外にカンタンに実装できてしまいました。

幾何級数的マッチ対策のアイデアはシンプルです。

幾何級数マッチが起こるのは、バックトラックが起こったとき、同じ文字位置で同じ NFA 状態が何度もマッチが行われるからです。

したがって、バックトラックが起きたときの文字位置と NFA 状態を保存して、同じ位置で同じ NFA 状態のバックトラックが起こったら即失敗にするようにしました。

なお、条件定義 CHECK_MATCH_EXPLOSION を無効にすればこのチェックを行わなくなります。ただし、チェック有り無しでの速度の違いは10%程度です。

ちなみに、幾何級数的マッチは以下のプログラムでどういうものかチェックできます。

version 1.1.7 で以下のプログラムを実行するとあっという間に終了しますが、version 1.0.x だと固まってしまいます。

実施にはバグっているわけではなく、マッチに時間がかかっているだけです。ものすごく時間がかかるので短気な方は実行しない方がいいでしょう

procedure TForm1.Button1Click(Sender: TObject);
var
  I: Integer;
  r: SkRegExpW.TSkRegExp;
  S, E, H, T: REString;
  TI, GI: Cardinal;
begin
  r := SkRegExpW.TSkRegExp.Create;
  try
    H := 'a?';
    T := 'a';
    E := H + T;
    S := T + 'a';
    r.Expression := E;
    Memo1.Lines.BeginUpdate;
    for I := 1 to 30 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
      else
        Memo1.Lines.Add('No Match?');
      H := H + 'a?';
      T := T + 'a';
      E := H + T;
      S := T;
    end;
    Memo.Lines.EndUpdate;
  finally
    r.Free;
  end;
end;

コメントを残す

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