While working on the C++ version of scalp, I had to do massive simple transformations of a given text, ie. replacements of words by others.

Since the main way to do this (a loop which does a replacement at the time), is very inefficient, I decided to find something faster. I then came up with a tree based replacement algorithm; I believe this is kinda famous but I never heard about such algorithm, it basically uses a non compact trie in order to have an efficient search of the current word.

The main algorithm is very simple and similar to a state machine where the state depends on the next character in the trie. For example, if we want to to replace the words: "ba", "me", "mp" in a text, the trie will be this following one:

The idea is then to iterate over all the characters in the text, and for each letter determines whether this is a possible word to replace or not (simply by looking if the letter is a child of the trie root). Then, we iterate over the next letters in the text in order to see if the sequence of letters are an actual word to replace or not (every time, the same methodology is used: look in the children at the current state of our iterator in the trie).

This algorithm seems more efficient than the simple replace used in a loop since we will perform a descent in a tree and therefore replace a linear search by a logarithm one.

I ran a little statistical comparison between two algorithms: mine and the simple loop one. The test bed is quite simple and uses randomly generated text which contains the words to replace with a certain density. In order to create statistics, I made all the sizes varying and I aggregated the results from the same dictionary size. So, for a given size of a dictionary (let's say, 200 words to replace), a text has been generated with a density that vary from 0.1 to 0.5 (from 10% to 50% of the words in the text will be words to replace) and finally, the size of the text vary from 25 to 200 words (and words are randomly generated to be from a size 5 to 32).
As I said previously, the results from a same dictionary size has been aggregated since I've seen practically that the result mainly depends on the dictionnary size (it also obviously depends on the size of the text, but as this is a constant for the 2 algorithm, I can compute the mean of the different data to extract the average gain for a particular dictionary size).

Finally, here is the curve that shows the logarithm progress of the gain compared to the classical method):

The reference replace implementation which has been compared to the one I developed is the following (STL/C++ implementation):

void str_replace(string& where, const string& what, const string& by) {
  for (string::size_type i  = where.find(what);
                                 i != string::npos;
                                 i  = where.find(what, i + by.size()))
    where.replace(i, what.size(), by);
}

and has been used M times (M is the size of the dictionary).
I also decided to release a very-early version of this replace algorithm (which is not template yet): stree.h which use the great STL friendly tree structure from Kasper Peeters.

As for data information, the here is the code I used to generate the dictionary, and text with a certain density: genRandData.cpp