5

我刚开始使用 perl 中的正则表达式。在玩过各种在线教程之后，我想写一个匹配顺序指定不区分大小写的单词匹配的正则表达式。

我正在尝试确定字符串“A”是否由一个单词或字符串“B”的单词序列组成，并且我想不区分大小写地执行此操作。

例如，如果字符串“B”是“John Von Neumann”，那么“JOhn”、“Von NeumaNn”、“VoN”、“john neuMann”将是一个匹配项，但是像“Joh”、“NeuMann VoN”这样的字符串， “Vonn”不会匹配。

我不确定如何使用正则表达式来做到这一点，知道吗？

4

2 回答 2

9

让我们暂时忽略大小写。

John Von Neumann

可以匹配

John Von Neumann    1 1 1
John Von            1 1 0
John     Neumann    1 0 1
John                1 0 0
     Von Neumann    0 1 1
     Von            0 1 0
         Neumann    0 0 1

所以你正在寻找的正则表达式模式是

/^(?:John Von Neumann|John Von|John Newmann|John|...)\z/i

以下是构建列表的方法：

sub true_indexes {
   my ($n) = @_;
   my $i = 0;
   my @indexes;
   while ($n) {
      push @indexes, $i if $n & 1;
      ++$i;
      $n >>= 1;
   }
   return @indexes;
}

my @words = split(' ', 'John Von Neumann');

my @patterns;
unshift @patterns, join ' ', @words[ true_indexes($_) ]
   for 1 .. (2**@words)-1;

最后，我们可以生成模式：

my $pat = join '|', map quotemeta, @patterns;
my $re = qr/$pat/i;

你会像这样使用它：

if ($input =~ /^$re\z/) {
   print "match\n";
} else {
   print "no match\n";
}
于 2013-02-10T18:25:07.763 回答
3

ikegami的解决方案会占用指数空间for来存储字符串在变成正则之前（每个单词会出现2 n - 1次，其中n是单词的个数，所以总空间至少是2 n - 1 * Sum （字长））。这与正则表达式引擎无关- 因为问题出在字符串转换为正则表达式之前。

与 ikegami 的解决方案等效的正则表达式构造（就其匹配的字符串集而言）将是：

^(?=[^ ])(?:(?: |^)John(?= |\z))?+(?:(?: |^)Von(?= |\z))?+(?:(?: |^)Neumann(?= |\z))?+\z

就单词数和所有单词的总长度而言，这只占用线性空间。

为了清楚起见：

^
(?=[^ ])
(?:(?: |^)John(?= |\z))?+
(?:(?: |^)Von(?= |\z))?+
(?:(?: |^)Neumann(?= |\z))?+
\z

前瞻断言(?=[^ ])有两个目的：防止空字符串被匹配，并确保第一个字符不是空格字符。

注意?+，它使量词具有所有格（或原子），因为我们在这里不需要回溯。为什么？如果我们要正常执行此操作，我们将遍历单词列表并将其与输入中最左边的单词进行比较。找到匹配项后，我们将继续循环以将其与输入中的下一个单词进行比较，直到找到输入中的所有单词或我们完成了单词列表的循环。

所有格量词还可以防止回溯地狱的发生。如果一个词被认为是匹配的，它将永远不会被重新考虑。

对于每个单词，它们前面可以有一个空格，或者它是字符串的开头。前瞻断言(?= |\z)的目的是确保具有相同前缀的单词在第一次尝试时不会被错误地匹配（例如"John Von Vone"，尝试匹配"John Vone"）。

由于没有回溯，因此最坏情况下的性能在所有单词的长度和输入字符串的长度方面是线性的（与没有正则表达式的情况相同）。

我们可以稍微改变一下正则表达式以允许灵活的间距：

^(?= *+[^ ])(?: *+John(?= |\z))?+(?: *+Von(?= |\z))?+(?: *+Neumann(?= |\z))?+ *+\z

为清楚起见（前导空格很重要）：

^
(?= *+[^ ])
(?: *+John(?= |\z))?+
(?: *+Von(?= |\z))?+
(?: *+Neumann(?= |\z))?+
 *+
\z

(?= *+[^ ])开头的前瞻确保输入字符串不只包含空格。

正则表达式已更改为允许在单词前有任意数量的空格（所有格量词不允许回溯）。使用0 个或多个量词*，因为单词正好在字符串的开头。由于前瞻断言，两个单词没有发生冲突的机会(?= |\z)。

在构造字符串时（在将其输入到正则表达式引擎之前），它仍然占用线性空间。最坏情况下的性能也是线性的。

极端情况

  1. 原话：

    aaaaaaaaaaaaaaaaaaa0 aaaaaaaaaaaaaaaaaaa1 ... aaaaaaaaaaaaaaaaaaa9 aaaaaaaaaaaaaaaaaaaa ... aaaaaaaaaaaaaaaaaaaz aaaaaaaaaaaaaaaaaaaA ... aaaaaaaaaaaaaaaaaaaZ

    （每个单词20个字符，最后一个字符由0-9、then a-z、then变化A-Z）

    要搜索的字符串（不匹配）：

    aaaaaaaaaaaaaaaaaaaz aaaaaaaaaaaaaaaaaaay

    （y只能先来z）

  2. 原话：

    patterns used in Perl pattern matching evolved from those supplied

    （一些普通话）

    要搜索的字符串（不匹配）：

    patterns used in Perl pattern matching evolved from those suppliedd

    （d最后补充）

  3. 原话：

    aaaaaaaaaaaa aaaaaaaaaaa aaaaaaaaaa aaaaaaaaa aaaaaaaa aaaaaaa aaaaaa aaaaa aaaa

    （Word 仅包含a，长度不同。）

    要搜索的字符串（不匹配）：

    aaaaaaaaaaaa aaaaaaaaaaa aaaaaaaaaa aaaaaaaaa aaaaaaaa aaaaaaa aaaaaa aaaaa aaaaa

    （a最后补充）

  4. 原话：

    performance abc xyz performance 456 !@# performance

    （同一个词出现多次）

    要搜索的字符串（不匹配）：

    performance performance performance performance
于 2013-02-11T11:21:06.220 回答