Suchen von Zeichenfolgen ab einer Position

[Kay]

Hallo,

ich würde gern eine Zeichenfolge nach einer anderen Zeichenfolge durchsuchen und das Vorkommen zurückgeben lassen.
Allerdings möchte ich ab einer bestimmten Position mit der Suche beginnen oder auch in umgekehrter Richtung, also vom Ende her suchen.

Code: Alles auswählen

IndexOf(3, 'lazarus', 'a');  // =4
LastIndexOf(3, 'lazarus', 'a');  // =2

Mit UTF8Pos habe ich das nicht hinbekommen und andere Funktionen hab ich in der LCL nicht gefunden.

Ich könnte die Funktionen zwar selbst erstellen, aber das Einzige was mir dazu einfällt wäre folgende Implementierung:

Code: Alles auswählen

function IndexOf(const Start: Integer; const S, SubStr: String): Integer;
var
  I, Len, SubLen: Integer;
begin
  Result := 0;
  Len := UTF8Length(S);
  SubLen := UTF8Length(SubStr);
 
  for I := Start to Len - SubLen + 1 do
  begin
    if UTF8Copy(S, I, SubLen) = SubStr then
    begin
      Result := I;
      Break;
    end;
  end;
end;

Das würde zwar prinzipiell funktionieren, ist aber bei längeren Zeichenfolgen (z.B. ganzen Texten) extrem ineffizient.
Daher meine Frage: Gibt es eine Implementierung, mit deren Hilfe ich die genannten Aufgaben schnell und effektiv erledigen kann? Existiert dazu eventuell eine gesonderte Bibliothek mit erweiterten Zeichenkettenfunktionen?

Vielen Dank schonmal

[theo]

Es gibt
Function PosEx(const SubStr, S: string; Offset: Cardinal): Integer;
in unit strutils.

Das Resultat kann man mit UTF8Length korrigieren.

[Kay]

Hallo theo,

erstmal vielen Dank für deine Antwort.
Ich hab mir die Funktion mal angeschaut und ich bin mir zwar nicht ganz sicher, aber kann es sein, dass das Suchmuster hier auch nur zeichenweise im Text verschoben wird um dann das Matching mit dem jeweiligen Ausschnitt vorzunehmen? Dann wäre der Algorithmus bei einem Text, der ca. 1.000.000 Zeichen umfasst, auch nicht gerade effizient oder täusche ich mich?
Dann könnte ich theoretisch auch meinen Vorschlag weiter ausbauen, von der Laufzeit her wird sich das nichts nehmen und ich bräuchte keine UTF8Length-Korrektur vornehmen?

VG, Kay

[theo]

Weiss nicht genau was du meinst, aber PosEx ist bestimmt schneller als kopieren.
Mach doch eine Messung.

[Kay]

Also was ich meine ist, dass PosEx meiner Meinung nach auch nur naiv sucht.

Wikipedia schreibt dazu:
"Der einfachste Algorithmus besteht darin, ein so genanntes Suchfenster von der Länge der Suchmaske über den Text zu schieben. In jeder Position der Suchmaske werden die Symbole der Maske mit denen des darunterliegenden Textes verglichen. Wenn ein nichtübereinstimmendes Symbol gefunden wird, wird das Fenster um eine Position verschoben, und erneut ein Vergleich angestellt; wenn alle Symbole im Fenster übereinstimmen, ist die Suchmaske gefunden worden. Der Algorithmus endet, wenn der ganze Text vom Fenster abgesucht worden ist."

Ich dachte eher an etwas effizienteres, aber wahrscheinlich müsste ich da selbst was bauen. Ist letztendlich auch kein Weltuntergang, aber ich wollte halt nicht unbedingt das Rad neu erfinden. Wenn es also bereits eine entsprechende Implementierung gäbe, würde ich diese natürlich lieber nutzen.

[theo]

Du hast Probleme...

In Wikipedia steht weiter: "Überraschenderweise ist der naive Ansatz in der Praxis sehr schnell, da Fehler in natürlichsprachigen Texten nach 1 bis 2 Zeichen auftauchen. Für die englische Sprache ergibt sich eine Wahrscheinlichkeit von 1.07 Zeichen. Somit ist der naive Ansatz nahezu linear schnell."

[Kay]

Dass der naive Ansatz in der Praxis schneller sein soll, bezweifel ich ganz stark.
Ich habe nämlich deinen Rat befolgt und eine Zeitmessung vorgenommen.
Ich habe dazu eine Textdatei eingelesen. Die Zeichenfolge mit dem Inhalt umfasst knapp 10 Mio. Zeichen, was von UTF8Length auch korrekt zurückgegeben wird. Das zu findende Wort befindet sich im letzten Drittel, also ungefähr bei Position 7 Mio.
Die von mir oben gepostete Funktion entspricht ja der einfachen Suche und da musste ich nach 10 Minuten abbrechen - also soviel dazu.
Bei PosEx konnte ich bisher keinen Wert messen, da die Funktion 0 zurückgibt, wenn entweder im Text oder im Such-String Umlaute enthalten sind. Scheint also nicht nur ein Problem der unterschiedlichen Längen zu sein.
Von daher verstehe ich nicht ganz, warum du schreibst, dass ich Probleme hätte, nur weil ich nach einer effizienten Lösung suche...

