如何为正则表达式词干制作公共前缀？

Question

我有一个单词我需要通过正则表达式操作进行查找和替换,有时这个数组可能长达数千字.我已经测试过并发现使用公共前缀来阻止单词比单独搜索它们要快得多.也就是说,^where|why$慢于^wh(ere|y)$.显然,在这样一个简短的例子中,这并不是一个明显的区别,但是如果有数以千计的替代品并且主题字符串很长,它会快得多.

所以我正在寻找一种方法来自动执行此操作,例如将其转换string[] { "what", "why", "where", "when", "which" }为wh(at|y|e(re|n)|i(ch))

是否已经有一个公认的算法可以做到这一点？如果没有,你会怎么做？它似乎需要递归完成,但我不能完全理解如何做到这一点.我有一个我写的方法在有限的范围内工作,但它不够优雅,60行长,并使用多个嵌套的foreach循环,所以这是一个未来的维护噩梦.我相信有更好的方法,如果有人能指出我正确的方向,我会非常感激......

Answer 1

这段代码应该可以工作：

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's 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;
    }
}

用法：

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))"

编辑：
要获得reg2 = "wh(y|at|e(re|n))|a(bc|pple)"没有第一个括号的 ie，只需取消注释方法中的标记行即可BuildRexp。