反转正则表达式

2001年5月1日，作者：Pete Sergeant

正则表达式可以说是Perl最有用和最强大的工具之一。匹配复杂字符串的能力是使Perl成为有效的“实用提取和报告语言”的原因之一。正则表达式引擎高度优化，因此非常快，尽管在某些情况下，人们没有以最有效的方式使用它。

例如，想象一下，你有一组来自日志文件的非常长的行，每行在接近末尾的地方都有一个以19开头的四位年份。

人们通常会这样说

# Match any occurrence of 19xx that's not followed by another one
if ($string =~ /(19\d\d)(?!.*19\d\d)/) {$date = $1}

or, better:

if ($string =~ /.*(19\d\d)/) {$date = $1}

然而，在这种情况下，正则表达式引擎必须遍历整个字符串，记住它找到的任何匹配项，并在找到新匹配项时丢弃它们，直到达到字符串的末尾。如果你有很长的日志行，这可能会非常低效，并且相对较慢。但是，有没有其他方法可以做到这一点？（提示：在Perl中，总有一种以上的方法可以做到这一点）

除非你是IRC或perlmonks.com的常客，或者参加了YAPC::Europe，否则你很可能从未听说过（a）Jeff Pinyan（又名Japhy）以及（b）他解决这个问题的简单而优雅的解决方案。他将这些解决方案称为反转正则表达式或sexeger。

与其遍历整个字符串寻找最后一个匹配项，不如从字符串的末尾开始工作，并取找到的第一个匹配项，这不是更好吗？目前，Perl没有提供内置的方法来做这个，但模拟一个却出奇地容易。用Mr. Pinyan为我写的闪电谈话来说，“反转输入！反转正则表达式！反转匹配！”

所以这就是我们要做的

sub get_date {
    $_ = scalar reverse($_[0]); # Reverse whatever string we were passed
    /(\d\d91)/;                 # Look for the first occurrence of a xx91 (19xx reversed)
    return scalar reverse $1;   # Reverse back whatever we found and return it
}

显然，我们在这个例子中执行了两个额外的函数，两次调用reverse。然而，reverse似乎非常高效，在进行的基准测试中（详情见下文），这似乎不是一个问题。为了测试这实际上是否会显著更快，我使用了一个10,000字符的字符串，并对其进行了10,000次正则表达式匹配。这是测试所使用的代码

$la = [our 10000 character string]
...
use Benchmark;
$t = timeit("10000",  sub { $_ = $la; /.*(19\d\d)/; });
print "Greedy took:",timestr($t), "\n";
$t = timeit("10000",  sub { $_ = $la; /(19\d\d)(?!.*19\d\d)/;});
print "Lookahead took:",timestr($t), "\n";
$t = timeit("10000",  sub { $_ = reverse($la); /(\d\d91)/;  });
print "Sexeger took:",timestr($t), "\n";

第一个例子，由于其前瞻断言，耗时四百秒，因为前瞻断言是一个主要的时间消耗点。第二个例子耗时1.5秒。然而，反转方法设法减少了3/4秒，变成了0.75秒。总结一下

然而，性能提升并不是反转正则表达式唯一的好用途，因为人们还可以使用它们来解决Perl难以处理的几个其他常见问题。如果你已经阅读了Perl附带的一些常见问题，我确信你已经读过，那么你会在第5节（perldoc perlfaq5）中看到Andrew Johnson的一个特别好的例子——“我如何输出带有逗号的数字？”

sub commify {
my $input = shift;
$input = reverse $input;
$input =~ s<(\d\d\d)(?=\d)(?!\d*\.)><$1,>g;
return scalar reverse $input;
}

我最喜欢的正则表达式工具之一是零宽先行断言，正如第一个示例中所示（值得注意的是，这是一个负零宽先行断言）。对于那些没有仔细阅读perldoc perlre的人来说，这允许你声明一个模式必须位于你的位置之前，而实际上并不匹配它。也许一个例子可以更好地说明：/ab(?=.+e)cd/将匹配"abcde"，但不会匹配"abecd"或"abcd"。遗憾的是，当前的正则表达式引擎无法执行可变长度的零宽后行断言。然而，如果我们应用Anthony Guselnikov提出的sexeger原则，它突然变得很容易。如果我们想要匹配字符串"def"，只要它之前有字母‘a’，我们可以说

sub nlba {
$_ = scalar reverse $_[0];
print "Success\n" if /fed(?=.*a)/;
}

反转正则表达式是任何程序员工具箱中的一种强大而有效的工具。我希望我已经成功地说明了这种简单而优雅的解决方案的实用性。使用它们需要程序员时间和处理时间的开销，因此我建议你根据具体情况评估使用它们。

更多信息，请访问主页：http://www.pobox.com/~japhy/sexeg er