使用正则表达式仅从列表中提取不包含重复字母的单词

Question

我有一个很大的单词列表文件，每行一个单词。我想过滤掉重复字母的单词。

INPUT:
  abducts
  abe
  abeam
  abel
  abele

OUTPUT:
  abducts
  abe
  abel

我想使用正则表达式（grep 或 perl 或 python）来做到这一点。这可能吗？

Answer 1

编写一个正则表达式来匹配具有重复字母的单词，然后否定匹配要容易得多：（

my @input = qw(abducts abe abeam abel abele);
my @output = grep { not /(\w).*\1/ } @input;

此代码假设 @input 每个条目包含一个单词。）但这个问题不一定能通过正则表达式得到最好的解决。

我已经在 Perl 中给出了代码，但它可以很容易地转换为任何支持反向引用的正则表达式风格，包括 grep （它也有 -v 开关来否定匹配）。

Answer 2

$ egrep -vi '(.).*\1' wordlist

Answer 3

可以使用正则表达式：

import re

inp = [
    'abducts'
,   'abe'
,   'abeam'
,   'abel'
,   'abele'
]

# detect word which contains a character at least twice
rgx = re.compile(r'.*(.).*\1.*') 

def filter_words(inp):
    for word in inp:
        if rgx.match(word) is None:
            yield word

print list(filter_words(inp))

Answer 4

简单的东西

尽管有不准确的说法称这对于正则表达式是不可能的，但它确实是不可能的。

虽然 @cjm 公正地指出，否定正匹配比将负匹配表示为单个模式要容易得多，但这样做的模型已经足够众所周知，以至于只需将一些东西插入该模式即可模型。假设：

    /X/

表达条件的方法

    ! /X/

匹配某些东西，那么以单个正匹配模式

    /\A (?: (?! X ) . ) * \z /sx

是将其写为因此，鉴于正模式是

    / (\pL) .* \1 /sxi

相应的负需求，必须

    /\A (?: (?! (\pL) .* \1  ) . ) * \z /sxi

通过简单替换 X 来 实现.

现实世界的担忧

尽管如此，有些令人情有可原的担忧有时可能需要更多的工作。例如，虽然 \pL 描述具有 GeneralCategory=Letter 属性的任何代码点，但它不考虑如何处理诸如 red‐violet–colored< /em>、'Tisn't 或 fiancée — 后者在其他等效的 NFD 与 NFC 形式中有所不同。

因此，您必须首先通过完全分解来运行它，以便像 "r\x{E9}sume\x{301}" 这样的字符串能够正确检测重复的“字母 é's”——即所有规范等效的字素簇单元。

为了解决这些问题，您至少必须首先通过 NFD 分解运行字符串，然后还通过 \X 使用字素簇，而不是通过 .< /代码>。

因此，对于英语，您需要遵循这些正匹配的内容，并根据上面给出的替换进行相应的负匹配：

    NFD($string) =~ m{
        (?<ELEMENT>
           (?= [\p{Alphabetic}\p{Dash}\p{Quotation_Mark}] ) \X 
        )
        \X *
        \k<ELEMENT>
    }xi

但即使如此，仍然存在某些未解决的未解决问题，例如是否 \ N{EN DASH} 和 \N{HYPHEN} 应被视为等效元素或不同元素。

这是因为正确的书写方式，将两个元素如 red-violet 和 colored 连接起来形成单个复合词 red-violet-colored，其中至少其中一个已经包含连字符，要求使用 EN DASH 作为分隔符，而不仅仅是连字符。

通常，EN DASH 保留用于类似性质的化合物，例如时空权衡。然而，使用打字机英语的人甚至不会这样做，他们使用超大规模重载的遗留代码点连字符减号来表示两者：红紫色。

这仅取决于您的文本是否来自 19 世纪的手动打字机，或者它是否代表在现代排版规则下正确呈现的英语文本。 :)

认真区分大小写

