Boyer Moore Algorithmus

[Ginko]

Hallo, hier diese Klasse http://www.delphipraxis.net/108604-post5.html, zum durchsuchen von Textdateinen, teste ich gerade. Allerdings gehen ab und zu ein paar Wörter verloren...
Ich weiß jetzt nicht ob es an Lazarus liegt oder ob ich sonst ein Fehler eingebaut habe.

Den Code, den ich aus dem oben verlinkten Projekt übernommen habe und unter Lazarus zum laufen gebracht habe, ist im Anhang.
In der Textdatei ist ein Text bei dem das lezte Wort, bei der Suche nicht berücksichtigt wird. Es kommt aber auch vor das ein Wort mitten drin nicht gezählt wird.

[Furtbichler]

Hi,

Ich kann es nicht belegen, aber laut Recherche sind die Delphi-Boyer-Moore-Implementierungen im Netz fehlerhaft. Ob das für den JsTextSearch-Code gilt, kann ich nicht sagen.

Aber was hält dich davon ab, es erst einmal mit einer einfachen Implementierung zu versuchen?

Delphi-Quellcode:

Function CountWords (Const text, wort : String) : Integer;
Var
  i : Integer;

Begin
  i:=1;
  Result := 0;
  repeat
    i := StrUtils.PosEx(wort,text,i)+1;
    if i>1 then inc(Result) else exit;
  until false
End;

Es verwendet 'PosEx', welches einen Teilstring ab einer bestimmten Stelle sucht. Nach dem Finden des Wortes wird dessen Position + 1 als nächste Anfangsposition verwendet. Das kann man alles natürlich noch verbessern, aber für den Anfang sollte es reichen.

Superduperschnell ist es nicht, aber benötigst du unbedingt BM? Und wenn ja, dann vermutlich besser QuickSearch, Horspool o.ä.

[Ginko]

Danke für die Antwort. Schade das die fehlerhaft sind...

So eine ähnliche Implementierung hatte ich schon. Ich werde das ganze mal noch hier mit versuchen http://www.delphipraxis.net/712289-post42.html. Allerdings meckert hier Lazarus bei einigen Assemblerbefehelen.

Z.B. hier:
@FillSkip: movzx edx,[edi+ecx] // SearchFor[i] FastPosUnit.pas(85,30) Error: Asm: [movzx reg32,mem32] invalid combination of opcode and operands

Aber das wäre vielleicht ein neues Thema.

[BUG]

Zitat von Furtbichler:

Und wenn ja, dann vermutlich besser QuickSearch, Horspool o.ä.

Die Implementierung von Quicksearch sieht gar nicht so kompliziert aus, dass sollte man in Delphi übertragen können.

[p80286]

Hast Du denn das Delphi-Original nicht?

Delphi-Quellcode:

unit BoyerMooreHorsepool;

interface

function Search_BMH_Unrolled(sourcestring,suchstr: String): Integer;

implementation


type
  TBC_IntArray = Array[Char] of Integer;


function PreProcess_BMH_BC(p: String): TBC_IntArray;
var
  i,
  m : Integer;
  c : Char;
begin
  m := Length(p);
  for c := low(Char) to High(Char) do
    result[c] := m;
  for i := 1 to m-1 do
    result[p[i]] := m-i;
end;

// Suche mit Horspool, direkt die unrolled-Variante. Sehr ähnlich zu BM_Unrolled
function Search_BMH_Unrolled(sourcestring,suchstr: String): Integer;
var
  m, n, k, j: Integer;
  BC      : TBC_IntArray;
  BC_last : Integer;
  Large   : Integer;
begin
  m := Length(suchstr);
  n := Length(sourcestring);
  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 := 0;

  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;
        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;

end.

[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