2

回答：

此正则表达式有效：

<item>(?:(?!</item>).|\n)*?(?:(?=201[0-3]</pubDate>))(?:(?!</item>).|\n)*?</item>

而这个使堆栈崩溃：

<item>(?:(?!</item>).|\n)*(?:(?=201[0-3]</pubDate>))(?:(?!</item>).|\n)*</item>

这也有效，没有前瞻：

(?s)<item>.*?201[0-3]</pubDate>.*?</item>

原始问题：

我在 Sublime Text 2 中有一个 XML 文件（下面的示例）。我想找到从 2010 年到 2013 年<item包含 > 元素的所有 > 元素。<pubDate

上面的正则表达式工作正常，但是当我找到所有（文件大约 1MB，大约有 120 个匹配项）时，ST2 的堆栈空间不足。

上面潜伏着什么可怕的低效率？

示例 XML：

<?xml version="1.0" encoding="utf-8"?>
    <channel>
        <item>
            <title>This will match</title>
            <link>http://gcanyon.posterous.com/</link>
            <pubDate>Sat Mar 10 10:22:00 -0800 2012</pubDate>
            <dc:creator><![CDATA[Geoff Canyon]]></dc:creator>
        </item>
        <item>
            <title>This won't</title>
            <link>http://gcanyon.posterous.com/</link>
            <pubDate>Tue Jun 30 05:01:32 -0700 2009</pubDate>
            <dc:creator><![CDATA[Geoff Canyon]]></dc:creator>
        </item>
    </channel>
</rss>
4

2 回答 2

2

贪婪的正则表达式。例如：

(?:(?!</item>).|\n)*

会一直走到下一个</item>，而这不是您想要的，我假设您只是不希望它走得更远。

你应该在懒惰的经营者身上找到快乐。

PS：抱歉，我没有足够的时间来更深入地研究您的正则表达式。希望它能解决你的问题。

于 2013-04-02T15:54:36.820 回答
2

我认为你有两个问题。一个是你的整个方法（如果你只是想要我的真正建议，所以跳到底部），但看起来另一个是灾难性的回溯。

为什么这是破坏

如果我们稍微简化您的模式，可以归结为：

{a}{x*}{x*}{b}

注意到两者x*紧挨着吗？是的，(?=y)它们之间有一个，但让我们暂时忽略它，因为我认为引擎没有有效地使用它来限制它正在做的工作量。假设您有一个类似的字符串，axxxxxxxb并且您希望将其与模式匹配。由于有两个x*令牌彼此相邻，因此引擎无法轻松判断一组结束和另一组开始的位置。所以它试图把它们都放在第一个{x*}桶里，因为它*是贪婪的：

{a}{xxxxxxx}{}{b}

太好了，对吧？它匹配，所以我们可以继续前进。但考虑类似axxxxxxQxb. 这在第一次传递时不匹配，因此引擎必须继续尝试排列：

{a}{xxxxxxx}{}{Q} #nope
{a}{xxxxxx}{x}{Q} #nope
{a}{xxxxx}{xx}{Q} #nope
...

最终，这需要很长时间，它会炸毁你的筹码。

改进正则表达式

那么如何解决呢？嗯，有这个：

(?:(?=201[0-3]</pubDate>))

我认为如果它是一个肯定的标记，而不是一个前瞻，引擎会做得更好。无论如何，它不需要是超前的。你可以使用它（有或没有\s*）：

201[0-3]\s*</pubDate>

(?:(?!</item>).)*后面是多余的；你应该只需要一个懒惰的.*?.

此外，您可以使用 Multiline 选项来.匹配换行符，但我不确定这是否会对速度/执行产生任何影响。不过，写起来会更短。

整个事情看起来像：

<item>(?:(?!</item>).)*?201[0-3]</pubDate>.*?</item>  #plus the /m flag

真正的解决方案

但我认为真正的问题是你完全使用了正则表达式。这看起来像 XML。为什么不使用 XML 解析器？如果您使用的是 .NET，则 LINQ to XML 非常适合您所描述的确切工作，包括有关嵌套pubdate. 应该比正则表达式更容易和更有效。

于 2013-04-02T16:53:18.677 回答