提高正则表达式的性能

Question

提高正则表达式的性能

3

我的软件允许用户使用正则表达式来准备文件。我正在添加一个默认的正则表达式库，其中包含可以重复使用以准备各种格式的常见表达式。一个常见的任务是在文件的特定部分删除crlf，但不在其他部分删除。例如：

    <TU>Lorem 
    Ipsum</TU>
    <SOURCE>This is a sentence
    that should not contain
    any line break.
    </SOURCE>

Should become:

    <TU>Lorem 
    Ipsum</TU>
    <SOURCE>This is a sentence that should not contain any line break.
    </SOURCE>

我有一个非常好用的正则表达式可以完成这个任务：

(?(?<=<SOURCE>(?:(?!</?SOURCE>).)*)(\r\n))

问题在于它需要大量处理时间，对于超过500kb的文件，可能需要30秒以上的时间。(在这种情况下，正则表达式已经编译，未编译的速度要慢得多)

虽然这不是一个大问题，但我想知道是否有更好的方法来使用正则表达式实现相同的结果。

提前感谢您的建议。

- Sylverdrag

2

哪种语言？（那个文件是XML格式的吗？） - kennytm

你尝试过查找闭合标签而不是开放标签吗？我经常觉得正则表达式引擎更自然地向前走。 - Jens

2

你有没有考虑不使用正则表达式？ - Daniel Trebbien

@KennyTM：那个文件只是一个例子。它可以是任何东西（无论是什么基于文本的格式）。这种要求在文件准备中相当常见，但不一定如此。因此，必须由用户决定。无法预测文件将是什么以及其中需要准备什么。如果我能预测到，我就会编写解析器。 - Sylverdrag

3个回答

2

我会在正则表达式中加入一个负向先行断言，以确保您可以实际匹配当前位置的\r\n。否则，引擎必须对整个文件中的每个字符执行整个回溯（任意大小），只为了发现没有回车符需要替换。

(?=\r\n)(?(?<=<SOURCE>(?:(?!</?SOURCE>).)*)(\r\n))

应该会更快。至少在RegexBuddy中，正则表达式引擎需要更少的步骤才能完成匹配。如果在.NET中不是这样，我不知道为什么。也许条件正则表达式不够高效（我必须承认，起初我没有认出它，以为你的正则表达式有语法错误）。我认为在这种情况下你不需要使用条件正则表达式。那么怎么样呢？

\r\n(?<=<SOURCE>(?:(?!</?SOURCE>).)*)

这样会更快吗？我假设你使用了RegexOptions.Singleline来编译正则表达式。

如果不是这样，那么你的<SOURCE>块内可能有很多回车和其他字符，任意大小的向后查找需要很长时间。那么我的另一个建议是分解任务：

匹配<SOURCE>块
替换块内所有CRLF（无需正则表达式）
替换<SOURCE>块

- Tim Pietzcker

谢谢您的建议。(+1) 它非常有道理，我很有希望，但我用秒表计时了Expresso和同样的文本样本。它们都在21秒内完成。由于未知原因，在我的程序中，对同一文件进行相同操作需要8秒钟，而且无论我是否使用负向先行断言进行测试，结果都是一样的。我认为这意味着.NET在运行正则表达式之前已经进行了优化。 - Sylverdrag

回复：解析器。文件格式事先未知。我的软件的主要特点是准备基于文本的文件，这些文件不遵循规则或不存在已知规则。我在此示例中使用类似XML的标记，因为它使人们非常容易理解我想做什么，但实际上可以是任何东西。我可以编写一个解析器来处理此特定功能，但是有许多此类结构，我无法为每个结构编写解析器并在有人请求新片段时发布新版本。尽可能地，我希望坚持使用正则表达式。 - Sylverdrag

感谢您的更新。\r\n(?<=<SOURCE>(?:(?!</?SOURCE>).)*) 比之前好了一点（从21秒缩短到18秒），但我还是选择了Alan的答案，因为它更快。非回溯子表达式（>）真的是一个很棒的技巧。 - Sylverdrag

2

试试这个：

\r\n(?=(?>[^<>]*(?><(?!/?SOURCE>)[^<>]*)*)</SOURCE>)

首先匹配\r\n，然后使用前瞻来查看匹配是否在<SOURCE>和</SOURCE>之间。它通过寻找</SOURCE>来实现，但如果它先找到<SOURCE>，则匹配失败。原子组可以防止保存回溯所需的状态信息，因为无论成功还是失败，都不需要回溯。

- Alan Moore

非常感谢！在 Expresso 中可以将时间减少一半，在我的应用程序中可以节省约 2 秒钟！ - Sylverdrag

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- msw · Accepted Answer

“编译”正则表达式的意思是将其从确定性有限自动机转换为非确定性有限自动机。它不是像您预期的那样“编译成机器代码”。

NFAs通常比它们对应的DFA小，并且可以更有效地执行空间。每个DFA都至少有一个等效的NFA，反之亦然。但是， Perl兼容正则表达式并不是真正的正则表达式。所以我不知道它们是否被转换为NFAs，或者“编译”是否只是另一种形式的词法分析，一旦完成就不需要再做了。

根据Russ Cox的说法，PCRE很慢，部分原因是它们的非正规性，而您上面的表达式非常非正规。

哦，如果你试图用正则表达式识别嵌套标签，请不要这样做。使用真正的 (X|HT)?ML 解析器。你真的不希望小马出现。