Regex pour tous les mots de 10 lettres, avec des lettres uniques

23

J'essaie d'écrire une expression régulière qui affichera tous les mots de 10 caractères et aucune des lettres ne se répète.

Jusqu'à présent, j'ai

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

C'est la toute première partie de la question. Comment pourrais-je procéder pour vérifier le «caractère unique»? Je n'ai vraiment aucune idée, à part cela, j'ai besoin d'utiliser des références arrières.

Dylan Meeus
la source
1
Cela doit être fait avec une expression régulière?
Hauke ​​Laging du
Je pratique le regex, donc de préférence oui :)
Dylan Meeus
3
Je ne crois pas que vous puissiez le faire avec une expression régulière de style informatique: ce que vous voulez nécessite une "mémoire" de ce que sont les caractères correspondants précédents, et les expressions régulières n'ont tout simplement pas cela. Cela dit, vous pourrez peut-être le faire avec des références arrières et les choses d'expression non régulière que la correspondance de style PCRE peut faire.
Bruce Ediger
3
@BruceEdiger tant qu'il y a un nombre fini de caractères dans la langue (26) et des lettres dans la chaîne (10), c'est tout à fait possible. C'est juste beaucoup d'états, mais rien qui ne ferait de lui une langue régulière.
1
Voulez-vous dire "Tous les mots anglais ..."? Voulez-vous inclure ou non ceux qui sont épelés avec des traits d'union et des apostrophes (beaux-parents, non)? Voulez-vous inclure des mots tels que café, naïf, façade?
hippietrail

Réponses:

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

exclut les mots qui ont deux caractères identiques.

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

exclut ceux qui ont des caractères répétitifs.

POSIX:

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

trplace les mots sur leur propre ligne en convertissant toute séquation de caractères autres que des mots ( ccomplément alphanumérique et trait de soulignement) en caractère de nouvelle ligne.

Ou avec un grep:

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

(exclure les lignes de moins de 10 et de plus de 10 caractères et celles dont le caractère apparaît au moins deux fois).

Avec un grepseul (GNU grep avec support PCRE ou pcregrep):

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

