現在位置：  Delphiログ >  QuickSearch アルゴリズムの実装

QuickSearch アルゴリズムの実装

QuickSearch は 高速な文字列検索アルゴリズム Boyer-Moore 法の亜種の一つで、その名の通り、オリジナルのBM法より速く検索が可能です。

きれいなものにはとげがあるの例えの通り、高速に動作するものは難しいのが相場ですが、QuickSearchは実装方法もカンタンです。

そんなわけで、Delphiで実装してみました。


function QuickSearch(AText: PWideChar; ATextLen: Integer;
  APattern: PWideChar; APatternLen: Integer): PWideChar;
var
  Index, I, L, Low: Integer;
  SkipTable: array[0..256] of Integer;
begin
  Result := nil;

  if ATextLen < APatternLen then
    Exit;

  {パターンが1文字ならQuick Seachの意味がない}
  if APatternLen = 1 then
  begin
    Result := StrPos(AText, APattern);
    Exit;
  end;

  for I := 0 to 256 do
    SkipTable[I] := APatternLen + 1;

  for I := 0 to APatternLen - 1 do
  begin
    Low := Integer(APattern[I]) and $FF;
    SkipTable[Low] := APatternLen - I;
  end;

  Index := 0;

  while Index < ATextLen - APatternLen do
  begin
    if StrLComp(AText + Index , APattern, APatternLen) = 0 then
    begin
      Result := AText + Index;
      Exit;
    end;

    Low := Integer(AText[Index + APatternLen]) and $FF;
    Inc(Index, SkipTable[Low]);
  end;
end;

UncodeDelphiが出ているご時世ですから、Unicodeの対応を意識しました。

BM法でUnicodeに対応するには次の３つの方法があるようです。

  1. SkipTable を $10FFFF 個用意する。
  2. SkipTable をハッシュテーブルで実装する。
  3. Unicode文字列をバイト列で処理し、マッチ後に正しい場所かチェックする

１と２は面倒くさそうだし、それだけで時間がかかりそう。３は大文字小文字の違いとか半角全角、ひらがなカタカナの同一視が面倒くさそう。

そこで今回は、移動量が少なくなるのを承知で下位１バイトだけを使ってみました。まあ、そこそこの性能は出ているのでいいでしょう。

ちなみに、アルゴリズムそのままなので著作権は主張しません。あなたが作ったものと同じように使ってもらって構わない。

Tips

ブログ

リンク