Ruby正则表达式卡死

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正则表达式操作符：token =~ URI_REGEX，但是我没有收到任何异常或错误消息。

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

有没有其他想法来解决这个问题？

- behas

Answer 1

你的问题是灾难性回溯。我刚刚将你的正则表达式和测试字符串加载到RegexBuddy中，它在正则表达式引擎迭代了1,000,000次后放弃了（从外观上看，如果没有终止，它可能会继续进行数百万次）。

问题出现在您的文本的某些部分可以与您的正则表达式的不同部分匹配（这个正则表达式非常复杂且难以阅读）。当它无法工作时，“One or more:”部分和“End with:”部分似乎在匹配方面存在困难，尝试了数百万个所有失败的排列组合。

在不知道匹配URI规则的情况下很难提出解决方案（我不知道）。所有这些括号的平衡让我想到正则表达式可能不是完成此任务的正确工具。也许您可以分解问题。首先使用简单的正则表达式查找所有类似于URI的内容，然后在第二步中验证它（Ruby是否有某种URI解析器？）。

你可能可以使用原子组来防止正则表达式引擎回溯。如果你能将一些(?:...)组更改为(?>...)组，那么这将允许正则表达式通过禁止回溯到这些组来更快地失败。但是，这可能会改变匹配结果，并在需要回溯才能实现匹配的情况下导致匹配失败 - 因此这并不总是一个选项。

- Tim Pietzcker

Answer 2

为什么要重新发明轮子？

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

- Lars Haugseth

---

看，这正是我所说的。使用正确的工具来完成工作，加1分。 - Tim Pietzcker

Answer 3

URI.extract("包含 URI 的文本。") 是最好的解决方案，如果你只需要 URIs。

我最终使用了 pat = URI::Parser.new.make_regexp('http') 来获取内置的 URI 解析正则表达式，并在 match = str.match(pat, start_pos) 中使用它来逐个解析输入文本中的 URI。我这样做是因为我还需要文本中的 URI 位置，而返回的 match 对象给了我这个信息 match.begin(0)。

- behas