Gleichzeitiges ersetzen mehrerer Strings

[werdas34]

Hallo,
ich haben ein String text der alles sein kann. Filenamen, Filecontent etc.

Nun möchte ich mehrere Strings in diesem text ersetzen. Soweit kein Problem.
einfach text.replace("a", "b").replace("c","d");

Ich habe nur das Problem das ein Substring das ersetzt wird vom anderen wiederum erkannt wird und falsch ersetzt wrid. Kleines Beispiel.
Torte -> Kirschtorte
torte -> kirschtorte

Das führt dazu das aus Torte -> Kirschkirschtorte wird, da zuerst der text nach Torte sucht und durch Kirschtorte ersetzt und dann torte durch kirschtorte in Kirschtorte ersetzen möchte und dann Kirschkirschtorte daraus wird.

Ne Idee wäre das ich den text zeichenweise durchgehe und bei einem match den String austausche. Quasi sliding window.
Nur haben die Strings unterschiedliche Längen. Heißt wenn ein String 2 Zeichen lang ist und einer 5 dann muss ich ich alle möglichen Kombination aus 2er und 5er Substrings überprüfen müsste

Gib es einen Weg mehrere replace-Strings unterschiedlicher Länge zu ersetzen und dabei den text nur einmal zu durchlaufen, um sowas wie oben zu vermeiden? Oder eine optimierte Variante von sliding window?

 

[KonradN]

Du hast generell mehrere Möglichkeiten:

a) manchmal hast Du die Möglichkeit, es über die Reihenfolge zu klären. Wenn Du also erst "torte" ersetzt und dann "Torte", dann reagiert das zweite Ersetzen nicht auf das Ersetzte vom ersten. Das ist also eine Art Sonderfall, bei dem Du keine Probleme hast.

b) Eine Idee ist, dass Du erst Dinge zu etwas ersetzt, die nicht vorkommen können. Du ersetzt also erst:
Torte -> ##1##
torte -> ##2##
Dann kannst Du
##1## -> Kirschtorte
##2## -> kirschtorte
ersetzen.
Damit hast zwar die doppelte Anzahl an Ersetzungen, aber es kommt nicht zu der Reaktion auf Elemente, die erst eingefügt wurden.

c) Wenn Du es als Code machst, dann kannst Du es natürlich selbst ersten. Dann gehst Du den String Zeichen für Zeichen durch und fügst das dann ein. Der Algorithmus könnte also etwas sein wie:
So lange pos < MaxIndex String

• fängt an pos ein zu ersetzender String an? Dann füge an das Ergebnis das zu ersetzende an und pos wird um die Länge des zu ersetzenden Strings erhöht.
• wenn nicht, dann füge das aktuelle Zeichen an das Ergebnis an und erhöhe pos um 1.

Damit hättest Du einen Algorithmus, der die Ersetzung macht ohne dass es zu doppelten Ersetzungen kommen kann.

Das wären 3 einfache Ideen, die das Problem lösen könnten und die mir so auf Anhieb direkt einfallen. Es gibt bestimmt noch deutlich mehr Möglichkeiten, aber ich hoffe, dass diese Ideen erst einmal reichen.

 

[werdas34]

Danke für deine Antwort.

a) hängt von der Reihenfolge der Wörter in text ab. Und das kann sehr unterschiedlich sein. Daher wird das nicht ausreichen.

b) Wäre ne interessante Idee, aber man müsste sehr viele Platzhalter verwenden bei vielen ähnlichen Substrings..

c) Ist der von mir angesprochene sliding window Ansatz. Meine Befürchtung ist das es recht lange dauern kann. Bei einem text von 1000 Zeichen und einem Substring der Länge 4, müsste ich wenn ich richtig liege 997 Vergleiche machen.
Könnte man das irgendwie optimieren?

 

[KonradN]

Also A) geht so du eine Reihenfolge basteln kannst, dass alle Nachfolger nicht auf den Replacement Text eines Vorgängers reagiert.

