How to make common prefixes for the regex word dictionary?

Question

I have an array of words that need to be executed for the find-and-replace operation on a regular expression, and sometimes this array can be thousands of words. I tested and found that using words using common prefixes is much faster than finding them individually. That is, it ^where|why$works slower than ^wh(ere|y)$. Obviously, this is not a noticeable difference in such a brief example, but much faster when there are thousands of alternatives and the subject line is long.

So I'm looking for a way to do this automatically, for example, to convert string[] { "what", "why", "where", "when", "which" }towh(at|y|e(re|n)|i(ch))

Is there an already recognized algorithm that does this? If not, how would you do it? It seems that this needs to be done recursively, but I cannot figure out how to do it. I have a method that I wrote that works to a limited extent, but it is inelegant, lasts 60 lines and uses several nested foreach loops to make it a nightmare in the future. I am sure there is a much better way if someone can point me in the right direction, which would be very appreciated ...

Answer 1

This code should work:

public static class StemmingUtilities
{
    private class Node
    {
        public char? Value { get; private set; }
        public Node Parent { get; private set; }
        public List<Node> Children { get; private set; }
        public Node(char? c, Node parent)
        {
            this.Value = c;
            this.Parent = parent;
            this.Children = new List<Node>();
        }
    }

    public static string GetRegex(IEnumerable<string> tokens)
    {
        var root = new Node(null,null);
        foreach (var token in tokens)
        {
            var current = root;
            for (int i = 0; i < token.Length; i++)
            {
                char c = token[i];
                var node = current.Children.FirstOrDefault(x => x.Value.Value == c);
                if (node == null)
                {
                    node = new Node(c,current);
                    current.Children.Add(node);
                }
                current = node;
            }   
        }
        return BuildRexp(root);
    }

    private static string BuildRexp(Node root)
    {
        string s = "";
        bool addBracket = root.Children.Count > 1;
        // uncomment the following line to avoid first brakets wrapping (occurring in case of multiple root children)
        // addBracket = addBracket && (root.Parent != null); 
        if (addBracket)
            s += "(";
        for(int i = 0; i < root.Children.Count; i++)
        {
            var child = root.Children[i];
            s += child.Value;
            s += BuildRexp(child);
            if (i < root.Children.Count - 1)
                s += "|";
        }
        if (addBracket)
            s += ")";
        return s;
    }
}

Application:

var toStem1 = new[] { "what", "why", "where", "when", "which" };
string reg1 = StemmingUtilities.GetRegex(toStem1);
// reg1 = "wh(at|y|e(re|n)|ich)"

string[] toStem2 = new[] { "why", "abc", "what", "where", "apple", "when" };
string reg2 = StemmingUtilities.GetRegex(toStem2);
// reg2 = "(wh(y|at|e(re|n))|a(bc|pple))"

EDIT:
to get reg2 = "wh(y|at|e(re|n))|a(bc|pple)"i.e. without first brackets, just uncomment the highlighted line in the method BuildRexp.