相关疑难解决方法(0)

我最近有一个SonarQube规则（https://rules.sonarsource.com/java/RSPEC-4784）引起了我的注意，一些性能问题可以用作对 Java 正则表达式实现的拒绝服务。

事实上，以下 Java 测试显示了错误的正则表达式的速度有多慢：

    import org.junit.Test;

    public class RegexTest {

    @Test
    public void fastRegex1() {
        "aaaaaaaaaaaaaaaaaaaaaaaaaaaabs".matches("(a+)b");
    }

    @Test
    public void fastRegex2() {
        "aaaaaaaaaaaaaaaaaaaaaaaaaaaab".matches("(a+)+b");
    }

    @Test
    public void slowRegex() {
        "aaaaaaaaaaaaaaaaaaaaaaaaaaaabs".matches("(a+)+b");
    }
}

如您所见，前两个测试很快，第三个测试非常慢（在 Java 8 中）

然而，Perl 或 Python 中的相同数据和正则表达式一点也不慢，这让我想知道为什么这个正则表达式在 Java 中的计算速度如此之慢。

$ time perl -e '"aaaaaaaaaaaaaaaaaaaaaaaaaaaabs" =~ /(a+)+b/ && print "$1\n"'
aaaaaaaaaaaaaaaaaaaaaaaaaaaa

real    0m0.004s
user    0m0.000s
sys     0m0.004s

$ time python3 -c 'import re; m=re.search("(a+)+b","aaaaaaaaaaaaaaaaaaaaaaaaaaaabs"); print(m.group(0))'
aaaaaaaaaaaaaaaaaaaaaaaaaaaab

real    0m0.018s
user    0m0.015s
sys     0m0.004s …

我有一个用户输入的搜索字符串.通常,使用空格分割搜索字符串,然后执行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 …

尝试在Chrome的JS控制台中输入此内容.我发现这是一个正则表达式,用于检查某些内容是否为有效的URL:

"http://www.kvraudio.com/".match(/^(https?:\/\/)?([\da-z\.-]+)\.([a-z\.]{2,6})([\/\w \.-]*)*\/?$/);

返回匹配,应该是.现在试试这个:

"tp:/www.kvraudio.com/forum/viewtopic.php".match(/^(https?:\/\/)?([\da-z\.-]+)\.([a-z\.]{2,6})([\/\w \.-]*)*\/?$/);

返回Null,因为它不匹配.现在.....试试这个:

"http://www.kvraudio.com/forum/viewtopic.php?p=5238905".match(/^(https?:\/\/)?([\da-z\.-]+)\.([a-z\.]{2,6})([\/\w \.-]*)*\/?$/);

没有!JS似乎已经死了或以某种方式陷入循环.如果我在实际网页中使用上述内容,则会停止响应.甚至不会滚动!有人对此有任何解释吗？我做错了什么？!

我有一个.Net Regex表达式,它从字符串中提取所有有效的Url.它通过我的所有20个单元测试,除了一个:当Url包含问号时.这导致正则表达式引擎挂起进程并造成严重破坏.

我在这个表达上花了很多时间,但我不确定如何解决这个问题.希望一个正则表达式专业人士可以伸出援助之手!两部分问题:

1)如何改进此正则表达式模式,以便在评估字符串" http://www.example.com/?a=1 " 时不会挂起:

正则表达式模式:

