Regex dla wszystkich 10-literowych słów z unikalnymi literami

Próbuję napisać wyrażenie regularne, które wyświetli wszystkie słowa o długości 10 znaków i żadna z liter nie będzie się powtarzać.

Do tej pory mam

grep --colour -Eow '(\w{10})'

Która jest pierwszą częścią pytania. Jak miałbym przejść do sprawdzania „wyjątkowości”? Naprawdę nie mam pojęcia, poza tym muszę użyć referencji.

grep -Eow '\w{10}' | grep -v '\(.\).*\1'

nie obejmuje słów, które mają dwa identyczne znaki.

grep -Eow '\w{10}' | grep -v '\(.\)\1'

nie obejmuje tych, które mają powtarzające się postacie.

POSIXly:

tr -cs '[:alnum:]_' '[\n*]' |
   grep -xE '.{10}' |
   grep -v '\(.\).*\1'

trumieszcza słowa we własnej linii, konwertując dowolną srówność znaków niebędących wyrazami ( cuzupełnienie znaków alfanumerycznych i podkreślników) na znak nowej linii.

Lub z jednym grep:

tr -cs '[:alnum:]_' '[\n*]' |
   grep -ve '^.\{0,9\}$' -e '.\{11\}' -e '\(.\).*\1'

(z wyłączeniem wierszy zawierających mniej niż 10 i więcej niż 10 znaków oraz wiersze o znaku pojawiającym się co najmniej dwa razy).

grepTylko jeden (GNU grep z obsługą PCRE lub pcregrep):

grep -Po '\b(?:(\w)(?!\w*\1)){10}\b'

Oznacza to, że granica słowa ( \b), po której następuje sekwencja 10 znaków słów (pod warunkiem, że po każdym nie następuje sekwencja znaków słowa i samych siebie, przy użyciu operatora PCRE o przeczącej przyszłości (?!...)).

Mamy szczęście, że tutaj działa, ponieważ niewiele silników wyrażeń regularnych działa z odwołaniami wstecznymi w powtarzających się częściach.

Zauważ, że (przynajmniej z moją wersją GNU grep)

grep -Pow '(?:(\w)(?!\w*\1)){10}'

Nie działa, ale

grep -Pow '(?:(\w)(?!\w*\2)){10}'

robi (as echo aa | grep -Pw '(.)\2') co brzmi jak błąd.

Może chcesz:

grep -Po '(*UCP)\b(?:(\w)(?!\w*\1)){10}\b'

jeśli chcesz \wlub \brozważasz dowolną literę jako składnik słowa, a nie tylko ASCII w ustawieniach regionalnych innych niż ASCII.

Inna alternatywa:

grep -Po '\b(?!\w*(\w)\w*\1)\w{10}\b'

Jest to granica słów (taka, po której nie następuje ciąg znaków, z których jeden się powtarza), a następnie 10 znaków.

Rzeczy, które mogą mieć na myśli:

• W porównaniu rozróżniana jest Babylonishwielkość liter, więc na przykład pasują, ponieważ wszystkie znaki są różne, mimo że są dwie litery Bs, jedna mała i jedna duża (użyj, -iaby to zmienić).
• o -w, \wa \b, słowo jest literą (ASCII tylko te, dla GNU grep teraz The [:alpha:]klasa znaków w danym regionie czy korzystania -Pi (*UCP)), cyfry dziesiętne lub podkreślenia .
• oznacza to, że c'est(dwa słowa zgodnie z francuską definicją słowa) lub it's(jedno słowo zgodnie z niektórymi angielskimi definicjami słowa) lub rendez-vous(jedno słowo zgodnie z francuską definicją słowa) nie są uważane za jedno słowo.
• Mimo to (*UCP)znaki łączące Unicode nie są uważane za składniki słowa, więc téléphone( $'t\u00e9le\u0301phone') jest uważane za 10 znaków, z których jeden nie jest alfa. défavorisé( $'d\u00e9favorise\u0301') byłby dopasowany, mimo że ma dwa, éponieważ to 10 różnych znaków alfanumerycznych, po których następuje łączący akcent ostry (inny niż alfa, więc granica między tym ea jego akcentem jest ograniczona).

Okej ... oto niezręczny sposób na pięcioznakowy ciąg:

grep -P '^(.)(?!\1)(.)(?!\1|\2)(.)(?!\1|\2|\3)(.)(?!\1|\2|\3|\4).$'

Ponieważ nie możesz umieścić referencji wstecz w klasie postaci (np. [^\1|\2]), Musisz zastosować przeczące spojrzenie - (?!foo). Jest to funkcja PCRE, więc potrzebujesz -Pprzełącznika.

