regex - 为什么 ^A|bA 比 grep -P 的负向后视慢，而 grep -E 快？

Question

这些是等效的:

grep -E '^A|bA'
grep -P '^A|bA'
grep -P '(?<![^b])A'

但是第二个， grep -P '^A|bA' , 慢了好几倍。为什么？

他们都找到了相同的东西:一行带有 A在 b 的开头或之后. (等效地，带有 A 的行前面没有除 b 之外的任何其他内容。)

第二行是否禁用了一些优化？是否 grep当它认为更快时并行检查多个字符？我想不出另一个解释，除非 ^或 |在 perl 中意味着一些微妙的不同。

Answer 1

如果模式不包含反向引用*，GNU egrep ( grep -E ) 将使用 DFA 引擎； grep -P使用 PCRE 的 NFA 实现。 DFA 引擎从不回溯，而模式 ^A|bA可以触发大量低效的 PCRE 回溯。

PCRE 检查 ^A ，然后 bA , 在字符串中的每个位置，直到找到匹配项。对于直到字符串后期(或根本不匹配)才匹配的大输入，这可能需要很长时间。

您可以通过 pcretest 看到这一点公用事业:

$ pcretest
PCRE version 8.32 2012-11-30

  re> /^A|bA/C
data> bcAbcAbcA
--->bcAbcAbcA
 +0 ^             ^
 +1 ^             A
 +3 ^             b
 +4 ^^            A
 +0  ^            ^
 +3  ^            b
 +0   ^           ^
 +3   ^           b
 +0    ^          ^
 +3    ^          b
 +4    ^^         A
 +0     ^         ^
 +3     ^         b
 +0      ^        ^
 +3      ^        b
 +0       ^       ^
 +3       ^       b
 +4       ^^      A
 +0        ^      ^
 +3        ^      b
 +0         ^     ^
 +3         ^     b
No match

(?<![^b])A更快，因为 PCRE 不是在每个位置都测试匹配，而是直接跳到第一个 A ;如果不匹配，则跳到下一个 A ，依此类推，直到字符串结束:

  re> /(?<![^b])A/C
data> bcAbcAbcA
--->bcAbcAbcA
 +0   ^           (?<![^b])
 +4   ^      ^    [^b]
 +8   ^           )
 +0      ^        (?<![^b])
 +4      ^   ^    [^b]
 +8      ^        )
 +0         ^     (?<![^b])
 +4         ^^    [^b]
 +8         ^     )
 +0          ^    (?<![^b])
 +4          ^    [^b]
 +8          ^    )
No match

有关 DFA 和 NFA 实现之间差异的详细信息，请参阅 Russ Cox 的文章“ Regular Expression Matching Can Be Simple And Fast”。

* 根据 "DFA Speed with NFA Capabilities: Regex Nirvana?"在 Jeffrey Friedl 的 Mastering Regular Expressions 第 182 页上。