红宝石正则表达挂起

Question

我编写了一个ruby脚本来处理大量文档,并使用以下URI从文档的字符串表示中提取URI:

#Taken from: http://daringfireball.net/2010/07/improved_regex_for_matching_urls
URI_REGEX = /
(                           # Capture 1: entire matched URL
  (?:
    [a-z][\w-]+:                # URL protocol and colon
    (?:
      \/{1,3}                        # 1-3 slashes
      |                             #   or
      [a-z0-9%]                     # Single letter or digit or '%'
    )
    |                           #   or
    www\d{0,3}[.]               # "www.", "www1.", "www2." … "www999."
    |                           #   or
    [a-z0-9.\-]+[.][a-z]{2,4}\/  # looks like domain name followed by a slash
  )
  (?:                           # One or more:
    [^\s()<>]+                      # Run of non-space, non-()&lt;&gt;
    |                               #   or
    \(([^\s()<>]+|(\([^\s()<>]+\)))*\)  # balanced parens, up to 2 levels
  )+
  (?:                           # End with:
    \(([^\s()<>]+|(\([^\s()<>]+\)))*\)  # balanced parens, up to 2 levels
    |                                   #   or
    [^\s`!()\[\]{};:'".,<>?«»“”‘’]        # not a space or one of these punct chars
  )
)/xi

它适用于所有文档的99.9%,但在遇到文档中的以下标记时总是挂起我的脚本: token = "synsem:local:cat:(subcat:SubMot,adjuncts:Adjs,subj:Subj),"

我正在使用标准的ruby regexp oeprator:token =~ URI_REGEX我没有收到任何异常或错误消息.

首先,我尝试解决将正则表达式评估封装到Timeout::timeout块中的问题,但这会降低性能.

关于如何解决这个问题的任何其他想法？

Answer 1

你的问题是灾难性的回溯.我刚刚将你的正则表达式和你的测试字符串加载到RegexBuddy中,并且它在正则表达式引擎的1.000.000次迭代之后放弃了(从它的外观来看,如果它没有中止,它将会持续数百万次).

出现这个问题的原因是你的文本的某些部分可以被你的正则表达式的不同部分匹配(这是非常复杂和阅读的痛苦); 似乎你的正则表达式中的"一个或多个:"部分和"结束于:"部分在比赛中挣扎(当它不起作用时),尝试所有失败的数百万个排列.

如果不知道匹配URI的规则是什么(我不这样做),很难提出解决方案.所有这些括号的平衡向我表明,正则表达式可能不适合这项工作.也许你可以打破这个问题.首先使用一个简单的正则表达式来查找远程看起来像URI的所有内容,然后在第二步验证(不是某种类型的Ruby的URI解析器吗？).

您可以做的另一件事是通过使用原子组来防止正则表达式引擎回溯.如果您可以将某些(?:...)组更改为(?>...)组,则可以通过禁止回溯到这些组来使正则表达式更快地失败.但是,这可能会改变匹配并使其在需要回溯以实现匹配的情况下失败 - 因此这并不总是一个选项.

Answer 2

为什么重新发明轮子？

require 'uri'
uri_list = URI.extract("Text containing URIs.")