AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Boyer-Moore für Unicode

Ein Thema von Schorschi5566 · begonnen am 13. Jun 2011 · letzter Beitrag vom 16. Jun 2011
Antwort Antwort
Seite 3 von 3     123
Benutzerbild von Deep-Sea
Deep-Sea

Registriert seit: 17. Jan 2007
907 Beiträge
 
Delphi XE2 Professional
 
#21

AW: Boyer-Moore für Unicode

  Alt 15. Jun 2011, 09:58
Na das ist dann natürlich sinnlos. Deine Aussage klang halt nur so allgemein
Chris
Die Erfahrung ist ein strenger Schulmeister: Sie prüft uns, bevor sie uns lehrt.
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
43.014 Beiträge
 
Delphi 12 Athens
 
#22

AW: Boyer-Moore für Unicode

  Alt 15. Jun 2011, 10:21
ganz dringend: Delphioptionen > Indexprüfung aktivieren

Ich bin mir ganz relativ sehr sicher, daß das nötig sein wird, da dur ganz bestimmt ein paar nette Indexfehler (Buffer Overrun) verbaut hast.

PS: Die letzen zwei Schleifen lassen sich zu einer vereinen, so daß Exit und Goto überflüssig werden.
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
my Delphi wish list : BugReports/FeatureRequests
  Mit Zitat antworten Zitat
Schorschi5566

Registriert seit: 6. Feb 2006
197 Beiträge
 
Delphi 10.2 Tokyo Enterprise
 
#23

AW: Boyer-Moore für Unicode

  Alt 15. Jun 2011, 11:15
Hallo Himitsu,

bin mir gerade nicht sicher ob wir von der selben Codestelle reden. NextStep war ja in der Hauptschleife.

Kann man natürlich ohne Goto machen, aber so wie es da steht, würde ich sagen stimmt es und da hilft auch kein Continue. Aber ich verwende Continue eigentlich nie. Continue setzt doch die aktuelle Schleife fort ohne den Rest der Schleife zu durchlaufen, oder? Wäre in dem Fall also die innere Schleife, was falsch wäre. An den Anfang der äußeren Schleife zu springen wäre auch falsch weil dann die Schleifenbedingung nicht abgefragt würde.

Ist aber alles Makulatur, weil ich ja auch das letzte Goto entfernt habe.

Alte Version:
Delphi-Quellcode:
 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;
Aktuelle Version:
Delphi-Quellcode:
  while (Offset <= iTLen) and (OffSet >= 0) do
  begin
    pcPattern := @Pattern[iOffKorr];
    pcText := @Text[Offset];
    j := 0; // Anzahl der Übereinstimmungen
    while (j < iPLen) and (pcText^ = pcPattern^) do
    begin
      dec(pcPattern, iDir);
      dec(pcText, iDir);
      inc(j)
    end;
    if j < iPLen then
    begin
      iBadSkip := FBadTable[Ord(pcText^)] + iPLen - j;
      if iBadSkip > FGoodTable[j] then
      begin
        inc(Offset, iBadSkip * iDir);
      end
      else
      begin
        inc(Offset, FGoodTable[j] * iDir);
      end;
    end
    else
      Exit(Offset - iOffKorr + 1);
  end;
Uwe
"Real programmers can write assembly code in any language." - Larry Wall
Delphi programming rocks
  Mit Zitat antworten Zitat
Schorschi5566

Registriert seit: 6. Feb 2006
197 Beiträge
 
Delphi 10.2 Tokyo Enterprise
 
#24

AW: Boyer-Moore für Unicode

  Alt 16. Jun 2011, 09:02
Hier nochmal die aktuelle Unit. Danke für eure Tipps.

Die Wikipedia-C-Version hatte auch noch andere Fehler.

Neue Version Boyer-Moore für Unicode:
- statisches Array für Bad-Table
- Goto-frei
- Charpointer statt indizierter Zugriff auf Pattern und Text
- $STRINGCHECKS OFF

Wer die Good-Table weglassen möchte, muss im Suchteil eine Abfrage auf iBadSkip < 1 machen und dann um 1 skippen. Je nach Suchmuster (wenige bis keine Suffixe) ist die Suche dann nochmal schneller.
iBadSkip < 1 kann vorkommen, wenn es Teilmatches gibt und der aktuelle nicht gematchte Char aus Text im Teilmatch vorkommt (negativer Offset). Mit Goodtable ist das egal weil die in so einem Fall zuschlägt. Ohne Goodtable und entsprechende Abfrage, hängt die Suche in diesem Fall.


