Boyer-Moore für Unicode

[Schorschi5566]

Hallo DP,

bei "normalen" Alphabeten ist ja der Boyer-Moore-Algorithmus sehr effizient.

Dabei wird eine Skiptabelle (Bad-Character-Table) von der Größe des Alphabets (<= 256 Zeichen) benutzt um Zeichen, die nicht im Suchmuster vorkommen schnell zu finden.

Für Unicode müsste man nun aber eine Tabelle von 64k Größe (oder noch größer?) verwalten, was die Effizienz dann doch in den Keller wandern lässt.

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

Ich habe mal gegoogled und einen Ansatz mit einer Hashtabelle gefunden. Leider war dort aber nicht beschrieben, wie die entsprechende Hashfunktion auszusehen hat, bzw. wie man die Hashtabelle aufbauen muss.

Das Ganze steht und fällt mit einer schnellen Funktion um zu ermitteln ob ein zu untersuchendes Zeichen im Suchmuster vorhanden ist oder nicht.

Hat jemand eine Idee, wie man das bei einem Unicode-Alphabet anstellen sollte?


Grüße,
Uwe

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

[s.h.a.r.k]

Zitat von Schorschi5566:

Ich habe mal gegoogled und einen Ansatz mit einer Hashtabelle gefunden. Leider war dort aber nicht beschrieben, wie die entsprechende Hashfunktion auszusehen hat, bzw. wie man die Hashtabelle aufbauen muss.

Das Ganze steht und fällt mit einer schnellen Funktion um zu ermitteln ob ein zu untersuchendes Zeichen im Suchmuster vorhanden ist oder nicht.

Ich weiß leider nicht, ob das bei Delphi 2010 mit dabei ist, aber bei XE gibts in der Unit Generic.Collections diesen generischen Typ TDictionary<TKey,TValue>, welcher mit Hashes arbeitet. Zur Not kann man aber immer noch THashedStringList aus der Unit IniFiles "vergewaltigen", wie ich das früher immer gemacht hatte Nur weiß ich nicht, ob dir das was bringt!?

[Schorschi5566]

Hallo Armin,

Zitat von s.h.a.r.k:

Ich weiß leider nicht, ob das bei Delphi 2010 mit dabei ist, aber bei XE gibts in der Unit Generic.Collections diesen generischen Typ TDictionary<TKey,TValue>, welcher mit Hashes arbeitet. Zur Not kann man aber immer noch THashedStringList aus der Unit IniFiles "vergewaltigen", wie ich das früher immer gemacht hatte Nur weiß ich nicht, ob dir das was bringt!?

Danke für den Tipp. Die Generics gibt's auch schon in D2010 aber vermutlich wird ein Suchvorgang über TDictionary länger dauern als auf die Art, wie ich es jetzt mache.

Im Prinzip tut nur das Initialisieren des 64k-Array richtig weh. Also lässt man es weg bzw. macht es nur einmal im Constructor. Anschließend werden bei einer neuen Suche nur die Positionen im Array wieder auf 0 gesetzt, die bei der letzten Suche verwendet wurden.

Ich habe das Ganze jetzt mal zu einer Funktion zusammengebaut, der man auch den Offset und die gewünschte Richtung mitgeben kann. Bei kleinen Suchmustern und Suchtexten ist Pos leicht im Vorteil aber ab 10 Zeichen Suchmuster und ca 5k Text, wird Pos dann schon deutlicher abgehängt. Muss man in verschiedenen Texten dasselbe Suchmuster suchen, sieht Pos dann richtig blaß aus weil man in dem Fall die Sprungtabellen nicht neu erzeugen muss.

Wer Lust hat, kann's ja mal testen. Bitte nicht über die paar Gotos mokieren. Es ging mir um Performance und da spart man jeden CPU-Zyklus . Lässt sich aber bestimmt noch weiter optimieren.


Grüße,
Uwe

Delphi-Quellcode:

unit BoyerMoore;

interface

uses
  SysUtils;

type
  TDirection = (dForward = 1, dBackward = -1);

  TBoyerMoore = class
  private
    FLastSearchStr : String;
    FLastSearchDir : TDirection;
    FBadTable, FGoodTable : array of Integer;
  public
    constructor Create;
    function PosBM(const Pattern, Text: String; Offset : Integer = 1; const Dir : TDirection = dForward): Integer; register;
  end;

implementation

{ TBoyerMoore }

constructor TBoyerMoore.Create;
begin
  // Array für Unicode initialisieren
  SetLength(FBadTable, 65536);
end;