您会注意到，我在这里将仅大小写不同的字母视为同一字母。这是因为我使用 /i 正则表达式开关，ᴀᴋᴀ (?i) 模式修饰符。

这相当就像说它们与排序规则强度1相同 - 但又不完全一样，因为Perl仅使用大小写折叠（尽管完整大小写折叠并不简单) 对于不区分大小写的匹配，而不是比三级更高的排序规则强度，这可能是首选。

主要校对强度的完全等价是一种明显更强的说法，但在一般情况下可能需要这种说法才能完全解决问题。然而，在许多特定情况下，这需要比解决问题所需的工作多得多的工作。简而言之，对于实际出现的许多具体情况来说，它是多余的，无论假设的一般情况需要多少。

这变得更加困难，因为尽管你可以这样做：

    my $collator = new Unicode::Collate::Locale::
                       level => 1, 
                       locale => "de__phonebook",
                       normalization => undef,
                    ;

    if ($collator->cmp("müß", "MUESS") == 0) { ... }

并期望得到正确的答案 - 你确实得到了，万岁！ - 这种强大的字符串比较不容易扩展到正则表达式匹配。

然而。 :)

总结

选择是设计不足还是过度设计解决方案将根据个人情况而有所不同，没有人可以为您做出决定。

我喜欢 CJM 的解决方案，它否定了正匹配，尽管它对于重复字母的判断有些漫不经心。注意：

    while ("de__phonebook" =~ /(?=((\w).*?\2))/g) {
        print "The letter <$2> is duplicated in the substring <$1>.\n";
    } 

产生：

    The letter <e> is duplicated in the substring <e__phone>.
    The letter <_> is duplicated in the substring <__>.
    The letter <o> is duplicated in the substring <onebo>.
    The letter <o> is duplicated in the substring <oo>.

这说明了为什么当您需要匹配字母时，您应该始终使用 \pL ᴀᴋᴀ \p{Letter} 而不是\w，实际上匹配 [\p{alpha}\p{GC=Mark}\p{NT=De}\p{GC=Pc}]。

当然，当你需要匹配字母时，你需要使用 \p{alpha} ᴀᴋᴀ\p{Alphabetic}，它与只是一封信——与普遍的误解相反。 :)

Answer 5

如果您正在处理可能包含重复字母的长字符串，尽快停止可能会有所帮助。

INPUT: for (@input) {
   my %seen;
   while (/(.)/sg) {
      next INPUT if $seen{$1}++;
   }
   say;
}

我会采用最简单的解决方案，除非发现性能确实不可接受。

my @output = grep !/(.).*?\1/s, @input;

Answer 6

我很好奇其他作者针对这个问题提交的各种基于 Perl 的方法的相对速度。所以，我决定对它们进行基准测试。

必要时，我稍微修改了每个方法，以便它填充一个 @output 数组，以保持输入和输出一致。我验证了所有方法都会产生相同的 @output，尽管我没有在此处记录该断言。

以下是对各种方法进行基准测试的脚本：

#!/usr/bin/perl

use strict;
use warnings;

use Benchmark qw(cmpthese :hireswallclock);

# get a convenient list of words (on Mac OS X 10.6.6, this contains 234,936 entries)
open (my $fh, '<', '/usr/share/dict/words') or die "can't open words file: $!\n";
my @input = <$fh>;
close $fh;

# remove line breaks
chomp @input;

# set-up the tests (
my %tests = (

  # Author: cjm
  RegExp => sub { my @output = grep { not /(\w).*\1/ } @input },

  # Author: daotoad
  SplitCount => sub { my @output = grep { my @l = split ''; my %l; @l{@l} = (); keys %l == @l } @input; },

  # Author: ikegami
  NextIfSeen => sub {
    my @output;
    INPUT: for (@input) {
      my %seen;
      while (/(.)/sg) {
        next INPUT if $seen{$1}++;
      }
      push @output, $_;
    }

  },

  # Author: ysth
  BitMask => sub {
    my @output;
    for my $word (@input) {
      my $mask1 = $word x ( length($word) - 1 );
      my $mask2 = join( '', map { substr($word, $_), substr($word, 0, $_) } 1..length($word)-1 );
      if ( ( $mask1 ^ $mask2 ) !~ tr/\0// ) {
        push @output, $word;
      }
    }
  },

);

