Re^3: effizientes Ersetzen mehrerer Stringteile

"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

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

--------

Idee 2:
Mit Hashes.
Folgende C-Zeilen

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