c# - 这些类型的正则表达式可以优化吗？

Question

我正在开发一款需要从文本中提取关键信息的应用。问题是文本来自 OCRed 文档，因此可能存在 OCR 识别错误、噪音、垃圾字符等。此外，文档上的文本可能有上百万种不同的格式，具体取决于来源。

因此，我们使用大量正则表达式来提取文本。我们注意到，在大容量情况下，这会重击服务器上的 CPU。我试过预编译正则表达式并缓存它们，但没有任何改进。 Profiler 显示 65% 的运行时间是由于调用 Regex.Match()。

阅读正则表达式，我发现灾难性回溯是一个性能问题。

假设我有一个这样的表达式(这是一个简单的表达式，只是为了说明我们的正则表达式的一般格式——其他表达式可以包含更多的关键字和格式):

(.*) KEYWORD1 AND (.* KEYWORD2)

当我逐步使用 Regex Coach 时，我发现它进行了大量回溯以匹配字符串。

这种正则表达式能否在概念上得到改进？我们只针对整个文档的一个子集(较小的文本 block )运行，但提取文本 block 的预处理本质上也不完美。

所以，是的，几乎任何东西都可以出现在“KEYWORD1”之前，任何东西都可以出现在“KEYWORD2”前面，等等。

我们不能限制为 A-Z 而不是 .*，因为在 OCR 世界中，字母有时会被误认为数字(即 Illene = I11ene)，或者由于 OCR 识别错误，我们可能会在其中得到乱码。

Answer 1

是的，这些类型很容易优化。

您可以通过将正则表达式替换为预期代码来优化它们。也就是说，两次子串搜索。如果 "KEYWORD1 AND " 的位置小于 "KEYWORD2" 的位置，那么你就有了匹配项。

要获得额外的速度，您可以使用优化的子字符串搜索，但这几乎肯定是不需要的。只需删除正则表达式即可大幅提升速度。

[编辑]好的，所以有 400 个。其中一些稍微复杂一些。模式保持不变:可以有效定位的大量子串几乎没有变化。如果您知道 "PART OF" 出现在您的输入中，则检查 "PART OF" 是否出现可以在大约一纳秒内完成。如果 PARTF OF_ _doesn't_ 发生，则根本不需要检查 AS PART OF` 是否发生。

现在 400 个正则表达式并不多。如果您有 40.000，自动检查公共(public)子字符串是值得的。目前，您可能只是依次运行每个正则表达式，尝试匹配其他 399 个正则表达式 strings 以获得第一次切割。 .*PART OF.* 将匹配 ".*AS PART OF.*"。

出于同样的原因，您也不需要其他优化。有 40.000 个要匹配的正则表达式，我会计算每个字母对的频率。 IE。输入 FOO AS PART OF BAR 有字母对 FO, OO, PA, AR (twice), RT, OF, BA。这不能与 .*FOR EXAMPLE.* 匹配，因为缺少字母对 EX。对的