Expression régulière correspondant au premier caractère non répété

Question

TL;DR

re.search("(.)(?!.*\1)", text).group() ne correspond pas à la première non-répétition des caractères figurant dans le texte (il renvoie toujours un personnage au ou avant le premier non-caractère répété, ou avant la fin de la chaîne si il n'y a pas non caractères répétés. Ma compréhension est que la ré.recherche() doit renvoyer None s'il n'y avait pas de matchs). Je suis seulement intéressé à comprendre pourquoi cette regex ne fonctionne pas comme prévu à l'aide de l'Python re module, non pas dans un autre moyen de résoudre le problème

Historique Complet

La description du problème vient de la https://www.codeeval.com/open_challenges/12/. J'ai déjà résolu ce problème en utilisant un non-regex méthode, mais revisité à élargir ma compréhension de Python remodule. Les expressions régulières me semblait (nommé vs sans nom dans les références arrières) sont:

(?P<letter>.)(?!.*(?P=letter)) et (.)(?!.*\1) (mêmes résultats en python2 et python3)

L'ensemble de mon programme ressemble à ceci

import re
import sys
with open(sys.argv[1], 'r') as test_cases:
    for test in test_cases:
        print(re.search("(?P<letter>.)(?!.*(?P=letter))",
                        test.strip()
                       ).group()
             )

et certaines paires d'entrées/sorties sont:

rain | r
teetthing | e
cardiff | c
kangaroo | k
god | g
newtown | e
taxation | x
refurbished | f
substantially | u

Selon ce que j'ai lu à https://docs.python.org/2/library/re.html:

• (.) crée un groupe nommé qui correspond à tout caractère et permet plus tard de références arrières comme \1.
• (?!...) est une anticipation négatif, ce qui limite correspond aux cas où l' ... ne correspond pas.
• .*\1 signifie n'importe quel nombre (y compris zéro) de caractères suivie par tout ce qui a été compensée par (.) précédemment
• re.search(pattern, string) retourne uniquement le premier endroit où l'regex modèle produit un match (et le retour Aucune si aucune correspondance n'a pu être trouvé)
• .group() est équivalent à .group(0) qui renvoie l'intégralité du match

Je pense que ces pièces ensemble devrait résoudre le problème posé, et il ne fonctionne pas comme je pense qu'il doit pour la plupart des entrées, mais a échoué sur teething. Jeter des problèmes semblables à lui révèle qu'il semble ignorer les caractères répétés si elles sont consécutives:

tooth | o      # fails on consecutive repeated characters
aardvark | d   # but does ok if it sees them later
aah | a        # verified last one didn't work just because it was at start
heh | e        # but it works for this one
hehe | h       # What? It thinks h matches (lookahead maybe doesn't find "heh"?)
heho | e       # but it definitely finds "heh" and stops "h" from matching here
hahah | a      # so now it won't match h but will match a
hahxyz | a     # but it realizes there are 2 h characters here...
hahxyza | h    # ... Ok time for StackOverflow

Je sais lookbehind et négatifs lookbehind sont limités à 3 caractères max chaînes de longueur fixe, et ne peut pas contenir de références arrières, même si ils évaluent à une chaîne de longueur fixe, mais je n'ai pas voir la documentation de préciser les restrictions sur l'anticipation négatif.

Answer 1

Eh bien nous allons prendre votre tooth exemple - voici ce que les regex moteur (beaucoup simplifié pour une meilleure compréhension)

Commencez avec t ensuite aller de l'avant dans la chaîne - et l'échec de l'anticipation, car il est un autre t.

tooth
^  °

Prenez ensuite o, regarder de l'avant dans la chaîne - et l'échec, car il y a un autre o.

tooth
 ^°

Suivant, prendre la deuxième o, regarder de l'avant dans la chaîne - aucun autre o aujourd'le match, le retourner, le travail effectué.

tooth
  ^

Si votre regex ne correspond pas à la première unrepeated caractère, mais la première, qui n'a plus de répétitions vers la fin de la chaîne.

Answer 2

Sebastian réponse déjà explique assez bien pourquoi votre tentative ne fonctionne pas.

.NET

Puisque vous êtes revo est intéressé par un .NET saveur solution, la solution devient limpide:

(?<letter>.)(?!.*?\k<letter>)(?<!\k<letter>.+?)

Le lien de démonstration

Cela fonctionne parce que .NET prend en charge de longueur variable lookbehinds. Vous pouvez également obtenir ce résultat avec Python (voir ci-dessous).

Donc, pour chaque lettre (?<letter>.) nous vérifions:

