13

我有一个用户输入的搜索字符串。通常，搜索字符串使用空格分割，然后执行 OR 搜索（如果项目匹配任何搜索字符串元素，则匹配）。我想提供一些“高级”查询功能，例如使用引号将包含空格的文字短语括起来的能力。

虽然我已经敲定了一个像样的正则表达式来为我拆分字符串，但是执行起来需要很长的时间（在我的机器上超过 2 秒）。我打破它来找出打嗝的位置，更有趣的是，它似乎发生在最后一个Match匹配之后（大概是在输入结束时）。直到字符串匹配结束的所有匹配都可以在更短的时间内捕获，但是最后一个匹配（如果是这样的话 - 没有返回）几乎花费了所有 2 秒。

我希望有人可能对我如何加快这个正则表达式有所了解。我知道我正在使用带有无界量词的后视，但是，就像我说的，这似乎不会导致任何性能问题，直到匹配最后一场比赛之后。

代码 

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

1 回答 1

18

尝试将您的正则表达式更改为以下内容：

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

此处唯一的更改是将[^"]*放入一个原子组中，以防止发生灾难性的回溯。

注意：上面的正则表达式显然没有使用 C# 正则表达式字符串语法，我不熟悉，但我认为它会如下：

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

为什么会发生灾难性的回溯：
一旦找到所有有效匹配项，下一个尝试的匹配项就是最后引用部分内的空间。后视将失败，因为空格前有奇数个引号。

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

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

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

于 2012-09-19T17:38:09.727 回答