正则表达式花了很长时间

Question

我有一个用户输入的搜索字符串.通常,使用空格分割搜索字符串,然后执行OR搜索(如果项匹配任何搜索字符串元素,则匹配项).我想提供一些"高级"查询功能,例如使用引号括起包含空格的文字短语的功能.

虽然我已经敲定了一个像样的正则表达式来为我分割字符串,但它执行时间却非常长(在我的机器上> 2秒).我把它弄清楚了解打嗝的位置,更有趣的是它似乎发生在最后一次Match匹配之后(大概是在输入结束时).直到字符串结尾的所有匹配在更短的时间内匹配然后我可以捕获,但是最后一个匹配(如果它是什么 - 没有返回)几乎占用所有2秒.

我希望有人可能会对我如何加速这个正则表达式有所了解.我知道我正在使用一个无限量词的lookbehind但是,正如我所说,这似乎不会导致任何性能问题,直到最后一场比赛匹配.

码

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

namespace RegexSandboxCSharp {
    class Program {
        static void Main( string[] args ) {

            string l_input1 = "# one  \"two three\" four five:\"six seven\"  eight \"nine ten\"";

            string l_pattern =
                @"(?<=^([^""]*([""][^""]*[""])?)*)\s+";

            Regex l_regex = new Regex( l_pattern );

            MatchCollection l_matches = l_regex.Matches( l_input1 );
            System.Collections.IEnumerator l_matchEnumerator = l_matches.GetEnumerator();

            DateTime l_listStart = DateTime.Now;
            List<string> l_elements = new List<string>();
            int l_previousIndex = 0;
            int l_previousLength = 0;
            //      The final MoveNext(), which returns false, takes 2 seconds.
            while ( l_matchEnumerator.MoveNext() ) {
                Match l_match = (Match) l_matchEnumerator.Current;
                int l_start = l_previousIndex + l_previousLength;
                int l_length = l_match.Index - l_start;
                l_elements.Add( l_input1.Substring( l_start, l_length ) );

                l_previousIndex = l_match.Index;
                l_previousLength = l_match.Length;
            }
            Console.WriteLine( "List Composition Time: " + ( DateTime.Now - l_listStart ).TotalMilliseconds.ToString() );

            string[] l_terms = l_elements.ToArray();

            Console.WriteLine( String.Join( "\n", l_terms ) );

            Console.ReadKey( true );

        }
    }
}

输出
(这正是我得到的.)

一个
"三"
4
五:"六七"
8
"九十"

Answer 1

尝试将正则表达式更改为以下内容:

(?<=^((?>[^"]*)(["][^"]*["])?)*)\s+

这里唯一的变化是将原子组[^"]*放入原子组中,以防止发生灾难性的回溯.

注意:上面的正则表达式显然不使用我不熟悉的C#正则表达式字符串语法,但我认为它将如下:

@"(?<=^((?>[^""]*)([""][^""]*[""])?)*)\s+";

为什么会发生灾难性的回溯:
一旦找到所有有效匹配,则尝试的下一个匹配是最终引用部分内的空间.lookbehind将失败,因为在空格之前有奇数引号.

此时,lookbehind内部的正则表达式将开始回溯.锚意味着它总是从字符串的开头开始,但它仍然可以通过从匹配的结尾删除元素来回溯.让我们看一下lookbehind里面的正则表达式:

^([^"]*(["][^"]*["])?)*

由于引用的部分是可选的,因此可以在正则表达式回溯时删除它们.对于不在引用部分内的每个非引号字符块,在回溯每个字符之前,它们将被匹配为[^"]*正则表达式开头的一部分.当回溯从该部分开始时,最后一个字符将从[^"]*匹配的内容中删除,并将被外部重复拾取.此时它变得非常类似于上面灾难性回溯链接中的示例.