Replace string based on multiple rules, don't replace same section twice

Question

Given a 2-column CSV dictionary file that contains translation of certain words, this c# code needs to replace the first occurrence of a word in the dictionary.

• Once a segment of string has been replaced, it cannot be matched or overwritten by a new dictionary word.

This sounded like a fairly simple task but the code I came up with runs horribly slow and I'm looking for ways to improve it.

All the offending code is in the TestReplace function, I build up a hashset that keeps track of what character Ids in the string have been touched. When you apply a rule that changes the lenght of the string, all the character ids switch around so they have to be recalculated and I believe it costs a lot of performance. Wish there was a simpler way to do this !

Here is a super simple case of what the code tries to do :

Dictionary file:

hello >>> hi

hi >>> goodbye

Input: hello, world!

First rule is applied so string becomes -> hi, world. The word hi is now locked.

Second rule is applied but the string does not become goodbye, world since this part is locked.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace stringReplacer
{
    class Program
    {
        public static Dictionary<string, string> ReplacementRules = new Dictionary<string, string>()
        {
            {"John","Freddy" },
            {"John walks","Freddy runs" },
            {"brown dog","gray dog" },
            {"dog","cat" },
            {"- not -", "(not)" },
            {"(","" },
            {")","" },
            {"whenever",  "sometimes, when"},
            {"raining", "snowing" },
            {"his", "many" }
        };

        static void Main(string[] args)
        {
            string Input = "John walks his brown dog whenever it's - not - raining";
            string ExpectedOutput = "Freddy walks many gray dog sometimes, when it's (not) snowing";

            string TestReplaceOutput = TestReplace(Input, ReplacementRules);
            ValidateReplacement("TestReplace", TestReplaceOutput, ExpectedOutput);
        }
        public static string TestReplace(string input, Dictionary<string, string> ReplacementRules)
        {
            HashSet<int> LockedStringSegment = new HashSet<int>();

            foreach (var rule in ReplacementRules)
            {
                string from = Regex.Escape(rule.Key);
                string to = rule.Value;
                var match = Regex.Match(input, from);
                if (match.Success)
                {
                    List<int> AffectedCharacterPositions = Enumerable.Range(match.Index, match.Length).ToList();

                    if (!AffectedCharacterPositions.Any(x => LockedStringSegment.Contains(x)))
                    {
                        input = Regex.Replace(input, from, to);
                        int LengthDelta = to.Length - rule.Key.Length;

                        LockedStringSegment
                            .Where(x => x > match.Index + rule.Key.Length).OrderByDescending(x => x).ToList()
                            .ForEach(x =>
                            {
                                //We shuffle the locked character's place depending on the replacement delta.
                                LockedStringSegment.Remove(x);
                                LockedStringSegment.Add(x + LengthDelta);
                            });

                        //Add all the new locked character's position to the hashset.
                        Enumerable.Range(match.Index, to.Length).ToList().ForEach(x => LockedStringSegment.Add(x));

                    }
                }
            }

            return input;
        }
        public static void ValidateReplacement(string MethodName, string Actual, string Expected)
        {
            Console.Write($"{MethodName} : ");

            if (Expected != Actual)
                Console.WriteLine("String replacement doesn't work");
            else
                Console.WriteLine("It works");

            Console.WriteLine($"Expected : {Expected}");
            Console.WriteLine($"Actual   : {Actual} \n\n");

        }

    }

}

Answer 1

A recursive solution seems like a good fit for this problem.

        public static string ReplaceOnce(
            string input, 
            Dictionary<string, string> ReplacementRules)
        {
            var matches = ReplacementRules.Where(rule => input.Contains(rule.Key));
            if (!matches.Any()) return input;

            var match = matches.First();
            int startIndex = input.IndexOf(match.Key);
            int endIndex = startIndex + match.Key.Length;

            var before = ReplaceOnce( input.Substring(0,startIndex), ReplacementRules );
            var replaced = match.Value;
            var after = ReplaceOnce( input.Substring(endIndex), ReplacementRules );

            return before + replaced + after;
        }

Answer 2

Another possible solution is to use a Trie.

Using a Trie costs more in setup and space than the original solution but if we are going to be processing a lot of strings with the same set of rules, the cost of setup becomes less of an issue.

Another advantage of the Trie approach is that processing an individual input scales with the length of the input and not with the number of rules.

In essence, we start at the first character of the input and try to match it against the first character of any of the rules (using a dictionary, so the cost is low).

If we do not find a match we add that character to the output and move to the next character.

If we find a match, we try to match the next character of the input against the next character of any of the matching rules (discarding rules as we go), progressing until the input next character of the input no longer matches the next character of any of the remaining matching rules.

