不区分大小写的有序单词搜索（基于正则表达式）

Question

我刚开始接触Perl中的正则表达式。在尝试各种在线教程后，我想编写一个正则表达式，它可以匹配指定顺序但不区分大小写。

我的目标是确定字符串“A”是否由字符串“B”的一个单词或一组单词组成，并且我希望不区分大小写。

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

我不确定如何使用正则表达式实现这一点，有什么想法吗？

- Quixotic

---

@ogzd发布了/^(?=.)(?:\bjohn\b)?\s*(?:\bvon\b)?\s*(?:\bneumann\b)?\z/i（在一些帮助下）。我不确定为什么他删除了它。这不是通用解决方案，但OP可能不需要通用解决方案。 - ikegami

@ikegami: (?=.) 需要改为 (?=\S)，否则模式将匹配一串空格。 - Borodin

Answer 1

先不考虑大小写的问题。

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";
}

- ikegami

---

@kamata 很好地使用了 Perl 语法。 - Déjà vu

我认为ogzd的解决方案比这个更好，如果用作构建通用正则表达式的基础。对于较长的短语，此解决方案将构建一个庞大的正则表达式（DFA可以缩小，但正则表达式庞大的事实不会改变）。不确定为什么这会得到如此多的赞。 - nhahtdh

@nhahtdh，ogzd的解决方案不能用于构建通用正则表达式。它只能通过^..\z和^..$进行匹配，因为它可以匹配空字符串。此外，您关于大小的看法是错误的。正则表达式引擎将为交替创建一个trie，这将减少所需的时间和内存到“无”。最后，我的解决方案更快，因为他的解决方案可能会进行大量回溯。 - ikegami

正则表达式引擎是一回事（实现可能对这种简单情况实现了高效的匹配方式），但在将字符串提供给正则表达式引擎之前，该字符串可能非常大。而且由于单词是有序的，因此可以使用可选运算符来进行匹配。 - nhahtdh

@ikegami：你说的对，ogzd 的答案容易陷入回溯地狱。不过，我关于字符串大小的观点仍然成立。我已经写了一个答案来解决这个问题。 - nhahtdh

Answer 2

ikegami的解决方案将占用指数空间来存储在将字符串转换为正则表达式之前的字符串（每个单词将出现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) 的存在，没有2个单词会发生碰撞。

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

---

极端情况

1. The original words:

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

   (Each word is 20 characters, the last character changes from 0-9, then a-z, then A-Z)

   Strings to search for (not matching):

   aaaaaaaaaaaaaaaaaaaz aaaaaaaaaaaaaaaaaaay
   

   (y can only come before z)

2. The original word:

   patterns used in Perl pattern matching evolved from those supplied
   

   (Some normal words)

   Strings to search for (not matching):

   patterns used in Perl pattern matching evolved from those suppliedd
   

   (Extra d at the end)

3. The original word:

   aaaaaaaaaaaa aaaaaaaaaaa aaaaaaaaaa aaaaaaaaa aaaaaaaa aaaaaaa aaaaaa aaaaa aaaa
   

   (Word contains only a, with different length.)

   Strings to search for (not matching):

   aaaaaaaaaaaa aaaaaaaaaaa aaaaaaaaaa aaaaaaaaa aaaaaaaa aaaaaaa aaaaaa aaaaa aaaaa
   

   (Extra a at the end)

4. The original word:

   performance abc xyz performance 456 !@# performance
   

   (Same word appearing multiple times)

   Strings to search for (not matching):

   performance performance performance performance
   

- nhahtdh