Effizientes Ersetzen mehrerer Stringteile

Hallo,

wie kann ich in einem String mehrere Teilstrings durch andere ersetzen und zwar möglichst schnell?

wenn ich also einen String
„abcdefghijk“ habe und möchte „d“ durch „x“ und „g“ durch „y“ ersetzen ist es wohl nicht die beste Idee, den String zweimal zu durchlaufen, sondern direkt je nachdem beide Ersetzungen vorzunehmen.

Dies war jetzt ein primitives Beispiel, es geht mir um beliebige Strings (nicht nur einzelne Zeichen und viel grössere Mengen von Ersetzungsregeln… wenn ich z.b. 50 Ersetzungsregeln habe, will ich end 50mal nen Riesenstring von vorne bis hintern parsen.

Ausserdem muss ich dann 50 Strings erstellen bis ich den richtigen habe, ich will nur einmal einen String zusammenbasteln.

Weiss jemand ob es sowas gibt und wie das am besten gemacht wird? Ich programmiere in Java, aber ein Pseudocode oder Prosabeschreibung würden mir auch reichen

MfG Bruno

Hi Bruno,

wenn ich also einen String
„abcdefghijk“ habe und möchte „d“ durch „x“ und „g“ durch „y“
ersetzen ist es wohl nicht die beste Idee, den String zweimal
zu durchlaufen, sondern direkt je nachdem beide Ersetzungen
vorzunehmen.

weiß nicht, ob Du das als effizient erachtest, aber Du könntest es ja mal so versuchen:

Array neu(1..26) ' enthält die neuen Buchstaben,
 ' etwa neu(1)="e", wenn "a" durch "e" ersetzt
 ' werden soll
For i=1 to len(string)
 string[i]=neu(asc(string[i])-64)
next

Damit wird jeder Buchstabe durch den neuen ersetzt. Buchstaben, die bleiben sollen, müssen durch sich selbst ersetzt werden, etwa neu(2)=„b“. Alternativ kannst Du auch

For i=1 to len(string)
 a = asc(string[i])-64
 if neu(a) !="" then string[i]=neu(a)
next

verwenden und die nicht zu ersetzenden Buchstaben im Array „neu“ leer lassen.

Anm.: string[i] soll hier das i-te Zeichen aus string bedeuten und asc(„x“) liefert den ASCII-Code des Zeichens x, also asc(„A“) = 65, asc(„a“) = 97. Wenn Du zwischen Groß- und Kleinschreibung unterscheiden willst, brauchst Du evtl. zwei Arrays oder entsprechend ein größer dimensioniertes.

Hoffe, das hilft Dir, wenn die obige Erklärung zu knapp war, frag nochmal nach!
Gruß
Sculpture

Ergänzung
Hallo Bruno,

nur eine Ergänzung, du sprachst von Teilstrings, da funktioniert das vorher gepostete nicht so ganz.

Bei Teilstrings wäre es IMHO am optimalsten getrennt nach den Teilstrings zu suchen, und zwar mit Textmustererkennungsalgorithmen wie Knutz-Morris-Pratt und Boyer-Moore (nein, das wußte ich nicht auswendig wie die heißen, hab nachschauen müssen :o).

Die sind zwar nicht einfach (zumindest hat mein beschränkter Geist etwas länger gebraucht um die zu kapieren), aber effizient. Grundprinzip ist, dass du nicht wie bei einer naiven Suche einfach Zeichen für Zeichen vorgehst sondern aus Informationen die du aus der Zeichenkette hast bestimmst wie weit du nach vorne springen kannst.

Einfaches Beispiel
Text: pewritagjsöaldfkgskd
Suche nach: pewald

Du vergleichst ab dem ersten Zeichen, beim dritten Zeichen kommst du drauf, dass die Strings nicht übereinstimmen:

pewritagjspewaldfkgskd
pewald
 X

Anhand der Tatsache, dass die ersten drei Zeichen im Text pew sind weißt du, dass dort dein neuer Text nicht mehr beginnen kann, ist ja kein p drinnen, also springst du:

pewritagjspewaldfkgskd
 pewald

Das war jetzt stark vereinfacht, wie man es halt im Kopf machen würde, für den Computer gibts die genannten Algorithmen. :smile:

Mehr Informationen findest du sicher zuhauf im Internet, falls du nichts findest kann ich auch Details posten. Hab das aber nur einmal gelernt, eine Prüfung darüber abgelegt und nachher nie wieder gebraucht. :o)