// *************
// P  o  s  B  M
// *************
//
// Boyer-Moore Stringsuche
//
// Eingabe:
// --------
// Pattern: Suchmuster
//    Text: Suchtext
//  Offset: Position ab der gesucht werden soll
//     Dir: Richtung in die gesucht werden soll: dForward = vorwärts dBackward = rückwärts
//
// Rückgabe:
// ---------
// =0: kein Match
// >0: Position des ersten Match
//
function TBoyerMoore.PosBM(const Pattern, Text: String; Offset: Integer;
  const Dir: TDirection): Integer; register;
var
  i, j, k, iDir, iPLen, iTLen, iOffKorr, iBadSkip : Integer;
label
  NextTryFwd, MatchedFwd, NextTryBwd, MatchedBwd, NextStep;
begin
  Result := 0;
  iPLen := Length(Pattern);
  iTLen := Length(Text);
  iDir := Ord(Dir);

  if (iPLen > iTLen) or (Offset = 0) or (Offset > iTLen) then
    raise Exception.Create('PosBMEx: Invalid parameter!');

  // Good- und Bad-Table nur neu erzeugen, wenn neues Suchmuster verwendet wird
  // oder die Suchrichtung wechselt.
  if (FLastSearchStr <> Pattern) or (FLastSearchDir <> Dir) then
  begin

    // Bad-Table wieder auf 0 setzen
    for i := 1 to Length(FLastSearchStr) do
      FBadTable[Ord(FLastSearchStr[i])] := 0;

    // Good-Table anlegen
    SetLength(FGoodTable, iPLen + 1);

    // Sprungtabellen abhängig von der Richtung erzeugen
    if Dir = dForward then
    begin
      // Bad-Character-Table vorwärts
      for i := 1 to iPLen do
        FBadTable[Ord(Pattern[i])] := - i; // iPLen später addieren

      // Good-Suffix-Table vorwärts
      for j := 0 to iPLen do
      begin
        for i := iPLen-1 downto 1 do
        begin
          for k := 1 to j do
          begin
            if i - k < 0 then
              Goto MatchedFwd;
            if (Pattern[iPLen - k + 1] <> Pattern[i - k + 1]) then
              Goto NextTryFwd;
          end;
          Goto MatchedFwd;
NextTryFwd:
        end;
MatchedFwd:
        FGoodTable[j] := iPLen - i;
      end;
    end
    else
    begin
      // Bad-Character-Table rückwärts
      for i := iPLen downto 1 do
        FBadTable[Ord(Pattern[i])] := i - 1 - iPLen; // iPLen später wieder addieren

      // Good-Suffix-Table rückwärts
      for j := 0 to iPLen do
      begin
        for i := 2 to iPLen do
        begin
          for k := 1 to j do
          begin
            if i + k - 1 > iPLen then
              Goto MatchedBwd;
            if (Pattern[k] <> Pattern[i + k - 1]) then
              Goto NextTryBwd;
          end;
          Goto MatchedBwd;
NextTryBwd:
        end;
MatchedBwd:
        FGoodTable[j] := i - 1;
      end;
    end;

    FLastSearchStr := Pattern;
    FLastSearchDir := Dir;
  end;

  Offset := Offset + (iPLen - 1) * iDir; // Startoffset
  case Dir of
    dForward:
      iOffKorr := iPLen;
    dBackward:
      iOffKorr := 1;
  end;

  while (Offset <= iTLen) and (OffSet >= 0) do
  begin
    j := 0; // Anzahl der Übereinstimmungen
    while j < iPLen do
    begin
      if Text[Offset - j * iDir] = Pattern[iOffKorr - j * iDir] then
        inc(j)
      else
      begin
        iBadSkip := FBadTable[Ord(Text[Offset - j * iDir])] + iPLen - j;
        if iBadSkip > FGoodTable[j] then
        begin
          inc(Offset, iBadSkip * iDir); // Bad-Table verwenden
        end
        else
        begin
          inc(Offset, FGoodTable[j] * iDir); // Good-Table verwenden
        end;
        Goto NextStep;
      end;
    end;
    Exit(Offset - iOffKorr + 1);
NextStep:
  end;
end;

end.

[omata]

Zitat von Schorschi5566:

Bitte nicht über die paar Gotos mokieren. Es ging mir um Performance und da spart man jeden CPU-Zyklus . Lässt sich aber bestimmt noch weiter optimieren.

Ja, das spart natürlich, wenn man mit Goto nach dem ersten Durchlauf sofort die Schleife verlässt.

Genau

