What is the most efficient way to replace a list of words without touching html attributes?

Question

I absolutely disagree that this question is a duplicate! I am asking for an efficiency way to replace hundreds of words at once. This is an algorithm question! All the provided links are about to replace one word. Should I repeat that expensive operation hundreds of times? I'm sure that there are better ways as a suffix tree where I sort out html while building that tree. I removed that regex tag since for no good reason you are focusing on that part.

---

I want to translate a given set of words (more then 100) and translate them. My first idea was to use a simple regular expression that works better then expected. As sample:

const input = "I like strawberry cheese cake with apple juice"
const en2de = {
    apple: "Apfel",
    strawberry: "Erdbeere",
    banana: "Banane",
    /* ... */}
input.replace(new RegExp(Object.keys(en2de).join("|"), "gi"), match => en2de[match.toLowerCase()])

This works fine on the first view. However it become strange if you words which contains each other like "pineapple" that would return "pineApfel" which is totally nonsense. So I was thinking about checking word boundaries and similar things. While playing around I created this test case:

<a href="https://www.apple.com">Apple</a> is a company

That created the output:

<a href="https://www.Apfel.com">Apfel</a> is a company.

The translation is wrong, which is somehow tolerable, but the link is broken. That must not happen.

So I was thinking about extend the regex to check if there is a quote before. I know well that html parsing with regex is a bad idea, but I thought that this should work anyway. In the end I gave up and was looking for solutions of other devs and found on Stack Overflow a couple of questions, all without answers, so it seems to be a hard problem (or my search skills are bad).

So I went two steps back and was thinking to implement that myself with a parser or something like that. However since I have multiple inputs and I need to ignore the case I was thinking what the best way is.

Right now I think to build a dictionary with pointers to the position of the words. I would store the dict in lower case so that should be fast, I could also skip all words with the wrong prefix etc to get my matches. In the end I would replace the words from the end to the beginning to avoid breaking the indices. But is that way efficiency? Is there a better way to achieve that?

While my sample is in JavaScript the solution must not be in JS as long the solution doesn't include dozens of dependencies which cannot be translated easy to JS.

TL;DR:

I want to replace multiple words by other words in a case insensitive way without breaking html.

Answer 1

You may try a treeWalker and replace the text inplace.

To find words you may tokenize your text, lower case your words and map them.

const mapText = (dic, s) => {
  return s.replace(/[a-zA-Z-_]+/g, w => {
    return dic[w.toLowerCase()] || w
  })
}
const dic = {
  'grodzi': 'grodzila',
  'laaaa': 'forever',
}
const treeWalker = document.createTreeWalker(
  document.body,
  NodeFilter.SHOW_TEXT
)

// skip body node
let currentNode = treeWalker.nextNode()
while(currentNode) {
  const newS = mapText(dic, currentNode.data)
  currentNode.data = newS
  currentNode = treeWalker.nextNode()
}

p {background:#eeeeee;}

<p>
  <a href="grodzi">grodzi</a>
  <a href="laaaa">LAAAA</a>
</p>

The link stay untouched.

However mapping each word in an other language is bound to fail (be it missing representation of some word, humour/irony, or simply grammar construct). For this matter (which is a hard problem on its own) you may rely on some tools to translate data for you (neural networks, api(s), ...)

Answer 2

Here is my current work in progress solution of a suffix tree (or at least how I interpreted it). I'm building a dictionary with all words, which are not inside of a tag, with their position. After sorting the dict I replace them all. This works for me without handling html at all.

function suffixTree(input) {
    const dict = new Map()
    let start = 0
    let insideTag = false
    // define word borders
    const borders = ' .,<"\'(){}\r\n\t'.split('')
    // build dictionary
    for (let end = 0; end <= input.length; end++) {
        const c = input[end]
        if (c === '<') insideTag = true
        if (c === '>') {
            insideTag = false
            start = end + 1
            continue
        }
        if (insideTag && c !== '<') continue
        if (borders.indexOf(c) >= 0) {
            if(start !== end) {
                const word = input.substring(start, end).toLowerCase()
                const entry = dict.get(word) || []
                // save the word and its position in an array so when the word is
                // used multiple times that we can use this list
                entry.push([start, end])
                dict.set(word, entry)
            }
            start = end + 1
        }
    }
    // last word handling
    const word = input.substring(start).toLowerCase()
    const entry = dict.get(word) || []
    entry.push([start, input.length])
    dict.set(word, entry)

    // create a list of replace operations, we would break the
    // indices if we do that directly
    const words = Object.keys(en2de)
    const replacements = []
    words.forEach(word => {
        (dict.get(word) || []).forEach(match => {
            // [0] is start, [1] is end, [2] is the replacement
            replacements.push([match[0], match[1], en2de[word]])
        })
    })
    // converting the input to a char array and replacing the found ranges.
    // beginning from the end and replace the ranges with the replacement
    let output = [...input]
    replacements.sort((a, b) => b[0] - a[0])
    replacements.forEach(match => {
        output.splice(match[0], match[1] - match[0], match[2])
    })
    return output.join('')
}

Feel free to leave a comment how this can be improved.