Boyer-Moore für Unicode

[Gausi]

Ein Ansatz, den ich mal verfolgt habe, ist UTF8. D.h. Text und Muster liegen UTF8 kodiert vor, und die Suche läuft dann auf dem Bytemuster der Strings. Das klappt auch ganz gut.
Ansonsten wäre eine Einschränkung der Tabelle sinnvoll, wenn man die verwenden Zeichen einschränken kann (z.B. ohne ostasiatische Zeichen). Für die anderen Zeichen setzt man dann den Bad-Character-Shift nur auf 1.

Zitat von Schorschi5566:

Die anderen Aspekte bei Boyer-Moore (Good-Suffix) sind unabhängig von der Alphabetgröße, spielen dabei also keine Rolle.

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.

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