Zu B) das ist nicht wirklich ein Problem. Wenn man sich das etwas überlegt. Es reicht ja, dass man in den Replacement Text zusätzliche Zeichen platziert, die nicht kommen können. Also z.B. \u0000. Damit würden Nachfolgende Replace nicht mehr ansprechen und am Ende entfernt man nur alle \u0000 …. So als kleine Variante.

Zu C) die genauen Anforderungen sind wichtig sowie die Länge der zu suchenden Texte. Wenn die Anzahl der Ersetzungen gering ist, dann hast du eine kleine Anzahl Anfangsbuchstaben und kannst vermutlich relativ zügig durch einen Text gehen mit wenig String Vergleichen.

Generell gilt aber auch: Bau es erst einmal möglichst einfach. Wenn es dann nicht performant genug ist, dann kannst du optimieren. Oder dir bessere Algorithmen überlegen.

 

[Oneixee5]

Du kannst auch Satzzeichen mit einbeziehen. Also z.B.: Anfang der Datei/Zeile, Ende der Datei/Zeile, Lehrzeichen, Komma, Punkt, etc. Das hört sich erst mal kompliziert an, aber dafür gibt es Zeichengruppen.
Wenn du nach " torte" suchst, dann wird Kirschtorte nicht gefunden.
Ein Marker dafür wäre evtl.: \b

abc = abc.replaceAll("\\btorte\\b", "Kirschtorte");

boundary matchers:​

Boundary Construct	Description
^	The beginning of a line
$	The end of a line
\b	A word boundary
\B	A non-word boundary
\A	The beginning of the input
\G	The end of the previous match
\Z	The end of the input but for the final terminator, if any
\z	The end of the input

 

[KonradN]

Wichtig ist, dass man hier halt die Anforderungen genau analysiert und ggf. spezifiziert. Bezüglich des Beispiels bedeutet dies: Was soll aus "Apfeltorte" werden? Soll das "Apfelkirschtorte"? Oder noch besser: Was ist, wenn es bereits eine "Kirschtorte" ist? Soll das eine Kirschkirschtorte werden?
Ebenso die Frage, was mit einem "Tortenheber" ist? Wird das ein "Kirschtortenheber"?

Da Torte ein Substantiv ist, deutet das Ersetzen von torte darauf hin, dass auch Wortbestandteile ersetzt werden soll.

Aber das ist ein wichtiger Punkt, wenn man so Ersetzungen mit regulären Ausdrücken machen möchte und je nach Anforderungen wird dies dann auch recht schwer umzusetzen.

 

[httpdigest]

By the way: Wenn es hier nicht um die Interpretation von "Was ist eigentlich ein Wort?" bzw. "wie ersetze ich Wörter durch andere Wörter?" im Kontext von natürlichen Sprachen geht (wo @KonradN ja sehr richtig aufführt, dass es wie immer auf die korrekte Formulierung der Anforderungen ankommt), sondern wirklich einfach nur um das Ersetzen von beliebigen Substrings durch andere Substrings in einem längeren String mit Berücksichtigung von den im initialen Post angesprochenen möglichen Fehlern durch Ersetzungen der Ersetzungen, dann gibt es als sehr laufzeiteffiziente Lösung den Aho-Corasick Algorithmus.

Diese Seite beschreibt den sehr gut: https://cp-algorithms.com/string/aho_corasick.html

Dieser hat dann bei Gesamtlänge M aller Ersetzungen bei einem Gesamttext der Länge N nicht Laufzeitkomplexität O(N*M), sondern nur O(M+N+k), wobei 'k' hier die Anzahl der im Gesamttext tatsächlich gefundenen Vorkommen ist.

 

[httpdigest]

Ein weiterer Fall, der aber auch hiermit schwierig wird, ist, wenn es zwei Ersetzungen A -> B und A' -> B' gibt, wobei A ein Präfix von A' ist.
Also z.B. "ab" -> "cd" und "abc" -> "xy".
Hier muss man dann auch entscheiden, was man haben möchte: z.B. "der längste Match gewinnt und nur dieser wird ersetzt".
Also der Text "abcd" wird dann zu "xyd" und nicht zu "cdcd".