正则表达式查找不连续的重复单词(即在字符串中出现多次)

Question

什么是正则表达式，它可以查找在字符串中多次出现的所有单词的所有实例(不一定连续出现)？

例如，在字符串中:

How much wood could a woodchuck chuck if a woodchuck could chuck wood?A woodchuck would chuck all the wood he could chuck if a woodchuck could chuck wood.

它会找到重复单词的每个实例；在上面的示例中，它将找到以下单词:"wood","could","a","woodchuck","chuck","if"。

我在互联网上搜索了这样的正则表达式，但没有成功。人们可能会认为这就是所有关于“使用正则表达式查找重复项”的问题所讨论的内容，但它们都只讨论诸如“the the”之类的相邻单词。

Answer 1

您需要以下内容:

\b\w+\b
(?: (?= .* \b(\1)\b )
|   (?<= \b\1\b .* \1 )
)

(确保.可以匹配您正在使用的引擎中的任何字符。根据需要进行调整。)

您尚未指定正则表达式引擎，但我想不出任何支持可变宽度lookbehinds的引擎。^[1]然而，这是实现您想要的目标所必需的。

它也非常慢，就单词而言需要 O(N^2) 时间。^[2]

---

好的，有人表明 Variable-Length Lookbehinds: actually possible in Perl/PCRE!他们使用递归一次后退一个字符。玩得开心。

---

通常会使用两遍，一次用于查找重复项，另一次用于“查找”。

my %seen;
my @dups = grep ++$seen{$_} == 2, $file =~ /\w+/g;
my $alt = join "|", @dups;
$file =~ s/\b($alt)\b/<$&>/g;

就单词而言，这是 O(N)。

---

1. 从技术上讲，从 Perl 5.30 开始，lookbehinds“作为实验性功能可以处理 1 到 255 个字符的可变长度”。这对于OP来说太小了，OP在现已删除的评论中谈到了GB。

2. 想象一下您有一个包含 N 个单词的文档，每个单词都不同。

   • 单词 1 需要与后面的 N-1 个单词和前面的 0 个单词进行比较。
   • 单词 2 需要与后面的 N-2 个单词和前面的 1 个单词进行比较。
   • ...
   • 需要将单词 N-1 与后面的 1 个单词和前面的 N-2 个单词进行比较。
   • 单词 N 需要与后面的 0 个单词和前面的 N-1 个单词进行比较。

     O( (N-1)+0 + (N-2)+1 + ... + 1+(N-2) + 0+(N-1) )
   = O( [ (N-1)+(N-2)+...+1+0 ] + [ 0+1+...+(N-2)+(N-1) ] )
   = O( [ 0+1+...+(N-2)+(N-1) ] * 2 )
   = O( 1+...+(N-2)+(N-1) )               # Constant factors irrelevant in O()
   = O( (N-1) * ((N-1)+1) / 2 )           # 1+2+..x == x*(x+1)/2
   = O( (N-1) * N / 2 )
   = O( (N-1) * N )                       # Constant factors irrelevant in O()
   = O( N^2 - N )
   = O( N^2 )                             # An N term is subsumed by a N^2 term