Grüße,
Uwe

Delphi-Quellcode:
unit BoyerMoore;

{$STRINGCHECKS OFF}

interface

uses
  SysUtils;

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

  TBoyerMoore = class
  strict private
    FPattern : String;
    FPatternLen : Integer;
    FDir : TDirection;
    FBadTable : array[0..65535] of Integer; // Größe entspricht gewünschtem Alphabet
    FGoodTable : array of Integer;
  public
    function PosBM(const Pattern, Text: String; Offset : Integer = 1; const Dir : TDirection = dForward): Integer; register;
  end;

implementation

{ TBoyerMoore }

// *************
// P o s B M
// *************
//
// Boyer-Moore Stringsuche
//
// Eingabe:
// --------
// Pattern: Suchtext
// Text: Text, der durchsucht wird.
// 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, iTLen, iOffCorr, iBadSkip : Integer;
  bMatch : Boolean;
  pcPattern, pcSuffix, pcPattFirst, pcText : PChar;
begin
  Result := 0;
  iTLen := Length(Text);
  iDir := Ord(Dir);

  // Good- und Bad-Table nur neu erzeugen, wenn neues Suchmuster verwendet wird
  // oder die Suchrichtung wechselt.
  if (FPattern <> Pattern) or (FDir <> Dir) then
  begin
    // Bad-Table der letzten Suche wieder auf 0 setzen
    pcPattern := PChar(Pointer(FPattern)); // Pattern der vorhergehenden Suche
    pcPattFirst := pcPattern;
    while pcPattern - pcPattFirst < FPatternLen do
    begin
      FBadTable[Ord(pcPattern^)] := 0;
      Inc(pcPattern);
    end;

    FPatternLen := Length(Pattern); // neue Patternlänge merken

    SetLength(FGoodTable, FPatternLen);

    // Sprungtabellen abhängig von der Suchrichtung erzeugen
    case Dir of
      dForward:
      begin
        // Bad-Character-Table vorwärts
        pcPattern := PChar(Pointer(Pattern));
        i := 1;
        while i <= FPatternLen do
        begin
          FBadTable[Ord(pcPattern^)] := - i; // FPatternLen später addieren
          Inc(pcPattern);
          Inc(i);
        end;

        // Good-Suffix-Table vorwärts
        j := 1;
        i := FPatternLen - 1; // Initialisierung für Good-Table vorwärts
        k := 0;
        bMatch := False;
        while j < FPatternLen do
        begin
          while (i > 0) and (k < j) do
          begin
            if (i - k > 0) then
            begin
              pcPattern := @Pattern[FPatternLen - k];
              pcSuffix := @Pattern[i - k];
              while (k < j) and (i - k > 0) and (pcPattern^ = pcSuffix^) do
              begin
                bMatch := True;
                inc(pcPattern);
                inc(pcSuffix);
                inc(k);
              end;
            end;
            if (k < j) then // kein ganzes Suffix gefunden
            begin
              if (i - k <= 0) then // Ende erreicht, Rest mit MaxSkip füllen
                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] := FPatternLen - i;
          inc(j);
        end;
      end;
      dBackward:
      begin
        // Bad-Character-Table rückwärts
        pcPattern := @Pattern[FPatternLen];
        i := FPatternLen;
        while i > 0 do
        begin
          FBadTable[Ord(pcPattern^)] := i - 1 - FPatternLen; // FPatternLen später wieder addieren
          Dec(pcPattern);
          Dec(i);
        end;

        // Good-Suffix-Table rückwärts
        j := 1;
        i := 1; // Initialisierung für Good-Table rückwärts
        k := 1;
        bMatch := False;
        while j < FPatternLen do
        begin
          while (i < FPatternLen) and (k - 1 < j) do
          begin
            if (i + k < FPatternLen) then
            begin
              pcPattern := @Pattern[k];
              pcSuffix := @Pattern[i + k];
              while (k - 1 < j) and (i + k < FPatternLen) and (pcPattern^ = pcSuffix^) do
              begin
                bMatch := True;
                inc(pcPattern);
                inc(pcSuffix);
                inc(k);
              end;
            end;
            if (k - 1 < j) then // kein ganzes Suffix gefunden
            begin
              if i + k > FPatternLen then // Ende erreicht, Rest mit MaxSkip füllen
                i := FPatternLen // Maximal-Skip
              else
              begin
                if bMatch then // kein Match mit dieser Länge...weitersuchen
                begin
                  k := 1; // wieder von vorn
                  bMatch := False;
                end;
                Inc(i);
              end;
            end;
          end;
          FGoodTable[j] := i;
          inc(j);
        end;
      end;
    end;

    FPattern := Pattern; // Pattern merken
    FDir := Dir; // Richtung merken
  end;

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

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

  // Pattern in Text suchen
  while (Offset <= iTLen) and (OffSet > 0) do
  begin
    pcPattern := @Pattern[iOffCorr];
    pcText := @Text[Offset];
    j := 0; // Anzahl der Übereinstimmungen
    while (j < FPatternLen) and (pcText^ = pcPattern^) do
    begin
      dec(pcPattern, iDir);
      dec(pcText, iDir);
      inc(j);
    end;
    if j < FPatternLen then // Mismatch
    begin
      iBadSkip := FBadTable[Ord(pcText^)] + FPatternLen - j;
      if iBadSkip > FGoodTable[j] then
      begin
        inc(Offset, iBadSkip * iDir);
      end
      else
      begin
        inc(Offset, FGoodTable[j] * iDir);
      end;
    end
    else // Match
      Exit(Offset - iOffCorr + 1);
  end;
