beste strategie für ein multiple string replace?

ich möchte in einem string verschiedene teilstrings durch andere ersetzen. dabei können längere suchmuster kürzere suchmusters beinhalten.
ist es dabei ratsam, längere suchmuster zu priorisieren?

mal ein beispiel ...
ich habe 'abcdef' und die ersetzungen 'ab->hello' und 'a->world'
ich suche also zuerst nach vorkommen von 'ab', weil 'ab' länger als 'a'
so bekomme ich 'hellocdef'.
würde ich zuerst nach 'a' suchen, bekäme ich 'worldbcdef', was bedeuten würde, dass ich das 'ab' niemals gefunden hätte.

wob

und wenn deine Ersetzungen sind 'ab->halloa' und 'a->world' sind, willst du dann 'abcdef' in "hworldlloworldcdef" umwandeln?

Du musst dir immer eine Reihenfolge überlegen. Oder du sagt, dass du im ersetzen String nicht nochmal ersetzt. Dann musst du aber auf jeden Fall irgendwie festlegen, was zuerst passieren soll.

=> Du musst also wissen, was du willst.

@wob sagte in beste strategie für ein multiple string replace?:

Du musst dir immer eine Reihenfolge überlegen. Oder du sagt, dass du im ersetzen String nicht nochmal ersetzt. Dann musst du aber auf jeden Fall irgendwie festlegen, was zuerst passieren soll.

wenn ich eine ersetzung anwende wird nicht das resultat der vorherigen ersetzung verwendet, sondern das was sie übrig gelassen hat.
nach obigem beispiel: a->world' sieht nicht 'hellocdef' sondern 'cedf',
nachdem 'ab->hello' zugeschlagen hat. aber trotzdem soll in 'cedf' zuerst nach 'ab' gesucht werden und erst danach nach 'a'. meine frage ist nun ob etwas dagegen spricht.

string beginnt mit der längsten kombination (lmax)?
wenn gefunden dann replacement an neuen string anhängen, source-string um lmax kürzen und weiter bei 1
string beginnt mit der zweitängsten kombi (lmax-1)?
wenn gefunden dann replacement an neuen string anhängen, source-string um lmax-1 kürzen und weiter bei 3
.............
... usw...
............
wenn keine kombination passt, dann nehme das zeichen selbst,
string um 1 kürzen und weiter bei 1 bis source-stringlänge==0 (alle zeichen abgearbeitet)

suchstring (key) und replacement (value) sind in einer treemap gespeichert, die dafür sorgt dass die längsten keys immer oben sind. suchstrings gleicher länge werden sequentiell abgearbeitet.

Jockelx

@Bushmaster

Wenn ich dich richtig verstehe, funktioniert das so nicht:

Keys: "aba"->"W", "ba"->"T"
Word: "xbaba"

liefert nach deinem Algorithmus (sofern ich das richtig verstehe):

"xTT" statt "xbW"

@Jockelx sagte in beste strategie für ein multiple string replace?:

Wenn ich dich richtig verstehe, funktioniert das so nicht:
Keys: "aba"->"W", "ba"->"T"
Word: "xbaba"
liefert nach deinem Algorithmus (sofern ich das richtig verstehe):
"xTT" statt "xbW"

ja, xTT, denn das zuerst gefundene 'ba' verhindert das finden von 'aba'
das ist nicht schön, oder?

hustbaer

Was spricht gegen die ganz naive Variante?

Du implementierst eine rekursive Funktion replace(str, patternIndex, patterns, replacements).

Diese sucht das erste Vorkommnis von patterns[patternIndex]. Wenn es gefunden wurde, dann ist das Ergebnis

replace(substringVorDemMatch, patternIndex + 1, patterns, replacements)
    + replacements[patternIndex]
    + replace(substringNachDemMatch, patternIndex, patterns, replacements)

Und wenn nichts gefunden wurde, dann ist das Ergebnis einfach

replace(str, patternIndex + 1, patterns, replacements)

Abbruchbedingung fehlt dann natürlich noch, die ist natürlich einfach wenn patternIndex >= patterns.size() dann ist das Ergebnis einfach str.

Das ganze kannst du dann noch schön umbauen so dass du keine Strings zurückgeben und konkatenieren musst - einfach einen Puffer (z.B. std::string oder std::vector<char>) als Parameter (by reference) übergeben wo die Funktion ihren Teil anhängt. Dadurch sollte die Sache ordentlich schneller werden.
Und den 2. rekursiven Aufruf kann man noch einfach wegmachen indem man den Teil in eine Schleife umwandelt. Was günstig wäre, weil andernfalls die Rekursionstiefe auf sehr direkte Art und Weise vom Input-String abhängig wäre. D.h. man könnte sehr einfach nen Stack-Overflow produzieren.

Jockelx

@Bushmaster sagte in beste strategie für ein multiple string replace?:

das ist nicht schön, oder?

Ist die Frage ernst gemeint?

@wob sagte in beste strategie für ein multiple string replace?:

=> Du musst also wissen, was du willst.

@Jockelx sagte in beste strategie für ein multiple string replace?:

@Bushmaster sagte in beste strategie für ein multiple string replace?:

das ist nicht schön, oder?

Ist die Frage ernst gemeint?

@wob sagte in beste strategie für ein multiple string replace?:

=> Du musst also wissen, was du willst.

doch, denn ich will die ersetzungen optimieren, daher ist die entscheidung zuerst nach den längsten mustern zu suchen offenbar falsch.

oder anders ausgedrückt: ist es besser in 'abcdef' ab, cd und ef zu finden, (3 ersetzungen) oder 'abc', was die ersetzung von 'cd' verhindert?

