正则表达式查找不连续的重复单词（即在字符串中出现不止一次）

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".

我在 Internet 上搜索过这样的正则表达式，但无济于事。有人会认为这将是所有关于“使用正则表达式查找重复项”的问题，但他们都只谈论相邻的词，如“the the”。

Answer 1

下面的demo代码或许更容易理解

use strict;
use warnings;
use feature 'say';

my $text = do { local $/, <DATA> };

my(%count,@found,$regex);

$count{$_}++ for split '[ .,?]', $text;
$count{$_} > 1 && push @found, $_ for keys %count;
$regex  = join('|',@found);

say 'Before: ' . $text;
$text =~ s/\b($regex)\b/<>/g;
say 'After: ' . $text;

__DATA__
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.

输出

Before: 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.
After: 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>.

Answer 2

您需要以下内容：

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

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

您没有指定正则表达式引擎，但我想不出任何支持 variable-width 回顾的引擎。^[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) 的字数。

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

假设您有一个包含 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

Answer 3

使用正则表达式完成关键部分的一种方法是使用允许在正则表达式内执行代码的功能来构建频率哈希（映射、字典）。然后可以用于 select 重复的单词。

仅使用正则表达式而不使用任何语言或工具来完成这一切是不可能的（除非在支持的情况下使用递归）。 post 的其余部分在允许在正则表达式中执行代码的正则表达式功能的上下文中使用了编程语言的基础知识。

我认为大多数引擎都可以使用的一个功能是运行编码以准备替换字符串。我将 Perl 用于以下简短示例。这里有趣的是使用副作用完成的，当然不是最佳的（并且通常会导致看起来笨拙的代码）。

或者运行正常替换并放回匹配的词

$string =~ s/(\w+)/++$freq{}; /eg;

或使用“non-destructive”替换，它不会更改目标（如果匹配失败，returns 更改的字符串或原始字符串）

my $toss = $string =~ s/(\w+)/++$freq{}/egr;

所描述的任务不需要返回的字符串。在这两种情况下，我们运行当这不是我们真正需要的时候，我们对每个词进行替换。

然后打印频率大于1的键（词）

foreach my $word (keys %freq) { say $word if $freq{$word} > 1 }

正则表达式匹配每个 \w 个字符的“单词”class；根据您的需要进行调整。

总而言之，由于这对正则表达式来说是一项棘手的任务，我建议将字符串拆分为单词并使用您的语言的功能计算重复项，而不是推送正则表达式。任何称职的语言都可以优雅而高效地做到这一点。

对于 Perl，另一种方法是使用 embedded code construct，它允许代码在匹配部分运行。据我所知，这在其他语言中是不可用的，除了一些图书馆。

可以运行在匹配部分编码

my @matches = $string =~ /(\w+)(?{++$freq{}})/g;

其中构造 (?{code}) 将执行嵌入式代码，此处构建频率哈希。（安全地）使用此功能需要仔细阅读文档。

上面的@matches有所有个词，与所述问题无关；它在这里用于将正则表达式的匹配运算符放在“列表上下文”中，以便通过 /g 修饰符继续搜索字符串。

正则表达式查找不连续的重复单词（即在字符串中出现不止一次）

Regex to find inconsecutive duplicate words (i.e. occurs more than once in a string)

regex

language-agnostic

duplicates