Entwickler-Ecke

Delphi Language (Object-Pascal) / CLX - Exaktes Vorkommen eines Strings in einem anderen


galagher - So 16.09.12 19:50
Titel: Exaktes Vorkommen eines Strings in einem anderen
Hallo!

Wie kann ich herausfinden, ob (und wie oft) ein Teilstring innerhalb eines Strings nicht nur vorkommt, sondern, ob und wie oft er auch in einer bestimmten Länge darin vorkommt?

Also zB., wie oft 'Test' im String 'Das ist ein Test zum Testen des Vorkommens eines Teilstrings' vorkommt. Die Funktion Pos würde mir hier 2 liefern, ich suche aber exakt das Wort 'Test', ich brauche eine Lösung, die mir 1 liefert, denn 'Test' ist hier genau nur 1x enthalten, 'Testen' ist ein anderes Wort!

Also so etwas wie:

Delphi-Quelltext
1:
if PosLen(sSubString, sString) > 1 then                    


Jann1k - So 16.09.12 20:47

Du könntest ja nach 'Test ' suchen lassen, problematisch wirds, wenn Satzzeichen dazukommen (wenn man nicht auch 'Test,', 'Test.' etc. suchen will. Ich würde bei jedem Ergebnis, das dir von pos geliefert wird, überprüfen ob an der Stelle nach dem Wort, kein Buchstabe steht, dann erst zählt der Fund.


HeftCD - So 16.09.12 20:50

dann mußte Du den String mit einer Schleife durchgehen.

evtl. z.B:


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
Vorkommen := 0; i := 0
while i < Length(ZeilesString)-1  do
begin
inc(i);
A := pos(ZeilesString, Suchstring)
if A <> 0 then
   begin
      inc (Vorkommen);
      ZeilesString := copy(ZeilesSting,i+length(Suchstring),Length(ZeilesSting));
   end;
end;


kurz ohne IDE geschnipselt


Delete - Mo 17.09.12 15:55


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
{*****************************************************************************************************************************************
 *** LIEFERT DIE ANZAHL DES VORKOMMENS VON SUCHWORT IN ZEILE ZURÜCK                                                                    ***
 *****************************************************************************************************************************************}

FUNCTION  StringCount(Zeile, Suchwort : String; Exakt : Boolean) : Integer;

CONST
     Zeich : Set of Char = [' ''.'';'':'',''!''?'')''"''/''#','%','+','-','*','\',']','}'];

VAR
   z, p, L : Integer;
   EFund,
   Fund    : Boolean;
   W       : Char;

BEGIN
     L      := Length(Suchwort);
     Result := 0;
     Fund   := TRUE;

     WHILE Fund DO
     BEGIN
          p    := POS(Suchwort,Zeile);
          Fund := p > 0;
          IF Fund THEN INC(Result);

          IF Fund THEN
          BEGIN
               Delete(Zeile, 1, p+L-1);

               IF Exakt THEN
               BEGIN
                    W    := Zeile[1];
                    EFund := W in Zeich;
                    IF NOT EFund THEN DEC(Result);
               END;
          END;
     END;
END;


galagher - Di 18.09.12 21:02

Hallo!

Vielen Dank für eure Antworten :) , aber ich komme im Moment nicht dazu, mir das näher anzusehen!


Narses - Di 18.09.12 22:21

Moin!

user profile iconPerlsau hat folgendes geschrieben Zum zitierten Posting springen:

Delphi-Quelltext
1:
2:
3:
FUNCTION  StringCount(Zeile, Suchwort : String; Exakt : Boolean) : Integer;
//...
               Delete(Zeile, 1, p+L-1);
:? Vielleicht solltest du erwähnen, dass sich dein Vorschlag nur für sehr kurze Strings eignet, da du unnötigerweise den zu durchsuchenden String kopierst und dann auch noch per Delete bearbeitest, was den Heap zumüllt. :nixweiss:

Der Standard für eine halbwegs effiziente Suche sollte wohl Boyer-Moore [http://de.wikipedia.org/wiki/Boyer-Moore-Algorithmus] sein. :les: :think:

cu
Narses


Delete - Di 18.09.12 22:29

user profile iconNarses hat folgendes geschrieben Zum zitierten Posting springen:
Moin!
Vielleicht solltest du erwähnen, dass sich dein Vorschlag nur für sehr kurze Strings eignet, da du unnötigerweise den zu durchsuchenden String kopierst und dann auch noch per Delete bearbeitest, was den Heap zumüllt.


Wieso nur für sehr kurze Strings? Kann ich nicht nachvollziehen.

Wo kopiere ich deiner Ansicht nach den zu durchsuchenden String?

Was meinst du mit "Heap zumüllen"? Welche Gefahren siehst du durch die Bearbeitung des zu durchsuchenden Strings via Delete?

user profile iconNarses hat folgendes geschrieben Zum zitierten Posting springen:
Der Standard für eine halbwegs effiziente Suche sollte wohl Boyer-Moore [http://de.wikipedia.org/wiki/Boyer-Moore-Algorithmus] sein.


Ist das nicht ein wenig zu aufwendig und umständlich?


Narses - Di 18.09.12 23:25

Moin!

user profile iconPerlsau hat folgendes geschrieben Zum zitierten Posting springen:
Wo kopiere ich deiner Ansicht nach den zu durchsuchenden String?
Hier:
user profile iconPerlsau hat folgendes geschrieben Zum zitierten Posting springen:

Delphi-Quelltext
1:
FUNCTION  StringCount(Zeile, Suchwort : String; Exakt : Boolean) : Integer;                    
da du nicht das Schlüsselwort const verwendet hast, wird ein call-by-value gemacht und die Strings dafür kopiert.

user profile iconPerlsau hat folgendes geschrieben Zum zitierten Posting springen:
Was meinst du mit "Heap zumüllen"? Welche Gefahren siehst du durch die Bearbeitung des zu durchsuchenden Strings via Delete?
Delete() verändert den String (nicht den originalen, sondern die "Arbeitskopie" (=lokale Variable) in der Funktion). Dafür muss der String erneut auf dem Heap angelegt werden, nur eben ohne den entfernten Teil! :idea: Es wird also Heap-Speicher in Anspruch genommen, der gar nicht gebraucht würde. Wenn du einen langen String ("Heuhaufen") und viele Treffer ("Nadeln") hast, dann wird der String sehr oft durch Delete() verändert und deshalb wird der Heap unnötig stark in Anspruch genommen. :think:

user profile iconPerlsau hat folgendes geschrieben Zum zitierten Posting springen:
user profile iconNarses hat folgendes geschrieben Zum zitierten Posting springen:
Der Standard für eine halbwegs effiziente Suche sollte wohl Boyer-Moore [http://de.wikipedia.org/wiki/Boyer-Moore-Algorithmus] sein.

Ist das nicht ein wenig zu aufwendig und umständlich?
Für kleine Heuhaufen und wenige Nadeln mag das zutreffen - wie ich schon schrieb. Mach das aber mal mit einem sagen wir 100MB großen Heuhaufen, in dem mehrere Tausend Nadeln drin sind. Und dann vergleich mal die Laufzeit von deinem Ansatz mit dem von Boyer-Moore. :zwinker:

Um in deiner Terminologie zu bleiben: dein Ansatz ist nicht "gefährlich" im Sinne von "nicht funktionsfähig", sondern unnötig langsam und speicherfressend. :nixweiss:

cu
Narses


Delete - Mi 19.09.12 00:05

@Narses: Das begreife ich heute abend wohl nicht mehr ... natürlich stimme ich deinen Argumenten zu, aber ich kann's im Moment wohl nicht besser. Ich kann auch kein C, so daß mir das Programmierbeispiel bei Wikipedia nicht weiterhilft. Aber ich bleibe dran, denn eine ordentlich funktionierende Suchfunktion für lange Texte braucht man immer wieder mal ...


Gausi - Mi 19.09.12 09:43

Wenn man in dem Heuhaufen nur kleine Nadeln sucht (sowas wie "Nadel"), dann bringt Boyer-Moore auch noch nicht fuchtbar viel. Der geht nur dann richtig ab, wenn man längere Dinge sucht. ;-) Wobei natürlich das Delete wirklich eine Bremse ist.

Da gibts aber auch was für Delphi, ich hab da mal was vorbereitet [http://gausi.de/studium.html]. :mrgreen: Ein paar Boyer-Moore-Varianten sind auch dabei.


Nersgatt - Mi 19.09.12 09:47

user profile iconGausi hat folgendes geschrieben Zum zitierten Posting springen:
Da gibts aber auch was für Delphi, ich hab da mal was vorbereitet [http://gausi.de/studium.html]. :mrgreen: Ein paar Boyer-Moore-Varianten sind auch dabei.

Der Zug ist für dieses Jahr natürlich abgefahren, aber willst Du nicht mal auf den Delphitagen einen Vortrag darüber halten? Das fände ich durchaus interessant und ich denke, das Thema eignet sich gut dafür.


jaenicke - Mi 19.09.12 11:14

Um mal ein kleines Beispiel zu bringen wie der gepostete Quelltext zumindest etwas besser aussieht (von den durch die Kürze unlesbaren weil nichtssagenden Variablennamen mal abgesehen):

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
function StringCount(const Zeile, Suchwort: Stringconst Exakt : Boolean): Integer;
const
  Zeich: set of Char = [' ''.'';'':'',''!''?'')''"''/''#','%','+','-','*','\',']','}'];
var
  z, p, L: Integer;
  EFund, Fund: Boolean;
  W: Char;
  CurrentRow: PChar;
begin
  L := Length(Suchwort);
  Result := 0;
  Fund := True;
  CurrentRow := PChar(Zeile);

  while Fund do
  begin
    p := Pos(Suchwort, CurrentRow);
    Fund := p > 0;
    if Fund then
      Inc(Result);

    if Fund then
    begin
      Inc(CurrentRow, p + L - 1);

      if Exakt then
      begin
        W := CurrentRow[0];
        EFund := W in Zeich;
        if not EFund then
          Dec(Result);
      end;
    end;
  end;
end;


galagher - Mi 19.09.12 18:12

user profile iconjaenicke hat folgendes geschrieben Zum zitierten Posting springen:
Um mal ein kleines Beispiel zu bringen wie der gepostete Quelltext zumindest etwas besser aussieht (von den durch die Kürze unlesbaren weil nichtssagenden Variablennamen mal abgesehen):function StringCount(const Zeile, Suchwort: Stringconst Exakt : Boolean): Integer;

Mit der Version von user profile iconjaenicke klappt es, vorher hatte ich Zugriffsfehler-Meldungen. Die Dauer ist für meine Zwecke erstmal egal, ich brauche es für mein Projekt, um maximal ein paar KB (meist viel weniger) an Text zu durchsuchen.

Ja, das const hätte ich noch eingebaut! Ich benutze das, wo immer möglich.
Danke!


jaenicke - Do 20.09.12 08:28

user profile icongalagher hat folgendes geschrieben Zum zitierten Posting springen:
vorher hatte ich Zugriffsfehler-Meldungen
Das dürfte daran liegen, dass nach dem Weitergehen um soundso viele Zeichen auf das erste Zeichen in CurrentRow zugegriffen wird ohne zu prüfen, ob das Stringende schon erreicht ist. Die Prüfung fehlt auch bei mir, ich wollte nur den Code als Beispiel umstellen (const, Pointer statt Stringoperationen, die unsägliche Turbo Pascal Formatierung weg, ...).


ml-kuen - Do 20.09.12 15:37

So weit mir bekannt ist, sind für derartige Aufgaben Reguläre Ausdrücke das Mittel der Wahl. Du selbst hast auch schon einmal einen Beitrag dazu gepostet. Eine Komponente gibts zB. hier: http://regexpstudio.com/DE/TRegExpr/Help/About.html

Michael


Narses - Do 20.09.12 16:08

Moin!

user profile iconml-kuen hat folgendes geschrieben Zum zitierten Posting springen:
So weit mir bekannt ist, sind für derartige Aufgaben Reguläre Ausdrücke das Mittel der Wahl.
Wenn ich nach Mustern suchen wollte, könnte man darüber nachdenken. :nixweiss: Wenn es aber um konstante (Teil-)Strings geht, würde ich das aus Performance-Gründen bei großen Datenmengen überhaupt nicht empfehlen. :schmoll: ;)

cu
Narses


thepaine91 - Do 20.09.12 19:16

Ich hätte das ganze über "Regular Expression" gelöst. Allerdings muss ich nach kurzer Recherche dazu sagen, das Delphi anscheinend bis "Delphi XE" keine Regex Implementation mitgeliefert hat und somit nur über externe Bibliotheken verwendet werden konnte. Somit ist dieser Ansatz wohl abhängig von deiner Delphi Version.


jaenicke - Do 20.09.12 21:42

Davon abgesehen hat ja user profile iconNarses schon geschrieben wie langsam das ist. Das ist bei dem Funktionsumfang ja auch kein Wunder, macht es aber für einfache Suchen wenig sinnvoll. Ich habe an der Stelle dann auch wieder auf simple Stringoperationen und einen Parser zurückgegriffen nachdem der Editor, in dem nur ein Teil des Highlighting darüber laufen sollte, zu langsam wurde...