@hustbaer sagte in beste strategie für ein multiple string replace?:

Was spricht gegen die ganz naive Variante?

Du implementierst eine rekursive Funktion replace(str, patternIndex, patterns, replacements).

Diese sucht das erste Vorkommnis von patterns[patternIndex]. Wenn es gefunden wurde, dann ist das Ergebnis
replace(substringVorDemMatch, patternIndex + 1, patterns, replacements)
    + replacements[patternIndex]
    + replace(substringNachDemMatch, patternIndex, patterns, replacements)
Und wenn nichts gefunden wurde, dann ist das Ergebnis einfach
replace(str, patternIndex + 1, patterns, replacements)
Abbruchbedingung fehlt dann natürlich noch, die ist natürlich einfach wenn patternIndex >= patterns.size() dann ist das Ergebnis einfach str.

Das ganze kannst du dann noch schön umbauen so dass du keine Strings zurückgeben und konkatenieren musst - einfach einen Puffer (z.B. std::string oder std::vector<char>) als Parameter (by reference) übergeben wo die Funktion ihren Teil anhängt. Dadurch sollte die Sache ordentlich schneller werden.
Und den 2. rekursiven Aufruf kann man noch einfach wegmachen indem man den Teil in eine Schleife umwandelt. Was günstig wäre, weil andernfalls die Rekursionstiefe auf sehr direkte Art und Weise vom Input-String abhängig wäre. D.h. man könnte sehr einfach nen Stack-Overflow produzieren.

danke, aber wenn ich das richtig verstanden habe, finden folge-ersetzungen auf dem neu generierten string statt (rekursion). das soll ja gerade nicht sein.

wob

@Bushmaster sagte in beste strategie für ein multiple string replace?:

oder anders ausgedrückt: ist es besser in 'abcdef' ab, cd und ef zu finden, (3 ersetzungen) oder 'abc', was die ersetzung von 'cd' verhindert?

Ist das ernst gemeint? Wie soll man das beantworten? Das hängt doch davon ab, was du erreichen willst!

hustbaer

@Bushmaster
Nein, das hast du nicht richtig verstanden.

Keys:
	0: "aba"->"W"
	1: "ba"->"T"
	2: "bW"->"FAIL"
Word: "xbabay"

Aufruf: replace("xbabay", 0, keys, replacements). Das sucht jetzt erstmal nach keys[0], also "aba". Findet es an Offset 2.
->

return	replace(str.substr(0, 2), 1, keys, replacements) // substr(0, 2) = Substring vor dem Match = "xb"
	+ replacements[0] // replacements[0] = Replacement für den Match = "W"
	+ replace(str.substr(5), 0, keys, replacements); // substr(5) = Substring nach dem Match = "y"

Ein rekursiver Aufruf von replace bekommt also "xb" gefüttert und einer bekommt "y". D.h. da wird nicht nochmal was replaced da kein Match mehr gefunden wird. Ergebnis ist also "xbWy". "bW" wird nicht als Pattern erkannt und replaced, da der Teil vor einer Ersetzung, die Ersetzung selbst und der Teil nach der Ersetzung getrennt weiterverarbeitet werden. Und die Ersetzung selbst wird natürlich direkt 1:1 kopiert, darauf nochmal replace aufzurufen macht ja wenig Sinn.

hustbaer

@Bushmaster Welche Semantik/welches Regelwerk mehr Sinn macht musst schon du wissen, das ist ja wohl abhängig davon was du damit machen willst. Und wenn du das mal weisst, dann kann man sich überlegen wie man es möglichst elegant und/oder performant implementieren kann.

Oder suchst du bloss etwas was möglichst performant zu implementieren ist und kannst mit allen Regeln leben die sich "daraus ergeben, hauptsache schnell"?

Oder anders gesagt: du fragst was ist das beste? ... Erm... das beste wofür?

Th69

Ich frage mich hier auch, was der echte Anwendungsfall hierbei ist?
Nur ein theoretischer, sonst wären die Regeln für das Ersetzen doch sicherlich vorgegeben (bzw. bekannt)?

@Th69 sagte in beste strategie für ein multiple string replace?:

Ich frage mich hier auch, was der echte Anwendungsfall hierbei ist?
Nur ein theoretischer, sonst wären die Regeln für das Ersetzen doch sicherlich vorgegeben (bzw. bekannt)?

ja, es ist nichts vorgegeben. ich versuche die 'beste' multiple stringersetzung zu finden, wobei ich mir über 'beste' noch nicht im klaren bin.

vielleicht ist es gut, verschiedene algorithmen anzuwenden und dann zu entscheiden, welcher davon die meisten teilstrings gefunden hat, und welcher davon die meisten zeichen ersetzen konnte. beispiel:

gegeben ist: "abcdefgh"
ersetzungen: "bcdefg->T", "ab->S", "cd->U".

in einem fall könnte "aTgh" entstehen: 1 ersetzung, 6 Zeichen
im anderen fall: "SUefgh" 2 ersetzungen, 4 zeichen

was wäre besser? sollte man die anzahl der treffer maximieren, oder die anzahl ersetzter zeichen? oder gar die länge des endresultats?

hustbaer

@Bushmaster Wenn du keinen Anwendungsfall hast, dann ist es IMO total sinnfrei sich grossartig Gedanken darüber zu machen was denn das "beste" Regelwerk zum Ersetzen von mehreren Patterns/Substrings wäre.

Das ist irgendwie wie sich zu überlegen was denn das "beste" Instrument ist, wenn man nicht weiss welche Musik man damit machen möchte, wie viele Arme/Beine der Spieler hat und ob man überhaupt Musik mag.