4

我试图通过寻找“！”，“？”来确定英语句子的结尾（仅近似）。或“.”，但在“.”的情况下 仅当前面没有常见缩写词（例如 Mr. 或 Dr.）时。

有什么方法可以使以下正则表达式更加高效？也许通过按大小递减，甚至按字母顺序对负面的lookbehinds进行排序？

这是我现在拥有的正则表达式：

((?<!St|Sgt|Rev|Ltd|Inc|Lt|Jr|Sr|Esq|Inst|Hon|Gen|Cpl|Comdr|Col|Corp|Mr|Dr|Gov|Mrs|Ms|[A-Z]|Assn|Capt)(\.)|(!)|(\?))(\s*$|\s+([_$#]|[A-Z][^.]))

问题：

http://regex.powertoy.org/上的网站报告说：“7 匹配 21044 探针（已完成）”，即使是一个简单的段落......数字 21044 的惊人大小似乎与负面回溯的数量密切相关。

我正在寻求降低 RegEx 引擎的计算复杂性，因为我有几 GB 的数据要通过它。

有什么办法可以解决这个问题吗？消极的后视真的是实现这一目标的最佳/唯一方法吗？有没有办法把它作为一个前瞻来代替？正则表达式是这个任务的错误工具吗？

编辑：我可以使用 ActionScript 或 PHP 的 RegEx 引擎。

编辑：我不能指望句子之间的空格数。 真的！？叹。

如果您不了解 RegEx 引擎的内部工作原理，请不要回答与优化有关的问题。

提前致谢。

4

3 回答 3

4

我会先匹配期间。而不是这个：

(?<!St|Sgt|Rev|Ltd|Inc|...|Capt)\.

...做这个：

\.(?<!(?:St|Sgt|Rev|Ltd|Inc|...|Capt)\.)

按照您的方式，正则表达式引擎必须在确定下一个字符是句点之前执行向后查找。当我进行更改时，它从28,423探针变为1,945。（我使用的是 Powertoy 网站提供的默认文本，因为您没有提供任何内容。）

我还将接下来的两个替代方案 - 合二为一(!)|(\?)，即([!?]). 这使探测计数减少到1,344。如果您不必捕获匹配的各个部分，我建议您使用非捕获括号 - 即，(?:...)而不是(...). 虽然它没有反映在探测计数中，但它确实使正则表达式更有效。

编辑：仔细看看你的正则表达式，我发现它没有找到任何匹配项的原因是[A-Z]另一种选择。由于整场比赛是在不区分大小写的模式下完成的，因此该替代方案胜过所有其他比赛。您应该删除/i修饰符或使用构造在本地覆盖(?-i:...)。正如@Swiss 建议的那样，添加\b（单词边界）也是一个好主意。这给你留下了：

(?-i:\.(?<!\b(?:St|Sgt|Rev|Ltd|Inc|...|[A-Z]|Assn|Capt)\.)

...随着[!?]更改，在 Regex Powertoy 站点上的 1404 次探测中产生 6 次匹配。

于 2010-10-19T05:17:20.170 回答
4

也许在成功匹配后尝试只做消极的后视测试。而不是每个字符：

(?x:  # Allow spacing and comments
    (   
        (\.)    # First match "."
        (?<!    # Then negative-look-behind for titles followed by "."
            (?: St|Sgt|Rev|Ltd|Inc|Lt|Jr|Sr|Esq|Inst|Hon|Gen|Cpl|Comdr|Col|Corp|Mr|Dr|Gov|Mrs|Ms|[A-Z]|Assn|Capt)
            \.
        )
      |  (!)  
      |  (\?)
    )
    ( \s* $  |  \s+ ( [_$#] | [A-Z] [^.] ))
)

这使 powertoy.org 上的探测数量从 70000 减少到 2500 左右，使用该站点的初始帮助文本。（但 powertoy 不喜欢我的多行正则表达式或“x”标志或其他东西，所以我不得不将正则表达式压缩到一行来测试它）。

您可以通过在标题列表中使用通用前缀来更进一步：

(?x:  # Allow spacing and comments
    (
        (\.)    # First match "."
        (?<!    # Then negative-look-behind for titles followed by "."
            (?:Assn|C(?:apt|ol|omdr|orp|pl)|Dr|Esq|G(?:en|ov)|Hon|I(?:nc|nst)|Jr|L(?:t|td)|M(?:[rs]|rs)|Rev|S(?:gt|[rt])|[A-Z])
            \.
        )
      |  (!)  
      |  (\?)
    )
    ( \s* $  |  \s+ ( [_$#] | [A-Z] [^.] ))
)

这使探测计数减少到大约 2000 次。

编辑：
另一个减少探测计数的技巧是在后视部分的开头包含一个大写字母的前瞻（但我不能肯定它会使正则表达式更有效）（还包括@Swiss 对单词边界的建议）：

        (?<!   # Then negative-look-behind for titles followed by "."
               \b (?= [A-Z] )  # But first ensure we have a capital letter before going on
               (?:Assn|C(?:apt|ol|omdr|orp|pl)|Dr|Esq|G(?:en|ov)|Hon|I(?:nc|nst)|Jr|L(?:t|td)|M(?:[rs]|rs)|Rev|S(?:gt|[rt])|[A-Z])
            \.
        )
于 2010-10-19T05:17:28.723 回答
2

停止印刷机！

根据您编辑的问题，您正在为该项目使用 PHP 或 ActionScript，这意味着到目前为止提供的解决方案都没有任何用处。您的原始正则表达式不仅太慢，而且在目标平台上根本不起作用。它在 Regex Powertoy 站点上运行的原因是因为该站点使用 Java regex 风格，它对lookbehinds 有更宽松的限制。

Lookbehind 是正则表达式功能中的害群之马；几乎所有的风格都对你可以在其中使用的表达方式施加了限制。例如，在 Perl 或 Python 中，表达式必须有一个固定的长度：(?<!St)will work 和 will 一样(?<!Sgt|Rev)，但(?<!St|Sgt)不会。Java 更加宽松；只要可以提前确定最大可能长度，它就接受可变长度的后向表达式，因此(?<!St|Sgt)可以正常工作，(?<!\w{3,12})但(?<!\w+)不会。

PHP 和 ActionScript 正则表达式风格都由 PCRE 库提供支持，就后向搜索而言，它比 Perl 和 Python 稍微宽松一点。如果lookbehind 表达式是一个替代，每个替代的长度仍然必须是固定的，但它们不必都具有相同的长度。但这仅在正则表达式的顶级“级别”中被允许——也就是说，lookbehind 既不能包含另一个分组结构，也不能包含在一个分组结构中。

这就是使迄今为止提供的所有解决方案都不可行的部分。为了绕过分组限制，我不得不将 和 into 的检查结合起来，并.在备选方案中分配and ，导致!?[.!?]\b\.

/([.!?])(?<!\bSt\.|\bSgt\.|\bRev\.|\bLtd\.|\bInc\.|\bLt\.|\bJr\.|\bSr\.|\bEsq\.|\bInst\.|\bHon\.|\bGen\.|\bCpl\.|\bComdr\.|\bCol\.|\bCorp\.|\bMr\.|\bDr\.|\bGov\.|\bMrs\.|\bMs\.|\b[A-Z]\.|\bAssn\.|\bCapt\.)(?:\s*$|\s+(?:[_$#]|[A-Z][^.]))/

这使探测计数达到2208，这仍然比您开始时要好一个数量级。对于您的几 GB 文本，这是否足够快，我不知道。

编辑：在您的评论中，您建议按长度对标题进行分组，但没有奏效。但是，更进一步，我将这些组中的每一个放在自己的后面，并且（令我惊讶的是）这似乎确实有效。以下是它在自由间距模式下的外观：

/(?:
   \.
     (?<!\bComdr\.)
     (?<!(?=\b[A-Z])(?:Assn|C(?:apt|orp)|Inst)\.)
     (?<!(?=\b[A-Z])(?:C(?:ol|pl)|Esq|G(?:en|ov)|Hon|Inc|Ltd|Mrs|Rev|Sgt)\.)
     (?<!(?=\b[A-Z])(?:Dr|Jr|Lt|M[rs]|S[rt])\.)
     (?<!\b[A-Z]\.)
   |
   [!?]
 )
 (?:\s*$|\s+(?:[_$#]|[A-Z][^.]))
/x

要查看它的实际效果，请查看ideone.com 上的 PHP 演示。

于 2010-10-19T08:56:35.343 回答