[mschnell]

Allerdings möchte ich ab einer bestimmten Position mit der Suche beginnen oder auch in umgekehrter Richtung, also vom Ende her suchen.

Das geht nicht.

In Unicode codierten Strings, gibt es keine "bestimmte Position", da in Unicode nicht definiert ist, wann ein inkrementieren der "Zeichenposition" stattfinden soll.

-Michael

[theo]

Von daher verstehe ich nicht ganz, warum du schreibst, dass ich Probleme hätte, nur weil ich nach einer effizienten Lösung suche...

Weil du nicht weisst, was du da tust. UTF8Copy ist fürchterlich langsam, und um einen String zu durchsuchen gänzlich ungeeignet.
Da hilft dir deine Theorie kein Stück weiter. Deshalb mein Einwand, erst einmal die vorhandenen Methoden sinnvoll auszutesten, bevor du neue theoretische Ansätze bemühst.

Das ist, als ob du mit 4 platten Reifen fährst, und damit es wieder schneller geht vorschlägst einen Ferrari Motor einzubauen.

Bei PosEx konnte ich bisher keinen Wert messen, da die Funktion 0 zurückgibt, wenn entweder im Text oder im Such-String Umlaute enthalten sind. Scheint also nicht nur ein Problem der unterschiedlichen Längen zu sein.

Bei mir nicht.

Code: Alles auswählen

var a,b:String;
begin
 a:='asfasdfäääasdfdasfääasdfsdaf';
 b:='äasd';
 ShowMessage(inttostr(PosEx(b,a,4)));
end;
 

[Kay]

Sorry, dein Beispiel ist sicherlich gut gemeint, aber hast du das auch bei großen Datenmengen getestet? Ich sprach ja nicht vom Strings mit 10 Zeichen.
Wenn du also feststellen möchtest, ob das mit PosEx funktioniert, dann müsstest du das schon richtig nachvollziehen. Alles andere ist kein Beleg.

[theo]

Sorry, dein Beispiel ist sicherlich gut gemeint, aber hast du das auch bei großen Datenmengen getestet? Ich sprach ja nicht vom Strings mit 10 Zeichen.
Wenn du also feststellen möchtest, ob das mit PosEx funktioniert, dann müsstest du das schon richtig nachvollziehen. Alles andere ist kein Beleg.

Nein, habe ich nicht. Du sagtest, dass es nicht geht "wenn entweder im Text oder im Such-String Umlaute enthalten sind ".
Das kann ich nicht bestätigen und ich wüsste auch nicht, warum sich das mit der Datenmenge ändern soll, so lange du die Grenzen der verwendeten Datentypen nicht überschreitest.

Poste doch mal ein Beispiel, bei dem es nicht geht.

[Michl]

Habe das eben an einem über 10MB großen String (mit Umlauten, Suchstring ziemlich am Ende) getestet. Dies funktioniert problemlos und schnell (mit gettickcount nicht messbar in einem Suchvorgang).

Bei PosEx konnte ich bisher keinen Wert messen, da die Funktion 0 zurückgibt, wenn entweder im Text oder im Such-String Umlaute enthalten sind. Scheint also nicht nur ein Problem der unterschiedlichen Längen zu sein.

Wichtig zu erwähnen wäre es, dass bei PosEx(SuchString, String, Position) die Position immer > 0 sein muss, da sonst immer 0 als Ergebnis zurückgeliefert wird!!!

[mschnell]

Das ist, als ob du mit 4 platten Reifen fährst, und damit es wieder schneller geht vorschlägst einen Ferrari Motor einzubauen.

Der Vergleich Unicode <-> 4 platte Reifen hätte von mir sein können

-Michael

[Kay]

Allerdings möchte ich ab einer bestimmten Position mit der Suche beginnen oder auch in umgekehrter Richtung, also vom Ende her suchen.

Das geht nicht.

In Unicode codierten Strings, gibt es keine "bestimmte Position", da in Unicode nicht definiert ist, wann ein inkrementieren der "Zeichenposition" stattfinden soll.

Ich weiß, aufgrund der variablen Länge der Unicode-Zeichen wird das wohl etwas heikel werden. Gehen muss es aber, da ja auch Editoren das bei UTF8-kodiertem Text hinbekommen.

VG, Kay

[theo]

In Unicode codierten Strings, gibt es keine "bestimmte Position", da in Unicode nicht definiert ist, wann ein inkrementieren der "Zeichenposition" stattfinden soll.

Stimmt nicht, es ist nur nicht vom Byteindex her zu adressieren (ausser bei normalisiertem UTF32). Sequentiell ist es natürlich möglich, was dennn sonst?

Was einen auf den Schluss bringt, dass das "Suchen von Hinten" bezüglich der Performance bei UTF-8 meistens nicht vorteilhaft ist.

Man muss sich aber erst fragen, ob der "Buchstabenindex" überhaupt benötigt wird, oder ob der Byteindex nicht ausreicht.