Извлекайте только те слова из списка, которые не содержат повторяющихся букв, используя регулярные выражения - PullRequest
2 голосов
/ 12 апреля 2011

У меня большой файл списка слов с одним словом в строке. Я хотел бы отфильтровать слова с повторяющимися алфавитами.

INPUT:
  abducts
  abe
  abeam
  abel
  abele

OUTPUT:
  abducts
  abe
  abel

Я бы хотел сделать это с помощью Regex (grep, perl или python). Это возможно?

Ответы [ 10 ]

7 голосов
/ 12 апреля 2011

Гораздо проще написать регулярное выражение, совпадающее со словами, которые do имеют повторяющиеся буквы, а затем отменить совпадение:

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

(В этом коде предполагается, что @input содержит по одному слову в каждой записи.) Но эту проблему не обязательно лучше всего решить с помощью регулярного выражения.

Я дал код на Perl, но его можно легко перевести в любой вариант регулярного выражения, который поддерживает обратные ссылки, включая grep (который также имеет переключатель -v для отмены соответствия).

5 голосов
/ 12 апреля 2011
$ egrep -vi '(.).*\1' wordlist
3 голосов
/ 12 апреля 2011

Простой материал

Несмотря на неточное утверждение, что это невозможно с помощью регулярных выражений, это, безусловно, так.

Хотя @cjm справедливо заявляет, что намного проще отрицать положительное совпадение, чем выражать отрицательное в качестве единого шаблона, модель для этого достаточно известна, так что это становится просто вопросом подключения вещи в эту модель. Учитывая, что:

    /X/

соответствует чему-то, то способ выражения условия

    ! /X/

в одном, положительно совпадающем шаблоне - записать его как

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

Следовательно, учитывая, что положительный паттерн равен

    / (\pL) .* \1 /sxi

соответствующие отрицательные потребности должны быть

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

путем простой замены X.

Реальные проблемы

Тем не менее, существуют смягчающие проблемы, которые иногда могут требовать дополнительной работы. Например, хотя \pL описывает любую кодовую точку, имеющую свойство GeneralCategory = Letter , он не учитывает, что делать со словами, такими как красный-фиолетовый , ' Это не , или невеста - последний из которых отличается в других эквивалентных 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} эквивалентными элементами или различными.

Это потому, что правильно написанные дефисы двух элементов, таких как красный фиолетовый и цветной , образуют одно составное слово красный фиолетовый , где, по крайней мере, одна из пары уже содержит дефис , требует, чтобы в качестве разделителя использовался EN DASH вместо простого HYPHEN.

Обычно EN DASH зарезервирован для соединений подобной природы, таких как компромисс между временем и пространством . Люди, использующие пишущую машинку - английский даже не делают этого, хотя и используют этот сверхнормативно перегруженный устаревший код HYPHEN-MINUS для обоих: красно-фиолетового цвета .

Это просто зависит от того, был ли ваш текст написан на какой-то ручной пишущей машинке 19-го века или представляет собой текст на английском языке, правильно отрисованный по современным правилам набора текста. :)

сознательная нечувствительность к регистру

Вы заметите, что я здесь рассматриваю письмо, которое отличается только в том случае, если оно совпадает. Это потому, что я использую /i переключатель регулярных выражений, (?i) модификатор шаблона.

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *1078* * * * * * * * * *1078* * * * * * * * * * * * * * * * * * по крайней мере *1078*. 1082 *) для совпадений без учета регистра, а не какой-либо более высокой силы сопоставления, чем третичный уровень, что может быть предпочтительным.

Полная эквивалентность по первичной силе сопоставления является значительно более сильным утверждением, но оно вполне может потребоваться для полного решения проблемы в общем случае. Тем не менее, , что требует гораздо больше работы, чем та, которая требуется во многих конкретных случаях. Короче говоря, для многих конкретных случаев это избыточно, независимо от того, сколько это может понадобиться для гипотетического общего случая.

Это стало еще сложнее, потому что, хотя вы можете, например, сделать это:

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

Это показывает, почему, когда вам нужно сопоставить букву, вы должны alwasy использовать \pL ᴀᴋᴀ \p{Letter} вместо \w, что на самом деле соответствует [\p{alpha}\p{GC=Mark}\p{NT=De}\p{GC=Pc}].

Конечно, когда вам нужно соответствовать буквенному алфавиту, вам нужно использовать \p{alpha} ᴀᴋᴀ \p{Alphabetic}, что совсем не то же самое, что простое письмо - вопреки распространенному заблуждению. :)

3 голосов
/ 12 апреля 2011

Можно использовать регулярное выражение:

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))
2 голосов
/ 13 апреля 2011

Мне было очень любопытно относительно относительной скорости различных методов на основе 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" является самым быстрым на сегодняшний день. Это на 180% быстрее, чем следующий самый быстрый метод, метод NextIfSeen от ikegami. Я подозреваю, что относительная скорость методов RegExp и NextIfSeen будет сходиться при увеличении средней длины входных строк. Но для английских слов «нормальной» длины метод RegExp является самым быстрым.

2 голосов
/ 12 апреля 2011

Если вы имеете дело с длинными строками, которые могут содержать повторяющиеся буквы, остановка как можно скорее может помочь.

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

Я бы выбрал самое простое решение, если производительность не будет признана неприемлемой.

my @output = grep !/(.).*?\1/s, @input;
1 голос
/ 13 апреля 2011

В питоне с регулярным выражением:

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

Очевидно, что регулярное выражение немного медленнее, чем простое создание frozenset и сравнение len в python.

1 голос
/ 12 апреля 2011

В ответ на решение 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.
}
1 голос
/ 12 апреля 2011

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";
    }
}
0 голосов
/ 12 апреля 2011

Вы не можете сделать это с Regex.Regex - это конечный автомат, и для этого потребуется стек для хранения увиденных букв.

Я бы предложил сделать это с помощью 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
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...