end;

end.
Uwe
"Real programmers can write assembly code in any language." - Larry Wall
Delphi programming rocks

Geändert von Schorschi5566 (16. Jun 2011 um 11:01 Uhr) Grund: Vorschläge von Andreas eingebaut.
  Mit Zitat antworten Zitat
jbg

Registriert seit: 12. Jun 2002
3.479 Beiträge
 
Delphi 10.1 Berlin Professional
 
#25

AW: Boyer-Moore für Unicode

  Alt 16. Jun 2011, 09:52
Wenn du jetzt noch aus @str[1] ein PChar(str) machst, dann entfällt der UniqueString Aufruf, den der Compiler einstreut. Und wenn du auch noch den PCharFromUStr loswerden willst, dann kannst du PChar(Pointer(str)) machen (der PChar cast ist zwar nicht notwendig, da Pointer zuweisungskompatibel ist, aber ich schreib den zur Lesbarkeit immer hin)
Dabei musst du aber beachten, dass ein Leerstring dann "nil" und nicht #0 liefert.

Übrigens ist dein statisches FBadTable Array um eins zu groß. In Ord(WideChar) passen nur 0..65535. Nicht 65536.

Geändert von jbg (16. Jun 2011 um 09:57 Uhr)
  Mit Zitat antworten Zitat
Schorschi5566

Registriert seit: 6. Feb 2006
197 Beiträge
 
Delphi 10.2 Tokyo Enterprise
 
#26

AW: Boyer-Moore für Unicode

  Alt 16. Jun 2011, 11:02
Danke, hab's direkt oben eingebaut.

Die Good-Table dürfte auch eins zu groß sein, weil bei GoodTable[FPattLen] ein Vollmatch vorliegt. Mache ich später noch...muss aber los.
Uwe
"Real programmers can write assembly code in any language." - Larry Wall
Delphi programming rocks

Geändert von Schorschi5566 (16. Jun 2011 um 11:05 Uhr)
  Mit Zitat antworten Zitat
jbg

Registriert seit: 12. Jun 2002
3.479 Beiträge
 
Delphi 10.1 Berlin Professional
 
#27

AW: Boyer-Moore für Unicode

  Alt 16. Jun 2011, 13:13
Danke, hab's direkt oben eingebaut.
Gerade die Performance-technisch unwichtigste Stelle hast zu geändert. Die anderen @Pattern[1] in den Schleifen hast du aber stehen lassen.
  Mit Zitat antworten Zitat
Schorschi5566

Registriert seit: 6. Feb 2006
197 Beiträge
 
Delphi 10.2 Tokyo Enterprise
 
#28

AW: Boyer-Moore für Unicode

  Alt 16. Jun 2011, 18:33
Echt? Habe im Code genau 2x "[1]" gefunden und da habe ich es ersetzt.

[EDIT]Wenn du die Stelle meinst:
Delphi-Quellcode:
    pcPattern := @Pattern[iOffCorr];
    pcText := @Text[Offset];
da habe ich auch so keine Calls mehr drin und 'ne Änderung auf PCHar(Pointer(Text/Pattern)) + Offset bringt 'ne Verschlechterung der Laufzeit.
[/EDIT]
Uwe
"Real programmers can write assembly code in any language." - Larry Wall
Delphi programming rocks

Geändert von Schorschi5566 (16. Jun 2011 um 22:28 Uhr)
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 15:08 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz