Chrome extension -- replace words on a page from a large dictionary

Question

This works, but is very very slow. Any recommendations on better, less trivial ways of accomplishing this would be appreciated. With a smaller dictionary it's fine, but the dictionary is about 80 different mappings. I also hardly ever work with JS so any input would be great. Obviously I have not included the dictionary.

var TEXTNODE = 3;

var elements = document.getElementsByTagName('*');

var wordMap = [
    [['word'], 'different word'],
    [['phrase'], 'something else'],
    [['one'], 'two'],

    /* etc for 80 lines */

];



function createRegularExpression(words)
{
    return new RegExp( '\\b(' + words.join('|') + ')s?\\b', 'gi');  
}

function replaceText(text)
{
    for (var ii = 0; ii < wordMap.length; ii++) 
    {
        var newText = text.replace(createRegularExpression(wordMap[ii][0]), wordMap[ii][1]);
        if (text != newText)
        {
            return newText;
        }
    }

return null;

}


for (var ii = 0; ii < elements.length; ii++) 
{
    var element = elements[ii];

    for (var jj = 0; jj < element.childNodes.length; jj++) 
    {
        var node = element.childNodes[jj];

        if (node.nodeType === TEXTNODE) 
        {
            var text = node.nodeValue;
            var lastText = text;
            var newText = text;;

            /* Have to keep looping because it will only replace the first occurence */

            while (newText != null) 
            {
                lastText = newText;
                newText = replaceText(lastText);
            }
            if (lastText != text)
            {
                element.replaceChild(document.createTextNode(lastText), node);
            }
        }
    }
}

---

UPDATE: Thanks to the awesome response I was able to rework this and it works lighting fast. I'll eventually look into that optimization. Thank you!!!!!!!! Updated code:

var wordMap = {
'word': 'new word',
'this is a phrase': 'new phrase',
'map this': 'to this'

//...
};

var regex = new RegExp('\\b(' + Object.keys(wordMap).join('|') + ')\\b', 'ig');

/* tree walker */
var treeWalker = document.createTreeWalker (
    document.body,
    NodeFilter.SHOW_TEXT,
    null,
    false
);

/* text nodes */
var textNodes = [];

while (treeWalker.nextNode())
{
    textNodes.push(treeWalker.currentNode);
}

/* iterate text nodes and modify in place */
for (var i = 0, len = textNodes.length; i < len; i++) 
{
    textNodes[i].nodeValue = textNodes[i].nodeValue.replace(regex, 
        function(match) 
        {
            var replacementWord = wordMap[match.toLowerCase()];

            /* match capitalization -- wordMap is all lowercase */

            if (match != match.toLowerCase())
            {
                if (match == match.toLowerCase().charAt(0).toUpperCase())
                {
                    replacementWord = replacementWord.charAt(0).toUpperCase() + replacementWord.slice(1);
                }
                else if (match == match.toUpperCase())
                {
                    replacementWord = replacementWord.toUpperCase();
                }
            }

            console.log('replacing ' + match + ' with ' + replacementWord);
            return replacementWord;
        }
    );
}

Answer 1

Your logic currently does a lot more work that it needs to do.

First, you are iterating every element in DOM and then iterating on every child element of those (which is actually duplicate work, since all nested tags would already be present in elements). This is especially problematic in that you are really only interested in text nodes. So, your first order of business, is to get only those nodes you care about.

Perhaps check out this Stack Overflow post on this topic. I personally like the TreeWalker approach in the accepted answer.

Now that you have a good flattened representation of these text nodes, you can just iterate through and directly modify them.

// build word map
var wordMap = {
   'match value': 'replace value',
   // etc.
}

// build single regex
var regex = new RegExp(Object.keys(wordMap).join("|"),"gi");

// get text nodes
var textNodes = ...; // derive similar to linked SO question above.

// iterate text nodes and modify in place
for (var i = 0, len = textNodes.length; i < len; i++) {
    textNodes[i].nodeValue = textNodes[i].nodeValue.replace(regex, function(match) {
        return wordMap[match];
    });
}

This example above would have you modifying the nodes in place rather than having to do any DOM replacements.

You could also potentially have some savings by dumping the regex approach to string search altogether in favor of simply iterating through the string a single character at a time comparing against key/property values in your word map, to see if any replacement strings are potentially starting or continuing. You would like need to build a trie structure to give efficient lookup against your dictionary. This is certainly more complex from an implementation standpoint, but could be an optimization you need to make if you find the regex approach is just not operating fast enough for you.

You might find this interesting reading on tries in javascript - http://ejohn.org/blog/javascript-trie-performance-analysis/