0

假设我有一个任意的正则表达式列表（IList<Regex> lst;例如）。有没有办法找出字符串中较早的匹配项？

当然，有一个直接的解决方案是在字符串上尝试每个匹配项并查看哪个匹配项的索引最低，但这对于长字符串可能效率低下。

当然，我可以返回并从每个正则表达式中拉出字符串Regex.ToString()（"(regex1)|(regex2)|(regex3)"

编辑：基本上，有没有办法在没有字符串操作和重新编译的情况下组合已经编译的正则表达式？

4

3 回答 3

2

众所周知，执行一个包含多个组的表达式通常比依次执行每个表达式要慢。看起来创建一个表达式会更快，但实际上正则表达式引擎将首先搜索整个字符串以找到第一个表达式，可能一直到字符串的末尾，但是当它找到匹配项时它将返回。所以没有办法强制它返回第一个匹配项。这是由于 .NET Regex 引擎的工作方式。

由于每个正则表达式可能在字符串中较早开始，但可能导致更长的匹配，因此您不能将搜索的结尾限制为当前最早匹配的索引，如下所示：

        // WARNING WILL NOT ALWAYS RESULT IN THE RIGHT VALUES
        List<Regex> rxs = new List<Regex>(4);
        rxs.Add(new Regex("def"));
        rxs.Add(new Regex("abc"));
        rxs.Add(new Regex("bcd"));
        rxs.Add(new Regex("cde"));

        string target = "abcdef";
        int firstIndex = target.Length;
        string firstMatch = string.Empty;

        foreach (var rx in rxs)
        {
            var match = rx.Match(target, 0, firstIndex);
            if (match.Success)
            {
                firstIndex = match.Index;
                firstMatch = match.Value;
                if (firstIndex == 0) break;
            }
        }
        return firstMatch;

当您知道每个正则表达式将匹配的最大长度时，这将起作用，在这种情况下使用：

        // WARNING WILL NOT ALWAYS RESULT IN THE RIGHT VALUES
        List<Regex> rxs = new List<Regex>(4);
        rxs.Add(new Regex("def"));
        rxs.Add(new Regex("abc"));
        rxs.Add(new Regex("bcd"));
        rxs.Add(new Regex("cde"));

        string target = "abcdef";
        int firstIndex = target.Length;
        string firstMatch = string.Empty;

        foreach (var rx in rxs)
        {
            var match = rx.Match(target, 0, firstIndex + GetMaxLength(rx));
            if (match.Success)
            {
                firstIndex = match.Index;
                firstMatch = match.Value;
                if (firstIndex == 0) break;
            }
        }
        return firstMatch;

但是您可以在第一个位置找到匹配项后立即进行短路，从而为您节省之后的任何潜在处决。

        foreach (var rx in rxs)
        {
            var match = rx.Match(target);
            if (match.Success)
            {
                if (match.Index < firstIndex)
                {
                    firstIndex = match.Index;
                    firstMatch = match.Value;    
                }
                if (firstIndex == 0) break;
            }
        }

通过一些技巧，您可以使用当前第一个匹配候选的索引来限制搜索，但我怀疑它实际上仍然比搜索所有可能的匹配要慢：

        List<string> rxs = new List<string>(4);
        rxs.Add( "def");
        rxs.Add( "abc");
        rxs.Add( "bcd");
        rxs.Add( "cde");

        string target = "abcdef";
        int firstIndex = target.Length;
        string firstMatch = string.Empty;

        foreach (var rx in rxs)
        {
            var match = Regex.Match(target, @"(?<!\A[\w\W]{" + firstIndex + "})" + rx);
            if (match.Success)
            {
                if (match.Index < firstIndex)
                {
                    firstIndex = match.Index;
                    firstMatch = match.Value;    
                }
                if (firstIndex == 0) break;
            }
        }

最后，进行试验和衡量，以找到最适合您的方式。

我确实有一些额外的信息：至少有一个正则表达式会在字符串的开头附近找到。

在这种情况下，您可以选择首先使用合理的长度索引值进行扫描，因此rx.Match(targetstring, 0, 1024 /* First scan */)只有在找不到匹配项时才使用，然后在第二遍中扩大搜索范围。如果您的目标字符串可以非常大，这将节省大量计算能力。

于 2012-11-29T14:06:36.407 回答
0

RegularExpressions.Match正则表达式匹配返回的类型包含一个Index属性，该属性指示在原始字符串中找到匹配项的位置。

您可以从几个不同的正则表达式结果中进行比较，以确定第一个匹配项。

就像是

 (from m in regexList
 let match = m.Match(targetstring)
 orderby match.Index
 select m.Value).FirstOrDefault()

注意：我没有针对语法或其他问题对此进行测试，因为您没有提供任何代码可以快速剪切并粘贴到 Linqpad 中以创建测试环境，我现在必须上班。但这应该给你一个大致的想法。

这与正则表达式是否已经编译无关——最终你将不得不针对目标字符串尝试它们中的每一个。

由于运行时环境在正常情况下管理您编译的正则表达式的编译和缓存，我不确定您的问题是什么，除非还有其他信息或尚未共享的上下文允许在尝试之前选择正则表达式它针对目标字符串。

于 2012-11-29T11:30:42.643 回答
0

不涉及您自己的正则表达式匹配器的唯一方法确实是连接路由。您可以将每个都放在一个命名的子组中，然后查看哪个组实际匹配以找出哪个原始正则表达式匹配。

我想知道您为什么如此担心重新编译，因为如果您同时担心大量输入，那么该步骤可能不是瓶颈...

于 2012-11-29T11:41:29.497 回答