この発言に対し以下のコメントが寄せられています

#01368　ぜえた          さん　EBMユニット(interface)

#01369　ぜえた          さん　EBMユニット(implementation)




　こんにちは、ぜえた です。



もっとも高速な文字列検索法は Boyer-Moore法であるといわれていますが、教
科書には単一文字列の検索しか載っていません。そこで、複数文字列が検索で
きるようにＢＭ法を拡張してみました。

パターンを順方向に読む複数文字列検索法（トライ）を逆方向から読むようＢ
Ｍ化したものです。

どうやっているのかは説明するのが難しいのでパスします。
特にテーブルを作っているところは自分でもわかりません(^^;　一応、与えら
れた文字列からトライを作りつつ、failer funtion, skipの表などを作ってい
るはずです。

今回アップするにあたって、Ansiに対応などのオプションをつけてみました。
バグは必ず入っていると思うので、だれか見つけてください(^^;

　ＢＭ法に関しては、石畑清「岩波講座ソフトウェア科学３　アルゴリズムと
データ構造」岩波書店。テーブルの作成にプログラム5.1.17を参考にしていま
す。
　トライに関しては、Aho, Sethi, Ullman「Compilers - Principles, 
Techniques, and Tools」Chapter3 Exercisesを参考にしました。


property Patterns: TStrings; 
(複数の)パターン文字列を指定します。

procedure SearchInit(S, E: PChar);
検索する前に呼び出します。Sにテキストの先頭、Eにテキストの末尾の次の文
字を指すポインタを指定します。

property Search: TEBMSearchProc;
プロパティになってますが、function Search: Boolean; というメソッドだと
思ってください。文字列の検索をし、存在したら True、存在しなかったら 
Falseを返します。

property FoundPatternIndex: Integer;
Searchが Trueを返した時、どの文字列が見つかったか、Patternsプロパティ
のインデックスを返します。

property FoundPos: PChar;
Searchが Trueを返した時、見つかった文字列のテキスト上の位置を返しま
す。

property Options: TSearchOptions;
(soIgnoreCase, soAnsi)の集合を指定します。soIgnoreCaseを指定すると大文
字小文字の区別をせず、soAnsiを指定すると Ansi対応になります。ただし、
soIgnoreCase, soAnsi両方指定しても、「ａ」と「Ａ」はマッチしません。１
バイト文字の大文字小文字のみ区別しません。

パターンを「a」「b」「c」「ab」「bc」「abc」、テキストを「abc」とする
と、マッチの順番は「a」「b」「ab」「c」「bc」「abc」になります。

//////////////////////// サンプルプログラム ////////////////////////

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls;

type
  TForm1 = class(TForm)
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  private
    { Private 宣言 }
  public
    { Public 宣言 }
  end;

var
  Form1: TForm1;

implementation

uses Consts, EBM;

{$R *.DFM}

function FileToStr(const FileName: string): string;
var
  Handle: THandle;
  Size: Integer;
begin
  Handle := FileOpen(FileName, fmOpenRead or fmShareDenyWrite);
  if Handle < 0 then
    raise EFOpenError.CreateFmt(SFOpenError, [FileName]);
  try
    Size := GetFileSize(Handle, nil);
    SetString(Result, nil, Size);
    FileRead(Handle, PChar(Result)^, Size);
  finally
    FileClose(Handle);
  end;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  S: string;
  EBMSearch: TEBMSearch;
  Counts: array[0..2] of Integer;
begin
  S := FileToStr('C:\Del3\Source\VCL\Classes.pas');
  EBMSearch := TEBMSearch.Create;
  with EBMSearch do begin
    Options := [soIgnoreCase];
    with Patterns do begin
      BeginUpdate;
      Add('procedure');
      Add('function');
      Add('Property');
      EndUpdate;
    end;
    SearchInit(@S[1], @S[Length(S)+1]);
    FillChar(Counts, SizeOf(Counts), 0);
    while Search do begin
      Inc(Counts[FoundPatternIndex]);
    end;
  end;
  Caption := Format('%d, %d, %d', [Counts[0], Counts[1], Counts[2]]);
end;

end.

                                                    ぜえた (QZC05100)
 


Original document by ぜえた          氏 ID:(QZC05100)

ここにあるドキュメントは NIFTY SERVEの Delphi Users' Forum の16番会議室「玉石混淆みんなで作るSample蔵」に投稿されたサンプルです。これらのサンプルはボーランド株式会社がサポートする公式のものではありません。また、必ずしも動作が検証されているものではありません。これらのサンプルを使用したことに起因するいかなる損害も投稿者、およびフォーラムスタッフはその責めを負いません。使用者のリスクの範疇でご使用下さい。