• si elle est répétée plus loin dans l'entrée (?!.*?\k<letter>)
• si elle a déjà été rencontré avant (?<!\k<letter>.+?)
  (nous avons d'ignorer la lettre que nous mettons à l'essai lorsque l'on va vers l'arrière, d'où l' +).

---

Python

Le Python regex module prend également en charge de longueur variable lookbehinds, de sorte que l'expression régulière ci-dessus va travailler avec un changement syntaxique: vous avez besoin de remplacer \k avec \g (ce qui est très malheureux, car avec ce module \g est un groupe de référence arrière, alors qu'avec PCRE c'est une récursivité).

L'expression régulière est:

(?<letter>.)(?!.*?\g<letter>)(?<!\g<letter>.+?)

Et voici un exemple:

$ python
Python 2.7.10 (default, Jun  1 2015, 18:05:38)
[GCC 4.9.2] on cygwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import regex
>>> regex.search(r'(?<letter>.)(?!.*?\g<letter>)(?<!\g<letter>.+?)', 'tooth')
<regex.Match object; span=(4, 5), match='h'>

---

PCRE

Ok, maintenant, les choses commencent à se salir: depuis PCRE ne supporte pas de longueur variable lookbehinds, nous devons en quelque sorte rappelez-vous si une lettre a déjà été rencontré dans l'entrée ou pas.

Malheureusement, le moteur d'expressions régulières ne fournit pas d'accès aléatoire en charge de la mémoire. Le mieux que nous pouvons obtenir en termes de mémoire générique est un pile - mais ce n'est pas suffisant pour cela, comme une pile ne nous permet d'accéder à son élément supérieur.

Si nous acceptons de nous retenir, pour un alphabet, nous pouvons abus de capturer les groupes dans le but de stocker des drapeaux. Voyons cela sur un petit alphabet de trois lettres abc:

# Anchor the pattern
\A

# For each letter, test to see if it's duplicated in the input string
(?(?=[^a]*+a[^a]*a)(?<da>))
(?(?=[^b]*+b[^b]*b)(?<db>))
(?(?=[^c]*+c[^c]*c)(?<dc>))

# Skip any duplicated letter and throw it away
[a-c]*?\K

# Check if the next letter is a duplicate
(?:
  (?(da)(*FAIL)|a)
| (?(db)(*FAIL)|b)
| (?(dc)(*FAIL)|c)
)

Voici comment cela fonctionne:

• Tout d'abord, l' \A d'ancrage assure que nous allons processus de la chaîne d'entrée qu'une seule fois
• Ensuite, pour chaque lettre X de notre alphabet, nous allons mettre en place une est double drapeau dX:
  • Le conditionnel modèle (?(cond)then|else) est utilisé:
    • La condition est - (?=[^X]*+X[^X]*X) , ce qui est vrai si la chaîne d'entrée contient la lettre X deux fois.
    • Si la condition est vrai, alors la clause est - (?<dX>), ce qui est un vide capture d'un groupe qui correspond à la chaîne vide.
    • Si la condition est fausse, l' dX groupe ne sera pas égalé
  • Ensuite, nous paresseusement sauter valide les lettres de notre alphabet: [a-c]*?
  • Et nous jeter dans le match final, avec \K
  • Maintenant, nous essayons de faire correspondre une lettre dont l' dX indicateur est pas définie. Pour cela, nous allons faire une branche conditionnelle: (?(dX)(*FAIL)|X)
    • Si dX a été appariés (ce qui signifie qu' X est un doublon de caractère), nous (*FAIL), de forcer le moteur à revenir en arrière et essayer à une autre lettre.
    • Si dX a pas de correspondance, nous essayons de faire correspondre X. À ce stade, si cela réussit, nous savons qu' X est le premier non-doublé lettre.

La dernière partie du modèle pourrait également être remplacé par:

(?:
  a (*THEN) (?(da)(*FAIL))
| b (*THEN) (?(db)(*FAIL))
| c (*THEN) (?(dc)(*FAIL))
)

Ce qui est un peu plus optimisé. Il correspond à la lettre d'abord et seulement ensuite, vérifie si c'est un doublon.

Le modèle complet pour les lettres minuscules a-z ressemble à ceci:

# Anchor the pattern
\A

# For each letter, test to see if it's duplicated in the input string
(?(?=[^a]*+a[^a]*a)(?<da>))
(?(?=[^b]*+b[^b]*b)(?<db>))
(?(?=[^c]*+c[^c]*c)(?<dc>))
(?(?=[^d]*+d[^d]*d)(?<dd>))
(?(?=[^e]*+e[^e]*e)(?<de>))
(?(?=[^f]*+f[^f]*f)(?<df>))
(?(?=[^g]*+g[^g]*g)(?<dg>))
(?(?=[^h]*+h[^h]*h)(?<dh>))
(?(?=[^i]*+i[^i]*i)(?<di>))
(?(?=[^j]*+j[^j]*j)(?<dj>))
(?(?=[^k]*+k[^k]*k)(?<dk>))
(?(?=[^l]*+l[^l]*l)(?<dl>))
(?(?=[^m]*+m[^m]*m)(?<dm>))
(?(?=[^n]*+n[^n]*n)(?<dn>))
(?(?=[^o]*+o[^o]*o)(?<do>))
(?(?=[^p]*+p[^p]*p)(?<dp>))
(?(?=[^q]*+q[^q]*q)(?<dq>))
(?(?=[^r]*+r[^r]*r)(?<dr>))
(?(?=[^s]*+s[^s]*s)(?<ds>))
(?(?=[^t]*+t[^t]*t)(?<dt>))
(?(?=[^u]*+u[^u]*u)(?<du>))
(?(?=[^v]*+v[^v]*v)(?<dv>))
(?(?=[^w]*+w[^w]*w)(?<dw>))
(?(?=[^x]*+x[^x]*x)(?<dx>))
(?(?=[^y]*+y[^y]*y)(?<dy>))
(?(?=[^z]*+z[^z]*z)(?<dz>))

# Skip any duplicated letter and throw it away
[a-z]*?\K

# Check if the next letter is a duplicate
(?:
  a (*THEN) (?(da)(*FAIL))
| b (*THEN) (?(db)(*FAIL))
| c (*THEN) (?(dc)(*FAIL))
| d (*THEN) (?(dd)(*FAIL))
| e (*THEN) (?(de)(*FAIL))
| f (*THEN) (?(df)(*FAIL))
| g (*THEN) (?(dg)(*FAIL))
| h (*THEN) (?(dh)(*FAIL))
| i (*THEN) (?(di)(*FAIL))
| j (*THEN) (?(dj)(*FAIL))
| k (*THEN) (?(dk)(*FAIL))
| l (*THEN) (?(dl)(*FAIL))
| m (*THEN) (?(dm)(*FAIL))
| n (*THEN) (?(dn)(*FAIL))
| o (*THEN) (?(do)(*FAIL))
| p (*THEN) (?(dp)(*FAIL))
| q (*THEN) (?(dq)(*FAIL))
| r (*THEN) (?(dr)(*FAIL))
| s (*THEN) (?(ds)(*FAIL))
| t (*THEN) (?(dt)(*FAIL))
| u (*THEN) (?(du)(*FAIL))
| v (*THEN) (?(dv)(*FAIL))
| w (*THEN) (?(dw)(*FAIL))
| x (*THEN) (?(dx)(*FAIL))
| y (*THEN) (?(dy)(*FAIL))
| z (*THEN) (?(dz)(*FAIL))
)

Et voici la démo sur regex101, complet avec les tests unitaires.

Vous pouvez étendre sur ce modèle si vous avez besoin d'une plus grande alphabet, mais évidemment, ce n'est pas une solution. C'est principalement de l'intérêt pédagogique et de devrait pas être utilisé pour toute application sérieuse.

---

Pour d'autres saveurs, vous pouvez essayer de modifier le modèle pour remplacer PCRE fonctionnalités simples équivalents:

• \A devient ^
• X (*THEN) (?(dX)(*FAIL)) peut être remplacé par (?(dX)(?!)|X)
• Vous pouvez jeter l' \K et remplacer la dernière noncapturnig groupe (?:...) avec un nom de groupe comme (?<letter>...) et de traiter son contenu comme résultat.

La seule nécessaire, mais quelque peu inhabituelle construire, c'est le conditionnel groupe (?(cond)then|else).

Answer 3

Les expressions régulières ne sont pas optimales pour la tâche même si vous utilisez des implémentations alternatives de re qui ne limitent pas le lookbehind par des chaînes de longueur fixe (comme l'expression régulière de Matthew Barnett).

Le moyen le plus simple consiste à compter les occurrences de lettres et à imprimer la première avec une fréquence égale à 1:

 import sys
from collections import Counter, OrderedDict

# Counter that remembers that remembers the order entries were added
class OrderedCounter(Counter, OrderedDict):
    pass

# Calling next() once only gives the first entry
first=next

with open(sys.argv[1], 'r') as test_cases:
    for test in test_cases:
        lettfreq = OrderedCounter(test)
        print(first((l for l in lettfreq if lettfreq[l] == 1)))
 

Answer 4

La raison pour laquelle votre expression régulière ne fonctionne pas est qu'elle ne correspondra pas à un caractère suivi du même caractère, mais rien ne l'empêche de correspondre à un caractère qui n'est pas suivi par le même caractère, même s'il est précédé par le même personnage.