Eventuell gibt es Versionen der obigen Algorithmen die auch effizienter mit mehreren Textstrings umgehen können, beim Versuch sich sowas auszudenken kriege ich aber einen Knoten im Hirn.

Grüße, Robert

Danke.

Aber Boyer-Moore ist mir aus der Informatik Vorlesung bekannt… darum gehts mir auch nicht. Ich denke bestehnde Funktionen wie z.b. String.indexOf() in Java werden das schon nach irgendso nem Prinzip machen…

mir gehts eher darum, wenn ich ned nur eins ersetzten möchte z.B. 1000 Ersetzungsregeln habe, dann nicht 1000Mal den String neu anfassen muss.

ich dachte evtl. lässt sich da irgendwie ein Baum zusammenbauen aus allen Regeln oder so, anhand dessen jeweils beim Durchlaufen erkannt wird ob ein Muster vorliegt und dieses dann zu ersetzen und zwar alle auf einmal und nicht nacheinander…

Aber ich glaube so gross is das Geschwindgeiktsproblem doch nicht dass ich mich noch mehr damit beschäftigen muss :smile:

Ausserdem fällt mir grad auf, dass mein Ansatz Schwächen hat, wenn Ersetzungsmuster, Teile von anderen Ersetzungsmustern sind… bei nachfolgender Ersetzung ist die Reihenfolge definiert, aber bei mir wäre nicht klar, was genau nun ersetzt werden soll

ich dachte evtl. lässt sich da irgendwie ein Baum
zusammenbauen aus allen Regeln oder so, anhand dessen jeweils
beim Durchlaufen erkannt wird ob ein Muster vorliegt und
dieses dann zu ersetzen und zwar alle auf einmal und nicht
nacheinander…

Ja, ich habe mir das auch gedacht, aber ich denke auf jeden Fall bleibt sich gleich ob du:

for( alle muster )
{
 for( durch den text durch )
 {
 compare
 }
}

oder

for( durch den text durch )
{
 for( alle muster )
 {
 compare
 }
}

machst.

D. h., wenn du wirklich einen Performancegewinn möchtest, dann brauchst du einen Algorithmus der nach dem Muster der beiden genannten Algorithmen für jedes Pattern speichert wo beim Mismatch nicht nur dieses Pattern sondern auch alle anderen Pattern angelegt werden können. Außerdem einen der noch dazu eine Reihenfolge festlegt in welcher Reihenfolge die Pattern am optimalsten angelegt werde können um große Sprünge zu garantieren.

Trotz Knoten im Hirn, mit ein bißchen Überlegungsaufwand könnte man sowas schon entwickeln, nur einerseits erhöht das bei der Ausführung den Vorbereitungsaufwand vor der eigentlichen Suche, d. h. es zahlt sich nur für längere Texte aus und andererseits erhöht es auch den Aufwand während der eigentlichen Suche, d. h. es sollten auch längere Pattern sein bzw. größere Sprünge, damit du wirklich effektiv Nutzen daraus ziehst.

Allerdings wäre es gar nicht so uninteressant sowas auszuprobieren. :o)

Grüße, Robert

Hallo Bruno

Ich habe mal so ein Programm geschrieben. Also eine Suchen-Ersetzen Funktion, wobei allerdings mehrere Begriffe durch jeweilige ersetzt werden.
Ist es das was du suchst?
Haben die zu ersetzenden Strings alle die gleiche Länge?
Wie gross sind denn die Dateien um die es da geht?

Ganz einfach ist die Sache nicht!!!

Muß allerdings dann noch in meinen alten Programmen wühlen, um es zu finden.

Wenn ich was habe melde ich mich

Tommy

wie kann ich in einem String mehrere Teilstrings durch andere
ersetzen und zwar möglichst schnell?

MfG Bruno

Haben die zu ersetzenden Strings alle die gleiche Länge?

Nein.

