1

我注意到正则表达式完成一个包含 3000 行 [1] 的 XML 文件非常慢：

\(<Annotation\(\s*\w\+="[^"]\{-}"\s\{-}\)*>\)\@<=\(\(<\/Annotation\)\@!\_.\)\{-}"MATCH\_.\{-}\(<\/Annotation>\)\@=

我一直认为正则表达式是有效的。为什么完成 Regex 需要这么长时间？

[1] 如何在 VIM 中从 A 到 B 重复匹配？

4

4 回答 4

5

它是否有效取决于正则表达式本身。它使效率低下的是回溯。为了避免这种情况，正则表达式必须尽可能不同。

我们以正则表达式a.*b为例，将其应用于字符串abcdef。该算法将首先将文字ain匹配a.*b到ain abcdef。接下来.*将处理表达式。bcdef在正常的贪心模式下，乘数被扩大到最大值，它将匹配abdef. 最后一个文字bina.*b将被处理。但是由于已经到达字符串的末尾并且正在使用乘法器，该算法将尝试回溯以匹配整个模式。.*( )的匹配bcdef将减少一个字符 ( bcde) 并且算法尝试遵守模式的其余部分。但是bina.*b不匹配f在abcdef. So.*将再减少一个字符，直到它匹配空字符串（因此.重复零次）并且bina.*b匹配bin abcdef。

如您所见，a.*b应用于整个正则表达式匹配之前abdef需要 6 种回溯方法。.*但是如果我们改变正则表达式并通过使用来区分它a[^b]*b，则不需要回溯，并且正则表达式可以在第一种方法中匹配。

如果你现在考虑改用惰性修饰符，我要告诉你，这条规则适用于每个修饰符，包括贪婪和惰性修饰符。不同之处在于不是首先将匹配扩展到最大值，而不是通过一次减少一个字符（贪婪）来进行回溯，惰性修饰符将首先扩展到最小匹配，而不是一次增加一个字符。

于 2009-04-11T12:47:01.263 回答
3

REs是有效的，但它们不是魔法 :-)

让你慢下来的不是输入文件中的行数（3,000 是一个非常小的数字）。当一个 RE 被编译时，它基本上必须（从概念上）编写一个可以基于该 RE 解析输入文件的程序。

该“程序”的速度始终取决于 RE 的复杂性。

例如，"^$"会非常快，"[0-9]{1,9}"会稍微慢一些，任何涉及回溯（即，必须在 RE 中备份，通常任何涉及多个可变元素数子句的任何内容，您的就是一个例子）都将是还是慢点。

您可以采取任何措施预先减少行数，这在一定程度上会有所帮助，但对于优化 RE 本身，这通常被认为是一种黑色艺术。一种可能性是首先去除注释停止和开始的行之间的行以外的行。

我不太担心优化我的 RE（但它们通常不会这么复杂）。我的观点是，只要他们愿意，他们就会坚持下去。如果时间太长，我通常会寻找另一种更快但适应性不强的解决方案。

在您想要获取about属性包含 MATCH 的所有 Annotation XML 的 RE 的情况下，我会在 Perl 中进行（或者对于我们的老前辈来说是 awk :-)，因为输入文件的格式相当固定：

  • 第一行 [a] 上的“<Annotation”。
  • “匹配”也在第一行 [a]。
  • </Annotation> 在最后一行和它自己的 [b]。

这将是一个简单的线扫描仪，在满足 [a] 条件时打开回显（并打印该行），在回显打开时打印任何其他行，并在满足 [b] 条件时关闭回显（在印刷线）。

是的，适应性要差得多，但几乎可以肯定更快（鉴于您的输入格式正确）。

于 2009-04-11T12:33:48.860 回答
2

我发现很难用所有反斜杠阅读你的正则表达式；如果我正确解释了这种正则表达式（vim？）的方言，那么您所说的是详细的 pcre 会拼写什么：

(?<= <Annotation(\s*\w+="[^"]*?"\s*?)*> )
    ((?! <\/Annotation).)*?
    "MATCH.*?
(?= <\/Annotation> )

一个明显的问题是它以可变长度的lookbehind断言开始。可变长度的lookbehind 已经够麻烦了（并且在许多正则表达式方言中不支持），但是它后面跟着一个自由匹配（任何带有否定lookahead 的字符）。

这对于处理器来说很难匹配；这种组合几乎扼杀了它可能实现的任何可能的优化。对于文件中的每个字符，它必须回溯（可能到文件开头/前一个匹配的结尾）以查看后向是否匹配，然后向前（可能到文件末尾）查找“MATCH.

您可以通过仅使用固定大小的后视来帮助它，或者只是忘记环视并在匹配中包含整个字符串，这将更有效地查找，但需要更多的后处理来挑选您感兴趣的组。

<Annotation(\s+(\w+="[^"]))*\s*>
    (.*? "MATCH .*?)
<Annotation>

但是，与此类问题一样，Clippy sez：

看起来您正在使用正则表达式解析 XML。

你需要帮助吗？

( ) 使用真正的 XML 解析器，因为正则表达式天生无法解析 XML

（）只是士兵制作仍然无法工作的难以理解的复杂正则表达式

[ ] 不要再给我看这个提示

于 2009-04-11T13:02:36.187 回答
1

“正则表达式是有效的”是一个太宽泛的描述，不准确。如果您忽略不同正则表达式引擎提供的相对性能的差异，那么您的正则表达式的效率仍然取决于模式的复杂性。

正则表达式在更快地失败时是有效的，而不是成功地更快地匹配部分文本。IOW，它需要足够具体，以便不完全匹配的文本应该在匹配过程的早期被拒绝，而不是到达结尾。这也意味着需要最小化回溯。请注意，回溯可能会达到灾难性水平，即使是最好的 Regex 引擎也会冻结。在 Jan Goyvaerts 提供的示例中，文件的大小甚至没有被提及并且不相关。然而，重要的是字符串的大小。

这是我几年前在 RegexAdvice.com 上开始的一个讨论线程，试图让人们讨论正则表达式的性能。我想它确实有一些值得学习的地方。

于 2009-04-11T12:52:02.403 回答