(?<URL>(\s|^)((?<Scheme>[A-Za-z]{3,9})[:][/][/])?([A-Za-z0-9-]+[.])+([A-Za-z]+){2,4}(?(Scheme)|[/])(((?:[\+~%\/.\w-_]*[/]?)?\??#?(?:[\w]*))?)*(\s|$))

我建议使用这个很棒的在线.Net Regex测试引擎:http://regexhero.net/tester/

2)我的呼叫代码可以做些什么来阻止/恢复正则表达式引擎挂起？这是调用代码:

        Regex linkParser = new Regex(UrlMatchRegex, RegexOptions.Compiled | RegexOptions.IgnoreCase);

        // Find matches and add them to the result
        foreach (Match m in linkParser.Matches(message))
        {
            result.Add(m.Value.Trim());
        }

我花了相当多的时间在这个特殊的Regex模式上,并尝试了至少7个我发现的替代品(包括本页的大部分内容:http://mathiasbynens.be/demo/url-regex).我宁愿改进我现有的模式,而不是使用完全不同的模式,但我愿意选择.

最终正则表达式v1:

经过一些修改,在下面的帮助下,我的最终正则表达式匹配如下所示:

(?<URL>((?<=\s)|^)((?<Scheme>[A-Za-z]{3,9})[:][/][/])?([A-Za-z0-9-]+[.])+[A-Za-z]{2,4}(?(Scheme)|[/]?)(((?:[\+~%\/.\w-_]*[/]?)?\??#?&?(?:[\w=]*))?)*((?=\s)|$))

**Regex v2:已更新,包含域名,端口号,主题标签的集合列表,但不包含尾随斜杠

(?<URL>((?<=\b)|^)((?<Scheme>[A-Za-z]{3,9})[:][/][/])?([A-Za-z0-9-]+[.])+((?<TLD>\b(aero|asia|biz|cat|com|coop|edu|gov|info|int|jobs|mil|mobi|museum|name|net|org|pro|tel|travel|ac|ad|ae|af|ag|ai|al|am|an|ao|aq|ar|as|at|au|aw|ax|az|ba|bb|bd|be|bf|bg|bh|bi|bj|bm|bn|bo|br|bs|bt|bv|bw|by|bz|ca|cc|cd|cf|cg|ch|ci|ck|cl|cm|cn|co|cr|cu|cv|cx|cy|cz|cz|de|dj|dk|dm|do|dz|ec|ee|eg|er|es|et|eu|fi|fj|fk|fm|fo|fr|ga|gb|gd|ge|gf|gg|gh|gi|gl|gm|gn|gp|gq|gr|gs|gt|gu|gw|gy|hk|hm|hn|hr|ht|hu|id|ie|il|im|in|io|iq|ir|is|it|je|jm|jo|jp|ke|kg|kh|ki|km|kn|kp|kr|kw|ky|kz|la|lb|lc|li|lk|lr|ls|lt|lu|lv|ly|ma|mc|md|me|mg|mh|mk|ml|mn|mn|mo|mp|mr|ms|mt|mu|mv|mw|mx|my|mz|na|nc|ne|nf|ng|ni|nl|no|np|nr|nu|nz|nom|pa|pe|pf|pg|ph|pk|pl|pm|pn|pr|ps|pt|pw|py|qa|re|ra|rs|ru|rw|sa|sb|sc|sd|se|sg|sh|si|sj|sj|sk|sl|sm|sn|so|sr|st|su|sv|sy|sz|tc|td|tf|tg|th|tj|tk|tl|tm|tn|to|tp|tr|tt|tv|tw|tz|ua|ug|uk|us|uy|uz|va|vc|ve|vg|vi|vn|vu|wf|ws|ye|yt|yu|za|zm|zw|arpa)\b))+(\/?)+((((?:[:\+~%/.\w-_\/])?[\?]?[#]?[&]?(?:[\w=]*))?)+(?=\?|\b)))

测试用例:这是对#的测试

不应该匹配:

like when you a/b test something
this sentence ends with a/
just a #hashtag

应该匹配:

sos.me extra
sos.me. extra <-- not period
sos.me, extra <-- not comma …

我要求一般工具或方法找到正则表达式中的"热点",导致不受控制的回溯.我对占有性匹配,负面前瞻断言,原子团体等有相当好的把握,但我面临的情况是,我的正则表达式错误到底在哪里都不清楚.

有问题的正则表达式是PCRE正则表达式; 但我会为任何语言的任何指针感到高兴.

理想情况下,我希望看到一个突出正则表达式中"热点"的工具.我过去曾尝试创建一个包装器,perl -Mre=debug但无法弄清楚我应该如何有效地处理它的输出.模糊地说,想法是针对正则表达式运行一个或多个输入字符串,并收集匹配器中的偏移量(以及可能是字符串中的偏移量),匹配器将继续返回.

我编译了以下模式

pattern = re.compile(
    r"""
    (?P<date>.*?)
    \s*
    (?P<thread_id>\w+)
    \s*PACKET\s*
    (?P<identifier>\w+)
    \s*
    (?P<proto>\w+)
    \s*
    (?P<indicator>\w+)
    \s*
    (?P<ip>\d+\.\d+\.\d+\.\d+)
    \s*
    (?P<xid>\w+)
    \s*
    (?P<q_r>.*?)
    \s*\[
    (?P<flag_hex>[0-9]*)
    \s*
    (?P<flag_char_code>.*?)
    \s*
    (?P<status>\w+)
    \]\s*
    (?P<record>\w+)
    \s*
    \.(?P<domain>.*)\.
    """, re.VERBOSE
    )

使用此字符串

2/1/2014 9:34:29 PM 05EC PACKET 00000000025E97A0 UDP Snd 10.10.10.10 ebbe R Q [8381 DR NXDOMAIN] A (1)9(1)a(3)c-0(11)19-330ff801(7)e0400b1(4)15e0(4)1ca7(4)2f4a(3)210(1)0(26)841f75qnhp97z6jknf946qwfm5(4)avts(6)domain(3)com(0)

它成功运作

In [4]: pattern.findall(re.sub('\(\d+\)', '.', x))
Out[4]: 
[('2/1/2014 9:34:29 PM',
  '05EC',
  '00000000025E97A0',
  'UDP',
  'Snd',
  '10.10.10.10',
  'ebbe',
  'R Q',
  '8381',
  'DR',
  'NXDOMAIN',
  'A',
  '9.a.c-0.19-330ff801.e0400b1.15e0.1ca7.2f4a.210.0.841f75qnhp97z6jknf946qwfm5.avts.domain.com')]

问题是在某些情况下需要很长时间,任何想法如何增强消耗时间的模式.