C'est-à-dire, une limite de mot ( \b) suivie d'une séquence de 10 caractères de mot (à condition que chacun ne soit pas suivi d'une séquence de caractères de mot et eux-mêmes, en utilisant l'opérateur PCRE d'anticipation négative (?!...)).

Nous avons de la chance que cela fonctionne ici, car peu de moteurs d'expression rationnelle fonctionnent avec des références inverses à l'intérieur de parties répétitives.

Notez que (avec ma version de GNU grep au moins)

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

Ne fonctionne pas, mais

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

fait (comme echo aa | grep -Pw '(.)\2') ce qui ressemble à un bug.

Vous voudrez peut-être:

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

si vous voulez \wou \bconsidérez n'importe quelle lettre comme un composant de mot et pas seulement celles ASCII dans les locales non ASCII.

Une autre alternative:

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

Il s'agit d'une limite de mot (celle qui n'est pas suivie d'une séquence de caractères de mot dont l'un se répète) suivie de 10 caractères de mot.

Choses à avoir éventuellement à l'esprit:

  • La comparaison est sensible à la casse, donc Babylonishpar exemple serait appariée, car tous les caractères sont différents même s'il y a deux Bs, un minuscule et un majuscule (utilisez -ipour changer cela).
  • pour -w, \wet \b, un mot est une lettre (celles ASCII uniquement pour GNU grep pour le moment , la [:alpha:]classe de caractères dans vos paramètres régionaux si vous utilisez -Pet (*UCP)), des chiffres décimaux ou un trait de soulignement .
  • cela signifie que c'est(deux mots selon la définition française d'un mot) ou it's(un mot selon certaines définitions anglaises d'un mot) ou rendez-vous(un mot selon la définition française d'un mot) ne sont pas considérés comme un mot.
  • Même avec (*UCP), les caractères de combinaison Unicode ne sont pas considérés comme des composants de mots, donc téléphone( $'t\u00e9le\u0301phone') est considéré comme 10 caractères, dont un non alpha. défavorisé( $'d\u00e9favorise\u0301') serait apparié même s'il y en a deux, écar il s'agit de 10 caractères alpha différents, suivis d'un accent aigu combiné (non alpha, il y a donc une limite de mot entre le eet son accent).
Stéphane Chazelas
la source
1
Impressionnant. \wne correspond pas -cependant.
Graeme
@Stephane Pouvez-vous poster une brève explication des deux dernières expressions.
mkc
Parfois, il semble que les contournements soient la solution à toutes les choses qui étaient auparavant impossibles avec RE.
Barmar
1
@Barmar, ils sont toujours impossibles avec les expressions régulières. Une "expression régulière" est une construction mathématique qui n'autorise explicitement que certaines constructions, à savoir les caractères littéraux, les classes de caractères et les opérateurs "|", "(...)", "?", "+" Et "*". Toute soi-disant "expression régulière" qui utilise un opérateur qui n'est pas l'un des ci-dessus n'est pas en fait une expression régulière.
Jules
1
@Jules C'est unix.stackexchange.com, pas math.stackexchange.com. Les RE mathématiques ne sont pas pertinentes dans ce contexte, nous parlons des types de RE que vous utilisez avec grep, PCRE, etc.
Barmar
12

D'accord ... voici la méthode maladroite pour une chaîne de cinq caractères:

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

Parce que vous ne pouvez pas mettre une référence arrière dans une classe de caractères (par exemple [^\1|\2]), vous devez utiliser une anticipation négative - (?!foo). Il s'agit d'une fonction PCRE, vous avez donc besoin du -Pcommutateur.

Le modèle pour une chaîne de 10 caractères sera beaucoup plus long, bien sûr, mais il existe une méthode plus courte utilisant une correspondance de n'importe quoi de longueur variable ('. *') Dans l'anticipation:

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

Après avoir lu la réponse éclairante de Stéphane Chazelas, je me suis rendu compte qu'il existe un modèle simple similaire pour cela utilisable via le -vcommutateur de grep :

    (.).*\1

Étant donné que la vérification procède un caractère à la fois, cela verra si un caractère donné est suivi par zéro ou plusieurs caractères ( .*), puis une correspondance pour la référence arrière. -vinverse, n'imprimant que les éléments qui ne correspondent pas à ce modèle. Cela rend les références arrières plus utiles car elles ne peuvent pas être annulées avec une classe de caractère, et de manière significative:

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

fonctionnera pour identifier une chaîne de n'importe quelle longueur avec des caractères uniques alors que:

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

ne le fera pas, car il correspondra à tout suffixe avec des caractères uniques (par exemple, abcabccorrespond à cause de abcà la fin et à aaaacause de ala fin - d'où toute chaîne). Il s'agit d'une complication causée par des contournements de largeur nulle (ils ne consomment rien).

boucle d'or
la source
Bien joué! Cela ne fonctionnera cependant qu'en combinaison avec celui du Q.
Graeme
1
Je pense que vous pouvez simplifier le premier si votre moteur d'expression régulière permet une anticipation négative de longueur variable:(.)(?!.*\1)(.)(?!.*\2)(.)(?!.*\3)(.)(?!\4).
Christopher Creutzig
@ChristopherCreutzig: Absolument, bel appel. Je l'ai ajouté.
goldilocks
6

Si vous n'avez pas besoin de faire tout cela en regex, je le ferais en deux étapes: d'abord faire correspondre tous les mots de 10 lettres, puis les filtrer pour l'unicité. Le moyen le plus court que je connais pour le faire est en Perl:

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

Notez les \Wancres supplémentaires pour vous assurer que seuls les mots de 10 caractères exactement correspondent.

Joseph R.
la source
Merci, mais je le voudrais comme oneliner regex :)
Dylan Meeus
4

D'autres ont suggéré que cela n'est pas possible sans diverses extensions de certains systèmes d'expression régulière qui ne sont en fait pas réguliers. Cependant, comme la langue que vous souhaitez associer est finie, elle est clairement régulière. Pour 3 lettres d'un alphabet à 4 lettres, ce serait facile:

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

De toute évidence, cela devient incontrôlable avec plus de lettres et des alphabets plus grands. :-)

