regulares - import re python para que sirve

Expresión regular que coincide con el primer carácter no repetido (4)

TL; DR

re.search("(.)(?!.*/1)", text).group() no coincide con el primer carácter que no se repite contenido en el texto (siempre devuelve un carácter en o antes del primero carácter repetido, o antes del final de la cadena si no hay caracteres no repetidos. Según tengo entendido, re.search () debe devolver Ninguno si no hubo coincidencias). Solo me interesa entender por qué esta expresión regular no funciona como se pretende con el módulo de re Python, no en ningún otro método para resolver el problema

Fondo completo

La descripción del problema proviene de https://www.codeeval.com/open_challenges/12/ . Ya resolví este problema utilizando un método no regex, pero lo revisé para ampliar mi comprensión del módulo de re de Python. Las expresiones regulares que pensé que funcionarían (denominadas contra referencias sin nombre) son:

(?P<letter>.)(?!.*(?P=letter)) y (.)(?!.*/1) (los mismos resultados en python2 y python3)

Todo mi programa se ve así

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

y algunos pares de entrada / salida son:

De acuerdo con lo que he leído en https://docs.python.org/2/library/re.html :

(.) crea un grupo con nombre que coincide con cualquier carácter y permite referencias posteriores a él como /1 .
(?!...) es un lookahead negativo que restringe las coincidencias a los casos donde ... no coincide.
.*/1 significa cualquier número (incluyendo cero) de caracteres seguido de cualquier cosa que haya coincidido con (.) Anteriormente
re.search(pattern, string) devuelve solo la primera ubicación donde el patrón de expresiones regulares produce una coincidencia (y devolvería Ninguno si no se pudiera encontrar una coincidencia)
.group() es equivalente a .group(0) que devuelve la coincidencia completa

Creo que estas piezas juntas deberían resolver el problema planteado, y funciona como creo que debería en la mayoría de los insumos, pero fracasó en la teething . Lanzar problemas similares revela que parece ignorar los caracteres repetidos si son consecutivos:

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

Sé que el aspecto detrás y el aspecto negativo están limitados a cadenas de longitud fija de 3 caracteres máx., Y no pueden contener referencias inversas, incluso si se evalúan a una cadena de longitud fija, pero no vi la documentación que especifique restricciones en el lookahead negativo.

Bien, tomemos el ejemplo de sus tooth : esto es lo que hace el motor de expresiones regulares (mucho simplificado para una mejor comprensión)

Comience con t luego mire hacia adelante en la cadena y falle el lookahead, ya que hay otra t .

tooth ^ °

Luego tome o , mire hacia adelante en la cadena, y falle, ya que hay otra o .

tooth ^°

Luego, tome la segunda o , mire hacia adelante en la cadena, no hay otra o presente, haga coincidir, devuélvala, trabaje.

tooth ^

De modo que su expresión regular no coincide con el primer carácter no repetido, sino con el primero, que no tiene más repeticiones hacia el final de la cadena.

La razón por la que su expresión regular no funciona es que no coincidirá con un carácter seguido por el mismo carácter, pero no hay nada que le impida coincidir con un carácter que no esté seguido por el mismo carácter, incluso si está precedido por el mismo personaje.

Las expresiones regulares no son óptimas para la tarea, incluso si utiliza implementaciones alternativas de re que no limitan la apariencia por cadenas de longitud fija (como la expresión regular de datos de Matthew Barnett).

La forma más fácil es contar las ocurrencias de letras e imprimir la primera con una frecuencia igual a 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)))

La respuesta de Sebastian ya explica bastante bien por qué tu intento actual no funciona.

.RED

Ya ~~que~~ revo está interesado en una solución de sabores .NET, la solución se vuelve trivial:

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

Enlace demo

Esto funciona porque .NET es compatible con la apariencia de longitud variable . También puede obtener ese resultado con Python (ver más abajo).

Así que para cada letra (?<letter>.) Comprobamos:

si se repite más en la entrada (?!.*?/k<letter>)
si ya se encontró antes (?<!/k<letter>.+?)
(tenemos que omitir la letra que estamos probando cuando retrocedemos, de ahí el + ).

Pitón

El módulo de expresiones regulares de Python también admite miradas de longitud variable, por lo que la expresión anterior de arriba funcionará con un pequeño cambio sintáctico: debe reemplazar /k con /g (lo cual es bastante desafortunado ya que con este módulo /g es una referencia de grupo, mientras que con PCRE es una recursión).

La expresión regular es:

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

Y he aquí un ejemplo:

$ 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, ahora las cosas empiezan a ensuciarse: ya que PCRE no soporta la apariencia de longitud variable, debemos recordar de alguna manera si una letra dada ya se encontró en la entrada o no.

Desafortunadamente, el motor de expresiones regulares no proporciona soporte de memoria de acceso aleatorio. Lo mejor que podemos obtener en términos de memoria genérica es una pila , pero eso no es suficiente para este propósito, ya que una pila solo nos permite acceder a su elemento superior.

Si aceptamos restringirnos a un alfabeto determinado, podemos abusar de capturar grupos con el fin de almacenar banderas. Veamos esto en un alfabeto limitado de las tres letras 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) )

Así es como funciona:

Primero, el anclaje /A asegura que procesaremos la cadena de entrada solo una vez
Luego, para cada letra X de nuestro alfabeto, configuraremos un indicador dX duplicado :
- El patrón condicional (?(cond)then|else) se usa allí:
  - La condición es (?=[^X]*+X[^X]*X) que es verdadera si la cadena de entrada contiene la letra X dos veces.
  - Si la condición es verdadera, la cláusula then es (?<dX>) , que es un grupo de captura vacío que coincidirá con la cadena vacía.
  - Si la condición es falsa, el grupo dX no coincidirá
- A continuación, omitimos perezosamente las letras válidas de nuestro alfabeto: [ac]*?
- Y los tiramos en el partido final con /K
- Ahora, estamos tratando de hacer coincidir una letra cuyo indicador de dX no está establecido. Para este propósito, haremos una rama condicional: (?(dX)(*FAIL)|X)
  - Si se combinó dX (lo que significa que X es un carácter duplicado), nosotros (*FAIL) a que el motor retroceda e intente una letra diferente.
  - Si dX no coincide, tratamos de igualar X En este punto, si esto tiene éxito, sabemos que X es la primera letra no duplicada.

Esa última parte del patrón también podría ser reemplazada por:

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

Que es algo más optimizado. Coincide con la letra actual primero y solo luego verifica si es un duplicado.

El patrón completo para las letras minúsculas az ve así:

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

Y aquí está la demostración en regex101 , completa con pruebas unitarias.

Puede ampliar este patrón si necesita un alfabeto más grande, pero obviamente esta no es una solución de propósito general. Es principalmente de interés educativo y no debe utilizarse para ninguna aplicación seria.

Para otros sabores, puede intentar modificar el patrón para reemplazar las características de PCRE con equivalentes más simples:

/A convierte en ^
X (*THEN) (?(dX)(*FAIL)) se puede reemplazar con (?(dX)(?!)|X)
Puede deshacerse de /K y reemplazar el último grupo noncapturnig (?: ... ) con un grupo nombrado como (?<letter> ... ) y tratar su contenido como el resultado.

El único constructo requerido pero algo inusual es el grupo condicional (?(cond)then|else) .