Wzorzec ciągu 10 znaków będzie oczywiście o wiele dłuższy, ale istnieje krótsza metoda wykorzystująca zmienną długość cokolwiek pasuje ('. *') W lookahead:

grep -P '^(.)(?!.*\1)(.)(?!.*\2)(.)(?!.*\3)(.)(?!.*\4)(.)(?!.*\5).$'

Po przeczytaniu pouczającej odpowiedzi Stephane'a Chazelasa, zdałem sobie sprawę, że istnieje podobny prosty wzór dla tego użytecznego za pomocą -vprzełącznika grep :

    (.).*\1

Ponieważ sprawdzanie odbywa się po jednym znaku na raz, zobaczysz, czy po danym znaku następuje zero lub więcej znaków ( .*), a następnie dopasowanie dla odwołania wstecznego. -vodwraca, drukując tylko rzeczy, które nie pasują do tego wzoru. To sprawia, że ​​referencje wsteczne są bardziej użyteczne, ponieważ nie można ich zanegować za pomocą klasy znaków, a znacznie:

grep -v '\(.\).*\1'

będzie działać, aby zidentyfikować ciąg dowolnej długości za pomocą unikalnych znaków, podczas gdy:

grep -P '(.)(?!.*\1)'

nie będzie, ponieważ będzie pasować do dowolnego sufiksu unikatowymi znakami (np. abcabcpasuje ze względu abcna koniec, a aaaaze względu ana koniec - stąd dowolny ciąg znaków). Jest to komplikacja spowodowana tym, że spojrzenia mają zerową szerokość (nic nie zużywają).

Jeśli nie musisz robić wszystkiego w wyrażeniu regularnym, zrobiłbym to w dwóch krokach: najpierw dopasuj wszystkie 10-literowe słowa, a następnie odfiltruj je pod kątem wyjątkowości. Najkrótszym sposobem, w jaki wiem, jak to zrobić, jest Perl:

perl -nle 'MATCH:while(/\W(\w{10})\W/g){
             undef %seen;
             for(split//,$1){next MATCH if ++$seen{$_} > 1}
             print
           }' your_file

Zwróć uwagę na dodatkowe \Wkotwice, aby zapewnić dopasowanie tylko słów o długości dokładnie 10 znaków.

Inni sugerują, że nie jest to możliwe bez różnych rozszerzeń niektórych systemów wyrażeń regularnych, które w rzeczywistości nie są regularne. Ponieważ jednak język, który chcesz dopasować, jest skończony, jest on wyraźnie regularny. W przypadku 3 liter z 4-literowego alfabetu byłoby to łatwe:

(abc|abd|acb|acd|bac|bad|bcd|bdc|cab|cad|cbd|cdb|dab|dac|dbc|dcb)

Oczywiście wymyka się to w pośpiechu z większą ilością liter i większych alfabetów. :-)

Opcja --perl-regexp(krótka -P) GNU grepużywa bardziej wydajnych wyrażeń regularnych, które zawierają wzorce wybiegające w przyszłość. Poniższy wzór wyszukuje każdą literę, której ta litera nie pojawia się w pozostałej części słowa:

grep -Pow '((\w)(?!\w*\g{-1})){10}'

Jednak zachowanie w czasie wykonywania jest dość złe, ponieważ \w*może mieć prawie nieskończoną długość. Można go ograniczyć do \w{,8}, ale to także sprawdza poza limitem słów 10 liter. Dlatego następujący wzorzec najpierw sprawdza poprawną długość słowa:

grep -Pow '(?=\w{10}\b)((\w)(?!\w*\g{-1})){10}'

Jako plik testowy wykorzystałem duży plik ≈ 500 MB:

• Pierwszy wzór: ≈ 43 s
• Późny wzór: ≈ 15 s

Aktualizacja:

Nie mogłem znaleźć znaczącej zmiany w zachowaniu w czasie wykonywania dla niewdzięcznego operatora ( \w*?) lub operatora dzierżawczego ( (...){10}+). Trochę szybciej wydaje się zastąpienie opcji -w:

grep -Po '\b(?=\w{10}\b)((\w)(?!\w*\g{-1})){10}\b'

Aktualizacja grep z wersji 2.13 do 2.18 była znacznie bardziej skuteczna. Plik testowy zajął tylko ≈ 6 sekund.

Rozwiązanie Perla:

perl -lne 'print if (!/(.)(?=$1)/g && /^\w{10}$/)' file

ale to nie działa

perl -lne 'print if (!/(.)(?=\1)/g && /^\w{10}$/)' file

lub

perl -lne 'print if ( /(.)(?!$1)/g && /^\w{10}$/)' file

testowane z perl v5.14.2 i v5.18.2