# run each test 100 times
cmpthese(100, \%tests);

以下是 100 次迭代的结果。

           s/iter SplitCount    BitMask NextIfSeen     RegExp
SplitCount   2.85         --       -11%       -58%       -85%
BitMask      2.54        12%         --       -53%       -83%
NextIfSeen   1.20       138%       113%         --       -64%
RegExp      0.427       567%       496%       180%         --

正如您所看到的，cjm 的“RegExp”方法是迄今为止最快的。它比第二快的方法（ikegami 的“NextIfSeen”方法）快 180%。我怀疑 RegExp 和 NextIfSeen 方法的相对速度会随着输入字符串的平均长度的增加而收敛。但对于“正常”长度的英语单词，RegExp 方法是最快的。

Answer 7

cjm 给出了正则表达式，但这是一个有趣的非正则表达式方式：

@words = qw/abducts abe abeam abel abele/;
for my $word (@words) {
    my $mask1 = $word x ( length($word) - 1 );
    my $mask2 = join( '', map { substr($word, $_), substr($word, 0, $_) } 1..length($word)-1 );
    if ( ( $mask1 ^ $mask2 ) !~ tr/\0// ) {
        print "$word\n";
    }
}

Answer 8

为了回应 cjm 的解决方案，我想知道它与一些相当简洁的 Perl 相比如何：

my @output = grep { my @l = split ''; my %l; @l{@l} = (); keys %l == @l } @input;

因为我在这里不受字符数和格式的限制，所以我会更清楚一点，甚至到过度记录的程度：

my @output = grep {

    # Split $_ on the empty string to get letters in $_. 
    my @letters = split '';

    # Use a hash to remove duplicate letters.
    my %unique_letters;
    @unique_letters{@letters} = ();  # This is a hash slice assignment.
                                     # See perldoc perlvar for more info

    # is the number of unique letters equal to the number of letters?
    keys %unique_letters == @letters

} @input;

并且，当然在生产代码中，请执行以下操作：

my @output = grep ! has_repeated_chars($_), @input;

sub has_repeated_letters {
    my $word = shift;
    #blah blah blah
    # see example above for the code to use here, with a nip and a tuck.
}

Answer 9

在带有正则表达式的 python 中：

python -c 'import re, sys; print "".join(s for s in open(sys.argv[1]) if not re.match(r".*(\w).*\1", s))' wordlist.txt

在没有正则表达式的 python 中：

python -c 'import sys; print "".join(s for s in open(sys.argv[1]) if len(s) == len(frozenset(s)))' wordlist.txt

我使用硬编码的文件名执行了一些计时测试，并将输出重定向到 /dev/null 以避免在计时中包含输出：

没有正则表达式的计时：

python -m timeit 'import sys' 'print >> sys.stderr, "".join(s for s in open("wordlist.txt") if len(s) == len(frozenset(s)))' 2>/dev/null
10000 loops, best of 3: 91.3 usec per loop

带有正则表达式的计时：

python -m timeit 'import re, sys' 'print >> sys.stderr, "".join(s for s in open("wordlist.txt") if re.match(r".*(\w).*\1", s))' 2>/dev/null
10000 loops, best of 3: 105 usec per loop

显然正则表达式比 python 中简单的 freezeset 创建和 len 比较慢一点。

Answer 10

你不能用正则表达式来做到这一点。正则表达式是一个有限状态机，这需要一个堆栈来存储已看到的字母。

我建议使用 foreach 执行此操作，并使用代码手动检查每个单词。
像这样的东西

List chars
foreach word in list
    foreach letter in word
        if chars.contains letter then remove word from list
        else
            chars.Add letter
    chars.clear