Und das ist dir natürlich nicht aufgefallen, weil Goto nunmal unstrukturiert ist. Naja, bleib bei Deiner super Optimierung (die hättest du auch, wenn du deine Schleifen einfach weglassen würdest).

Edit: Habs gerade nochmal angeschaut (echt gruselig), macht vermutlich aber doch das, was du haben möchtest (leider!, macht es das)

[Schorschi5566]

Hehe, ich hab's doch gewußt. Na ein Verkünder der "einzigen, reinen Wahrheit", meldet sich halt immer zu Wort. Hat ja oft schon religiöse Züge. Und viele der Verkünder verwenden hemmungslos Break, Exit und try-except-Blöcke (am besten über drei Bildschirmhöhen hinweg).

Zitat:

Habs gerade nochmal angeschaut (echt gruselig), macht vermutlich aber doch das, was du haben möchtest (leider!, macht es das)

Wieso leider und gruselig? Effizient, würde ich sagen. Aber ich will mich nicht mit fremden Federn schmücken. Der Teil ist aus den einschlägigen Beispielen für Boyer-Moore entnommen und von mir lediglich an Delphi und die Rückwärtssuche angepaßt worden. (Da war doch noch ein dummes "break" drin, das auf ein Goto gesprungen ist, was logischerweise 2 Jumps bedeutet, wo nur einer nötig ist und wurde prompt von mir durch ein Goto ersetzt. )

Zitat:

weil Goto nunmal unstrukturiert ist

Strukturier's halt ohne Gotos, wenn dir das mit der gleichen Performance und in zehn Zeilen gelingt. Viel Spaß.

Ich bin auch gegen Gotos (aber ich erzähl's nicht jedem bei jeder Gelegenheit) und musste erstmal nachsehen, wie das in Delphi überhaupt geht aber wohl dosiert und wenn es sinnvoll ist habe ich kein Problem dieses Sprachelement einzusetzen.

Im Übrigen gibt es diese Diskussion hier doch schon mehrfach und du musst niemanden bekehren.

[omata]

Zitat von Schorschi5566:

Im Übrigen gibt es diese Diskussion hier doch schon mehrfach und du musst niemanden bekehren.

Tue ich auch nicht. Entschuldigung, dass ich was gesagt habe. ich bereue es schon.

[Schorschi5566]

@Deep-Sea:

Zitat von Schorschi5566:

Aber ich will mich nicht mit fremden Federn schmücken. Der Teil ist aus den einschlägigen Beispielen für Boyer-Moore entnommen und von mir lediglich an Delphi und die Rückwärtssuche angepaßt worden.

@jbg:

Zitat:

Da ist dein "ein JMP gespart" belanglos, was es ohnehin dank Jump-Optimierung seitens Delphi bereits ist. Delphi erkennt, dass du mit "break" auf ein "goto" springst, und leitet den Sprung direkt weiter ohne den Zwischenstopp. (Einfach mal den Assemblercode im CPU-View anschauen).

Danke, das war mir neu.

@all:
Ich hab mal den "goto-verseuchten" Teil umgeschrieben.

Delphi-Quellcode:

      // Good-Suffix-Table vorwärts
      FGoodTable[0] := 1;
      j := 1;
      i := iPLen - 1;
      k := 0;
      bMatch := False;
      while j < iPLen  do
      begin
        while (i > 0) and (k <> j) do
        begin
          while (k < j) and (i - k > 0) and (Pattern[iPLen - k] = Pattern[i - k]) do
          begin
            bMatch := True;
            inc(k);
          end;
          if (k < j) then // kein ganzes Suffix gefunden
          begin
            if i-k <= 0 then
              i := 0 // Maximal-Skip
            else
            begin
              if bMatch then  // kein Match mit dieser Länge...weitersuchen
              begin
                k := 0; // wieder von vorn
                bMatch := False;
              end;
              Dec(i);
            end;
          end;
        end;
        FGoodTable[j] := iPLen - i;
        inc(j);
      end;

[Deep-Sea]

Zitat von Schorschi5566:

Delphi-Quellcode:

[...]
            if (Pattern[iPLen - k + 1] <> Pattern[i - k + 1]) then
              Goto NextTryFwd;
          end;
          Goto MatchedFwd;
NextTryFwd:
        end;
MatchedFwd:
        FGoodTable[j] := iPLen - i;
      end;
    end
[...]

Kommt mir bekannt vor:

Code:

[...]
                if (p[plen - k] != p[i - k]) {
                    goto nexttry;
                }
            }
            goto matched;
nexttry:
            ;
        }
matched:
        next[j] = plen - i;
    }
[...]

Quelle: Wikipedia