Boyer-Moore für Unicode

[Schorschi5566]

Hallo Gausi,

Zitat von Gausi:

Die spielen in der Praxis sowieso fast nie eine Rolle. Bzw. es ist eher andersrum. Boyer-Moore nur mit Bad-Character ist in der Regel schneller als Boyer-Moore mit Bad-Character und Good-Suffix.

Stimmt, wer sucht schon nach "supersupe".

Ich hab's jetzt doch mal mit einem 64K-Array probiert. Wenn man ausnutzt, dass das Array zu 0 initialisiert wird, ist die Performance doch recht gut.

Delphi-Quellcode:

    // Sprungtabelle für Bad-Character
    SetLength(FBadTable, 65536);
//    for i := 0 to 65535 do
//      FBadTable[i] := pLen;

    for i := 0 to pLen do
      FBadTable[Ord(sSearch[i+1])] := - i - 1; // später pLen addieren

Dann muss man beim Skipwert natürlich später noch plen addieren, was aber wesentlich weniger ins Gewicht fällt als die Initialisierung der Skiptable zu pLen.

Delphi-Quellcode:

  while Offset <= sLen do
  begin
{$IFDEF TBDEBUG} ShowOffset(Offset - plen + 1, sText, sSearch); {$ENDIF}
    j := 0; // Anzahl der Übereinstimmungen
    while j < pLen do
    begin
      if sText[Offset - j] = sSearch[pLen - j] then
        inc(j)
      else
      begin
        BadSkip := FBadTable[Ord(sText[Offset - j])] + pLen - j;
        if BadSkip > FGoodTable[j] then
        begin
{$IFDEF TBDEBUG} me.Lines.Add('Bad:' + IntToStr(BadSkip); {$ENDIF}
          inc(Offset, BadSkip);
        end
        else
        begin
{$IFDEF TBDEBUG} me.Lines.Add('Good: ' + IntToStr(FGoodTable[j])); {$ENDIF}
          inc(Offset, FGoodTable[j]);
        end;
        Goto NextStep;
      end;
    end;
    Exit(Offset - pLen + 1);
NextStep:
  end;