Wie gross sind denn die Dateien um die es da geht?

Weiss ich gerade nicht… ist flexibel

Mach dir keinen Stress, falls du es nicth auf ANhieb findest, so wichtig ist es nicht…

Danke
bruno

Hi,

denke mal der Verwaltungsaufwand für das Verwalten der
„Regeln“ ist zu hoch. Du mußt ja bei jedem Zeichen, daß
Du gerade vergleichst für jede Regel ein Flag mitpflegen,
ob das entsprechende Wort noch in Frage kommt oder nicht und
daß bis zum letzten Zeichen des längsten Suchwortes!

Du kannst natürlich ein Array anlegen und dir die bereits
ersetzten Stellen im Text merken um sie nachher nicht erneut
zu durchsuchen.

Die angesprochenen Verfahren mit dem Buchstaben überspringen
beim Suchen kannst Du eh nur anwenden, wenn Du nach einem
Wort suchst. Bei zwei zu ersetzenden Wörtern mußt Du ja
wieder eine Liste führen.

Wenn Du nur Wörter ersetzt ist es auch möglich, sich in einem
Vordurchlauf (oder eben beim ersten Durchlauf) die Position
von allen nicht-alphanumerischen Positionen zu merken und beim
Vergleich darauf zu achten, daß der Abstand zwischen aktueller
Buchstabe zur nächsten Nichtbuchstabenmarke größer gleich der
Länge des gesuchten Wort ist. Wenn der kleiner ist, kannst Du
ja getrost hinter die nächste Marke springen.

Vielleicht kannst Du hiermit was anfangen.

Alex

„Effizient“ hängt natürlich voin vielem ab.
Willst du z.B. denselben Satz von 50 Ersetzungsregeln
täglich auf verschiedene Daten im Gigabyte-Bereich anwenden,
lohnen sich definitiv ein paar aufwendigere Gedanken über die Regeln vorab.

Idee 1:
Wenn die ersten n Zeichen des Textes gelesen sind,
gibt es am Ende einen „best match“ im Sinne von:
Die letzten k Zeichen (der ersten n Zeichen!!) stimmen
mit den ersten k Zeichen des Strings Nummer m überein.
Es kann zu gegebenem n mehrere Paare (m,k) geben, da mehrere
Strings teilweise pasen [bzw. (m,0) geht auch, wenn gar nix paßt].
Wir betrachten immer nur solche mit maximalem k (und ggf.
unter diesen minimales m). Auf diese Weise wird jeder
Textposition n ein Zustand (m,k) zugeordnet.
Wir haben dadurch so um die Summe(strlen) möglich Zustände.
Der Zustand an der Stelle n+1 hängt nur vom Zeichen c an der
Stelle n+1 ab und vom vorherigen Zustand.

Und zwar wird aus (m,k)

  • der Zustand (m,k+1), falls c == m[k+1]
  • für die meisten anderen Zeichen der Zustand (0,0)
  • für ein paar andere Zeichen c jedoch gewisse andere (m’,k’)
    („paar andere“ = höchstens Anzahl Suchstring viele)

Ist man irgendwann bei (m,strlen(m)) angelangt,
so hat man Such-String m gefunden, kann ihn durch
Ersetzungs-String m ersetzen und mit (0,0) weitermachen.
[Ich gehe davon aus, daß einmal ersetzter Text nicht als
match zu einem neuen Suchstring gelten darf]

Beispiel:
S1 = „suchtexteins“
S2 = „textsuchezwei“
Text = „dies ist ein suchtextstueck“

Nach „dies ist ein suchte“
befinden wir uns im Zustand (S1,6).
Jetzt kommt ein ‚x‘ => (S1,7)
Dann ein ‚t‘ => (S1,8)
Die Nachfolger von (S1,8) in Abhängigkeit vom folgenden
Zeichen c sind jedoch:
(S1,9), falls c==S1[9] // i.e. c==‚e‘
(S2,5), falls c==‚s‘ (weil die ersten 4 von S2 die letzten 4 von S1 sind)
(0,0) in allen anderen Fällen.
Im Beispiel folgt ein ‚s‘, daher folgt Zustand (S2,5)
Dann folgt ‚t‘ => (S2,1)
Dann ‚u‘ => (NULL,0)
usw.