At this point we have either matched a rule (IsLeaf == true) and we add the value to the output or else what we have matched was only a fragment (e.g. the input was 'do ' and the rule was 'dog') and we add that fragment of the input to the output and start matching against the full set of rules from the next character in the input.

public class Trie
{

    private readonly IDictionary<char, Trie> _lookup = new Dictionary<char, Trie>();

    public bool Check(char ch, out Trie next)
    {
        return _lookup.TryGetValue(ch, out next);
    }

    public char Char { get; set; }

    public string Key { get; set; }

    public string Value { get; set; }

    public bool IsLeaf => Value != null;

    public void Add(string key, string replacement)
    {
        if (string.IsNullOrEmpty(key))
        {
            throw new ArgumentException("key");
        }

        Trie trie = null;
        var lookup = _lookup;
        foreach(var ch in key)
        {
            if(!lookup.TryGetValue(ch, out trie))
            {
                trie = new Trie { Char = ch };
                lookup.Add(ch, trie);
            }
            lookup = trie._lookup;
        }
        trie.Key = key;
        trie.Value = replacement;
    }

}


public interface ITextReplacer
{
    string Replace(string text);
}


public class TrieReplacer : ITextReplacer
{

    private readonly Trie _root;

    public TrieReplacer(IDictionary<string, string> replacementRules)
    {
        _root = CreateRoot(replacementRules);
    }

    private static Trie CreateRoot(IDictionary<string, string> replacementRules)
    {
        var ret = new Trie();
        foreach(var replacement in replacementRules)
        {
            ret.Add(replacement.Key, replacement.Value);
        }
        return ret;
    }

    public string Replace(string text)
    {
        var ret = new StringBuilder();
        var currentPos = 0;

        while(currentPos < text.Length)
        {
            Trie currentTrie = _root;
            Trie innerTrie;
            while((currentPos < text.Length) && !currentTrie.Check(text[currentPos], out innerTrie))
            {
                ret.Append(text[currentPos++]);
            }
            var savedPos = currentPos;
            while ((currentPos < text.Length) && currentTrie.Check(text[currentPos], out innerTrie))
            {
                currentPos++;
                currentTrie = innerTrie;
                if (currentTrie.IsLeaf) break;
            }
            // not a leaf means that we haven't a match before the input end
            if(currentTrie.IsLeaf)
            {
                ret.Append(currentTrie.Value);
            }
            else
            {
                ret.Append(text.Substring(savedPos, (currentPos - savedPos)));
            }
            
        }
        return ret.ToString();


    }
}

Other

I think there is a problem with the original in terms of functionality but I am not sure. If I am reading the description correctly we should support overlapping keys and use the first match found.

We currently have rules

• John -> Freddy
• John walks -> Freddy runs

and because of the order, we match John ahead of John walks and thus

'John walks his brown dog whenever it's - not - raining'

becomes

'Freddy walks his brown dog whenever it's - not - raining'

If the rules were reversed, we would match the long one first and get

'Freddy runs his brown dog whenever it's - not - raining'

Now, say, we change the rules to

• John walks -> Freddy runs
• runs -> trots

We get (as expected)

'Freddy runs his brown dog whenever it's - not - raining'

The 'runs' to 'trots' change is not made because 'Freddy runs' is in our LockedStringSegment. All good.

Now, if we change the input to

'Tom runs and John walks his brown dog whenever it's - not - raining'

we would expect

'Tom trots and Freddy runs his brown dog whenever it's - not - raining'

but we get

'Tom trots and Freddy trots his brown dog whenever it's - not - raining'

This is because after the check to see if the match for the new key ('runs') is in the LockedStringSegment (it's not), we use the Regex to replace all instances of runs with trots which includes those in the LockedStringSegment

List<int> AffectedCharacterPositions = Enumerable.Range(match.Index, match.Length).ToList();

if (!AffectedCharacterPositions.Any(x => LockedStringSegment.Contains(x)))
{
    input = Regex.Replace(input, from, to);

When we match 'runs', the text is

'Tom runs and Freddy runs his brown dog whenever it's - not - raining'

the first match for 'runs' ('Tom runs') is not in the locked segment so we replace all

'Tom trots and Freddy trots his brown dog whenever it's - not - raining'

Similarly, if the input was

'John walks his brown dog whenever it's - not - raining - and Tom runs'

we would get 'Freddy runs many gray dog sometimes, when it's (not) snowing - and Tom runs'

The first match of 'runs' is inside the LockedStringSegment so none of the occurrences of runs are replaced.