Quick Search algorithm for Delphi

SkRegExp ばかり触っていると飽きてくるので、他の事をやってみる。

とは言っても SkRegExp がらみだが。

SkRegExp の最適化で、高速な文字列検索を実装したいと考えている。

Boyer-Moore より速いアルゴリズムがあると聞いたので、ネットで探してみた。

Quick Search と言うのが見つかった。

早速、Delphi に移植してみた。

最初、Unicode を使うには文字数分のテーブルが必要なのか?と思った。

もちろん、そんなもん非現実的だ。

そこで、効率は悪くなるが、下位バイトだけ使うことにして作ってみたのが以下のソース。

試してみたがやっぱり速い。

アルゴリズムそのままなので著作権は主張しない。自由に使ってください。

function QuickSearch(const AText, APattern: string): Integer;
var
  TextP, PatternP: PChar;
  SkipTable: array[0..256] of Integer;
  I, PatternLen, TextLen, Low: Integer;
begin
  Result := 0;
  PatternLen := Length(APattern);
  TextLen := Length(AText);
  if TextLen < PatternLen then
    Exit;
  {パターンが1文字ならQuick Seachの意味がない}
  if PatternLen = 1 then
  begin
    Result := Pos(APattern, AText);
    Exit;
  end;
  TextP := PChar(AText);
  PatternP := PChar(APattern);
  for I := 0 to 256 do
  SkipTable[I] := PatternLen + 1;
  for I := 0 to PatternLen - 1 do
  begin
    Low := Integer(PatternP[I]) and $FF;
    SkipTable[Low] := PatternLen - I;
  end;
  Result := 0;
  while Result < TextLen - PatternLen do
  begin
    if StrLComp(TextP + Result, PatternP, PatternLen) = 0 then
    begin
      Inc(Result);
      Exit;
    end;
    Low := Integer(TextP[Result + PatternLen]) and $FF;
    Inc(Result, SkipTable[Low]);
  end;
end;

コメントを残す

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