R ..
la source
J'ai dû voter contre, car c'est en fait une réponse qui fonctionnerait. Bien qu'il s'agisse en fait de la façon la moins efficace jamais écrite de regex: P
Dylan Meeus
4

Option --perl-regexp(courte -P) de GNUgrep utilise des expressions régulières plus puissantes qui incluent des modèles d'anticipation. Le modèle suivant recherche pour chaque lettre que cette lettre n'apparaît pas dans le reste du mot:

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

Cependant, le comportement au moment de l'exécution est assez mauvais, car il \w*peut avoir une longueur presque infinie. Il peut être limité à\w{,8} , mais cela vérifie également au-delà de la limite de 10 lettres. Par conséquent, le modèle suivant vérifie d'abord la longueur de mot correcte:

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

En tant que fichier de test, j'ai utilisé un gros fichier de 500 Mo:

  • Premier motif: ≈ 43 s
  • Dernier motif: ≈ 15 s

Mise à jour:

Je n'ai pas pu trouver de changement significatif dans le comportement à l'exécution pour un opérateur non gourmand ( \w*?) ou un opérateur possessif ( (...){10}+). Un tout petit peu plus rapide semble le remplacement de l'option -w:

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

Une mise à jour de grep de la version 2.13 à 2.18 était beaucoup plus efficace. Le fichier de test n'a pris que ≈ 6 s.

Heiko Oberdiek
la source
Les performances dépendront beaucoup de la nature des données. Lors des tests sur le mien, j'ai trouvé que l'utilisation d'opérateurs non gourmands ( \w{,8}?) aidait pour certains types d'entrées (mais pas de manière très significative). Belle utilisation de \g{-1}pour contourner le bogue de grep GNU.
Stéphane Chazelas
@StephaneChazelas: Merci pour la rétroaction. J'avais également essayé des opérateurs non gourmands et possessifs et je n'ai pas trouvé de changement significatif dans le comportement à l'exécution (version 2.13). La version 2.18 est beaucoup plus rapide et j'ai pu voir au moins une petite amélioration. Le bogue GNU grep est présent dans les deux versions. Quoi qu'il en soit, je préfère la référence relative \g{-1}, car elle rend le motif plus indépendant de l'emplacement. Sous cette forme, il peut être utilisé dans le cadre d'un modèle plus large.
Heiko Oberdiek
0

Une solution Perl:

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

mais ça ne marche pas avec

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

ou

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

testé avec perl v5.14.2 et v5.18.2


la source
Le 1er et le 3e ne font rien, le 2e sort n'importe quelle ligne de 10 caractères ou plus, avec pas plus de 2 espaces consécutifs. pastebin.com/eEDcy02D
manatwork
c'est probablement la version perl. testé avec v5.14.2 et v5.18.2
Je les ai essayés avec v5.14.1 sur Linux et v5.14.2 sur Cygwin. Les deux se sont comportés comme dans l'exemple pastebin que j'ai lié plus tôt.
manatwork
la première ligne fonctionne pour moi avec les versions notées de perl. les deux derniers devraient fonctionner, car ils sont les mêmes, mais pas. Perlre note souvent que certaines expressions gourmandes sont très expérimentales.
Retesté avec vos dernières mises à jour. Seul le 2ème émet correctement. (Cependant, le mot doit être seul dans une ligne, alors que la question concerne les mots correspondants, pas des lignes entières.)
manatwork