Is there an elegant algorithm for applying multiple simultaneous search-and-replace operations to a string?

Question

The operation I'm interested in is a slight twist on your standard search-and-replace operation, in that instead of a single pair of arguments (replaceme and withme), it takes a keyed set of N [before, after] pairs as an argument, and for each pair in the set, replaces all instances of <before> in the string with <after>.

For example, if we have this initial string:

three point one four one five

... and our set of [before, after] pairs looks like this:

[one, two]
[two, three]
[three, four]
[four, five]
[five, six]

... then after the operation completed, our updated string would be:

four point two five two six

The intuitive (but wrong) way to implement this would be to just iterate over the set and do a traditional search-and-replace for each pair in series. That works for cases where the values in the set are unrelated, but it fails in other cases (such as our example above) because the later iterations inappropriately operate on the results of the earlier operations. So doing it that way yields an incorrect result like this:

six point six six six six

My question is, there any well-known algorithm for handling this operation efficiently? I was able to come up with an algorithm that seems to accomplish it, but I suspect there might be a better way to do it than my hackish approach.

Answer 1

In principle: Starting with position I=0, check if one of your original strings is stored at position I. If not, increase i by 1. If yes, replace the string and set I = I + length of replacement. Note that an empty string as original string cannot be allowed.

To optimise: Make a table with the starting characters, look from position I until you find one of the starting characters, reducing the number of long comparisons.

Answer 2

You can build an Aho-Corasick automata for the before words, run your string through it, and whenever you find a match go back in the string and replace it with the after value, and then reset the automata. This takes linear time (in the length of both the input and output).

Answer 3

Well yeah, the Trie algorithm is a well-known technique for effectively performing this task. This technique can efficiently conduct numerous search-and-replace operations in a single pass over the input text, avoiding the problems that occur when the operations are performed in succession.

The temporal complexity of this approach is O(n + k), where n is the length of the input string and k is the total length of all 'before' strings. This is significantly quicker than doing the operations sequentially, which has a temporal complexity of O(n*k).

and also there are several Trie algorithm implementations available in many programming languages, thus it should be very simple to implement in your unique use case.

Answer 4

Store original: replacement in a map. Make an empty output string. Run through the string and word by word find new word using map and concatenate with output. return output.