Boyer Moore Algorithmus

[Ginko]

Danke, den hatte ich auch grad gefunden nur etwas weniger ausführlich. Beim testen fehlen aber fast die Hälfte der Wörter. Vielleicht habe ich auch einen Fehler in der NextPos Funktion, muss mal schauen.

[Ginko]

Zur Sicherheit habe ich mal nicht meine NextPos geholt, sondern hier diese http://www.swissdelphicenter.ch/de/showcode.php?id=474. Wenn ich hier Pos mit Search_BMH_Unrolled ersetze fehlen immer ein haufen Wörter.

Delphi-Quellcode:

 function NextPosSwiss(SearchStr, Str: string; Position: Integer): Integer;
begin
  Delete(Str, 1, Position - 1);
  Result := Search_BMH_Unrolled(Str,SearchStr);  //Pos(SearchStr, Str);//
  if Result = 0 then Exit;
  if (Length(Str) > 0) and (Length(SearchStr) > 0) then
    Result := Result + Position + 1;
end;

[Horst_]

Hallo,

Furtbichlers Vorschlag ist doch insofern sinnig, dass man von einer Festplatte die Daten bestimmt nicht so schnell lesen kann, wie PosEx(wort,text) oder strPos(pAnsiChar(aBuffer[0]), wort) { -> Puffer um 1 vergrößern und dort eine #0 reinschreiben} die Sachen finden.
Wie ist denn die minimale Wortlänge, ab der Boyer Moore überhaupt Sinn macht?

Gruß Horst

[CCRDude]

Da ich selber drei oder vier Versionen aus dem Netz bearbeitet habe, bevor ich mir das selber implementiert habe, kann ich Furtbichler nur recht geben.

Die TJsTextSearch zum Beispiel hat funktionierte so nicht, sobald einzelne Zeichen mehrfach im Suchbegriff vorkommen - da gibt es einen Fehler in InitSkipTable (der Code von p80286 zeigt wie die Skiptable richtig aufgebaut werden muss) und einen in Search.

Irgend eine Implementierung hatte gar einen Sonderfall, wo die Suche in einem von 1 Million Fällen (eine bestimmte Datei halt) endlos lief - da wurde halt immer wieder in der Datei zurück gesprungen.

[p80286]

Zitat von Horst_:

Hallo,

Furtbichlers Vorschlag ist doch insofern sinnig, dass man von einer Festplatte die Daten bestimmt nicht so schnell lesen kann, wie PosEx(wort,text) oder strPos(pAnsiChar(aBuffer[0]), wort) { -> Puffer um 1 vergrößern und dort eine #0 reinschreiben} die Sachen finden.

Was bitte hat die Festplatte damit zu tun? Soweit mir bekannt ist, müssen in den allermeisten Fällen alle Daten, die verarbeitet werden sollen im (Haupt)Speicher vorliegen.

Zitat:

Wie ist denn die minimale Wortlänge, ab der Boyer Moore überhaupt Sinn macht?

Es kommt darauf an.... es gilt aber immer noch je länger, desto besser.
Und je mehr Bumms Dein Rechner hat, desto weniger benötigst Du BM.

Zitat von Ginko:

..fehlen immer ein haufen Wörter.

Du bedenkst aber, daß Hallo<>hallo<>HALLO<>HALLo ist?

@CCRDude
ist nicht "Mein" Code, ich hab es aus einem älteren tread den ich nicht mehr wiederfinde.

Gruß
K-H

[Ginko]

Hier ist mal mein Versuchsaufbau:

Delphi-Quellcode:

unit Unit1;
{$mode objfpc}{$H+}

interface

uses
  Classes, SysUtils, FileUtil, Forms, Controls, Graphics, Dialogs, StdCtrls, BMH, strutils;

type

  { TForm1 }

  TForm1 = class(TForm)
    Button1: TButton;
    Button2: TButton;
    Edit1: TEdit;
    Label1: TLabel;
    Label2: TLabel;
    procedure Button1Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
  private
    { private declarations }
  public
    { public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.lfm}

{ TForm1 }

function NextPosBMH(SearchStr, Str: string; Position: Integer): Integer;
begin
  Delete(Str, 1, Position - 1);
  Result := Search_BMH_Unrolled(Str,SearchStr);
  if Result = 0 then Exit;
  if (Length(Str) > 0) and (Length(SearchStr) > 0) then
    Result := Result + Position + 1;
end;

Function CountWordsStd(Const text, wort : String) : Integer;
Var
  i : Integer;
Begin
  i:=1;
  Result := 0;
  repeat
    i := PosEx(wort,text,i)+1;
    if i > 1 then inc(Result) else exit;
  until false
End;

Function CountWordsStdBMH(Const text, wort : String) : Integer;
Var
  i : Integer;
Begin
  i:=1;
  Result := 0;
  repeat
    i := NextPosBMH(wort,text,i)+1;
    if i > 1 then inc(Result) else exit;
  until false
End;

procedure TForm1.Button1Click(Sender: TObject); //Std Pos
var
  Filestream : TFileStream;
  SuchWort, SuchText: String;
begin
  SuchWort:= Edit1.Text;

  Filestream:=TFileStream.Create('test.txt',fmOpenRead);
  Try
    SetLength(SuchText,Filestream.Size);
    Filestream.Read(SuchText[1],Length(SuchText));
    Label1.Caption:= IntToStr(CountWordsStd(SuchText,SuchWort));
  Finally
    Filestream.Free;
  end;
end;

procedure TForm1.Button2Click(Sender: TObject);   // BMH
var
  Filestream : TFileStream;
  SuchWort, SuchText: String;
begin
  SuchWort:= Edit1.Text;

  Filestream:=TFileStream.Create('test.txt',fmOpenRead);
  Try
    SetLength(SuchText,Filestream.Size);
    Filestream.Read(SuchText[1],Length(SuchText));
    Label1.Caption:= IntToStr(CountWordsStdBMH(SuchText,SuchWort));
  Finally
    Filestream.Free;
  end;
end;
end.

Textdatei test.txt:

Code:

Point

Line

Square

Point Point

Triangle

Line

Point

Die Funktion, die mit der Standard Pos arbeitet findet für "Point" -> 4
Die Funktion, die mit BMH arbeitet findet für "Point" -> 1

[Horst_]

Hallo,

nur mal als Hinweis, wie schnell PosEx ist
Ich habe diese Zeile:
"Point Line Square Point Point Triangle Line PointPoint Line Square PointPoint>>"

So oft hintereinanderkopiert, bis 1Gb belegt waren.Das schafft kein PC-CPU-Cache.
"Gesamttextlaenge 1.000.000.000"
Die Standardsuche nach 87.500.000 "Point" dauerte knapp 2,8 Sekunden
Die Standardsuche nach 12.500.000 "Triangle" dauerte knapp 1,03 Sekunden
Die Suche nach nach 25.000.000 "Point Lin" dagegen um 3,5 Sekunden

Das "T" bei Triangle ist einzigartig im Satz-> "T" gefunden=> Wort gefunden,
während "Point" 7 mal vorkommt, also müssen auch entsprechend oft mindestens 5 Zeichen untersucht werden, was in 5 von 7 Fällen eben vergebens ist.
Das BMH einen in 2.5 Sekunden findet ist nicht wirklich hilfreich

Apropos "Grautier", das wird in 0,72 Sekunden nicht gefunden."G" gibt es nicht.
"Papagei" braucht 2,3 Sekunden um nicht gefunden zu werden."P" sehr oft.

Gruß Horst

[Furtbichler]

Kein Wunder das die BM-Suche so langsam: Hier wird ja jedesmal der String gekürzt und BM liefert eh falsche Ergebnisse, denn er bricht beim ersten Fund nicht ab sondern sucht weiter. Da scheint ein 'exit' zu fehlen:

Delphi-Quellcode:

...
     if j=m then
       begin
         // Muster gefunden
         result := k - j + 1;
         exit; // <<<<<<<<<<<<<<<<<<<<<<< Fehlt
         // Die nächste Zeile ist auskommentiert, denn wir wollen ja nicht weitersuchen
         // k := k + m; //oder: k+1, oder: break; je nachdem, wie man den Text komplett durchsucht haben will
       end else
...

Der Code lässt sich im Übrigen leicht modifizieren, um ein sehr schnelles PosEx_BMH zu implementieren, d.h. 'Suche ab Position'. Hier die Korrekturen.

Delphi-Quellcode:

function Search_BMH_Unrolled(sourcestring,suchstr: String;Offset : integer=1): Integer;
var
   m, n, k, j: Integer;
   BC : TBC_IntArray;
   BC_last : Integer;
   Large : Integer;
begin
   m := Length(suchstr);
   n := Length(sourcestring)-Offset+1;
   Large := m + n + 1;

   BC := PreProcess_BMH_BC(suchstr);

   // "echten" BC-Shift merken
   BC_last := BC[suchstr[m]];
   // BC(lastCh) mit "Large" überschreiben
   BC[suchstr[m]] := Large;

   k := m;
   result := Offset-1;

   while k <= n do
   begin
       //fast loop
       repeat
         k := k + BC[sourcestring[k]];
       until k > n;

       //undo
       if k <= Large then
         //Muster nicht gefunden
         break
       else
         k := k - Large;

       j := 1;
       // slow loop
       while (j < m) and (suchstr[m-j] = sourcestring[k-j]) do
         inc(j);

       if j=m then
       begin
         // Muster gefunden
         result := k - j + 1;
         exit;
       //  k := k + m; //oder: k+1, oder: break; je nachdem, wie man den Text komplett durchsucht haben will
       end else
       begin
           // Muster verschieben
           if sourcestring[k] = suchstr[m] then
             k := k + BC_last // Hier dann den original-Wert nehmen
           else
             k := k + BC[sourcestring[k]];
       end;
   end;
end;

PS: Kann mal einer 'Horsepool' richtig schreiben? Das ist kein Pool für Pferde, sondern der Mann heißt 'Nigel Horspool'.