Das Nachschlagen des nächsten Zustands kann man realisieren
am einfachsten (und zugriffschnellsten und speicherintensivsten)
als eine Tabelle[Zustand][char].
Platzsparender als eine Tabelle[Zustand] von structs
mit Zeigern auf a) einen String mit den „speziellen“ Zeichen,
die nicht auf (0,0) führen und b) einem Zeiger auf ein ebensolanges Array von Zuständen [plus Information, ob
ein kompletter Match erreicht wurde].
Im Beispiel wäre der String spezeiller Zeichen für (S1,8)
der String „es“, das zug. Zustandsarray {(S1,9),(S2,5)}
[statt (S1,9) usw. wird man am wahrscheinlichsten char-Pointer
verwenden oder gar direkt einen Pointer in das so konstruierte Array].
Vorgehensweise wäre dann inetwa:

c = getch();
i = IndexOf(c,aktuellerZustand->spezialZeichen);
if (i==0) {
aktuellerZustand = AnfangsZustand;
} else {
aktuellerZustand = aktuellerZustand->NachfolgeZustand[i];
}
// hier fehlt noch: Erkennen von vollständigen Matches und
// tatsächliches Ersetzen.

Diese Datenstruktur tatsächlich aufzubauen, überlasse ich
deinem eigenen Spieltrieb :wink:

Allerdings gibt es in dieser einfachen Form noch ein Problem wenn Suchstrings komplett als Teil eines anderen Suchstrings auftreten.
Beispiel:
Search1 = „absdefghijklm“; Replace1 = „alpha“;
Search2 = „def“; Replace2 = „beta“;
Search3 = „hi“; Replace3 = „gamma“;
Search4 = „fghij“ Replace4 = „delta“;
Text = „abcdefghijkxxxx“
Nach dem ‚k‘ sind wir in Zustand (S1,11) und hoffen
auf ein Match mit S1. Da jedoch kein ‚l‘ kommt, war die
Hoffnung vergebens. Statt jetzt bei (0,0) anzufangen,
müssen wir wieder ein paar Zeichen zurück und die schon
fast vergessenen „def“ und „hi“ (nicht jedoch „fghij“)nachträglich durch den zug. Replacement-Text ersetzen.
Diese Situation hängt natürlich von den Suchstrings ab.
Umgehen kann man dies, indem man in solchen Fällen
zusätzliche Strings in die Zustandstabelle miteinbezieht.
Hier:
Search5 = „defg“ Replace5 = „betag“
Search6 = „defgh“ Replace6 = „betagh“
Search7 = „defghi“ Replace7 = „betaggamma“
Search8 = „defghij“ Replace8 = „betaggammaj“
Search9 = „defghijk“ Replace9 = „betaggammajk“
Search10= „defghijkl“ Replace10=„betaggammajkl“
Search11 = „fghijk“ Replace11=„deltak“
Search12 = „fghijkl“ Replace12=„deltakl“

Du siehst, daß dies ärgerlich wird, wenn ein kleiner String
recht früh in einem längeren auftaucht…

Dafür ist aber die ablaufende Programmschleife recht flott.
Außerdem braucht man den zu durchsuchenden Text nicht im Speicher zu halten: Man kann zeichenweise einlesen und
zeichenweise ausgeben, indem man

  • die ersten (k’-k+1) Zeichen von String m ausgibt, wenn man
    von Zustand (m,k) auf (m’,k’) weitergeht
  • falls hierbei (m’,k’) = (NULL,0), so gebe man zusätzlich
    das gerade eingelesene Zeichen c aus.
    [Ausnahme: bei einem erfolgreichen Match gebe man Ersatzstring m aus und wechsele zum Zustand (NULL,0), ohne das Zeichen c auszugeben]
    Bei Erreichen des Dateiendes gebe man schließlich noch
    die ersten k Zeichen von String m aus.
    Auch hier gilt: Details werden dem geneigten Leser überlassen :wink:

Idee 2:
Mit Hashes.
Folgende C-Zeilen

unsigned long accu = 0;
while ((c=gethc())!=EOF) {
accu = (accu